Description:

描述：

This is a standard interview problem featured in interview coding rounds of Amazon, Flipkart.

這是亞馬遜Flipkart的采訪編碼回合中的標準采訪問題。

Problem statement:

問題陳述：

Given a gold mine of n*m dimensions, each cell in this mine contains a positive integer which is the amount of gold in tons. Initially, the miner is at the first column but can be at any row. He can move only right or right up or right down from the current cell, i.e., the miner can move to the cell diagonally up towards the right or right or diagonally down towards the right. Find out the maximum amount of gold he can collect.

給定一個 n * m尺寸 的金礦，該礦中的每個單元格都包含一個正整數，該黃金數量以噸為單位。 最初，該礦工位于第一列，但可以位于任何行。 他只能從當前牢房向右或向右或向下移動，即，礦工可以向右或向右斜向上或向右斜向向下移動到該牢房。 找出他可以收集的最大數量的黃金。

    Input:
Matrix:
{{1,5,12},
{2,4,4},
{0,6,4}
{3,0,0}	
}
Output: 
18
Input:
Matrix:
{{1,3,1,5},
{2,2,4,1},
{5,0,2,3},
{0,6,11,2}
}
Output: 
25

Explanation with example

舉例說明

So, the matrix is:

因此，矩陣為：

So, the miner starts from the first column (any row) and he has to reach the last row with maximum gold.

因此，礦工從第一列(任意行)開始，他必須以最大的金數到達最后一行。

To make a note, the possible moves from a cell (i,j) is to either of,

要說明一下，從單元格(i，j)可能移動到以下任一位置：

Now, it seems apparently that greedy may work for the problem that is at the first column pick the cell with maximum value and then move to next best neighbouring cell.

現在，似乎貪婪似乎可以解決以下問題：在第一列中選??擇具有最大值的單元格，然后移至下一個最佳相鄰單元格。

If we follow the above greedy approach,

如果我們遵循以上貪婪的方法，

We would pick (3,0) as our starting cell since that contains maximum gold out of the first column. The next best move would be (2,1) and then to (2,2).

我們將(3,0)作為起始單元格，因為它包含第一列中最多的金。 下一個最佳移動是(2,1)然后到(2,2) 。

So, the total gold collected is = (3+6+4) = 13

因此，收集的總金= (3 + 6 + 4)= 13

Is this the global maximum? Do our local maximum choices lead to global maximum?

這是全球最大值嗎？ 我們的局部最大選擇會導致整體最大嗎？

No, it's not the global maximum.

不，這不是全局最大值。

The global maximum path would be: (1,0) ->(0,1)->(0,2)

全局最大路徑為： (1,0)->(0,1)->(0,2)

Total coin that can be achieved: (2+5+12) = 19

可以達到的總硬幣數： (2 + 5 + 12)= 19

So, the local best choices don't lead to the global best and hence we need dynamic programming.

因此，本地的最佳選擇不會導致全球最佳，因此我們需要動態編程。

Solution Approach:

解決方法：

Create a DP matrix of dimension m*n: DP[m][n]

創建尺寸為m * n的DP矩陣： DP [m] [n]

The first column of the DP matrix would be same as the input matrix. Rest of the columns are 0,

DP矩陣的第一列將與輸入矩陣相同。 其余列為0，

    for i=0 to n-1
DP[i][0]=arr[i][0];

For the other columns, update DP value for every row. For every cell (i,j) update like following way.

對于其他列，更新每行的DP值。 對于每個單元格(i，j)都按照以下方式進行更新。

So, for the earlier input matrix,

因此，對于較早的輸入矩陣，

After completion of the First column (row wise computing),

完成第一列(行計算)后，

After completion of second column (row wise computation),

完成第二列后(行計算)，

Now find the maximum of the final column, that's the maximum gold that can be collected.

現在找到最后一列的最大值，這就是可以收集的最大黃金量。

Result=19

結果= 19

C++ implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
int GoldMine(int** arr, int n, int m)
{
//DP table
int DP[n][m];
memset(DP, 0, sizeof(DP));
for (int i = 0; i < n; i++)
DP[i][0] = arr[i][0];
//for every column
for (int j = 1; j < m; j++) {
//check which option is better accordingly
for (int i = 0; i < n; i++) {
//choosing max of possible moves
DP[i][j] = arr[i][j];
int val = DP[i][j - 1];
if (i - 1 >= 0) {
if (val < DP[i - 1][j - 1])
val = DP[i - 1][j - 1];
}
if (i + 1 < n) {
if (val < DP[i + 1][j - 1])
val = DP[i + 1][j - 1];
}
DP[i][j] += val;
}
}
// find the maximum of the last column
int gold = DP[0][m - 1];
for (int i = 1; i < n; i++) {
if (DP[i][m - 1] > gold)
gold = DP[i][m - 1];
}
return gold;
}
int main()
{
int n, item, m;
cout << "Enter matrix dimensions, m & n\n";
cin >> n >> m;
cout << "Input matrix cells\n";
int** arr = (int**)(malloc(sizeof(int*) * n));
//input array
for (int j = 0; j < n; j++) {
arr[j] = (int*)(malloc(sizeof(int) * m));
for (int k = 0; k < m; k++)
cin >> arr[j][k];
}
cout << "Max amount of gold that can be collected: " << GoldMine(arr, n, m) << endl;
return 0;
}

Output

輸出量

Enter matrix dimensions, m & n
4 3
Input matrix cells
1 5 12
2 4 4
0 6 4
3 0 0
Max amount of gold that can be collected: 19

翻譯自: https://www.includehelp.com/icp/gold-mine-problem.aspx