# Goldmine

#### Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

`1. You are given a number n, representing the number of rows.2. You are given a number m, representing the number of columns.3. You are given n*m numbers, representing elements of 2d array a, which represents a gold mine.4. You are standing in front of left wall and are supposed to dig to the right wall. You can start from      any row in the left wall.5. You are allowed to move 1 cell right-up (d1), 1 cell right (d2) or 1 cell right-down(d3).6. Each cell has a value that is the amount of gold available in the cell.7. You are required to identify the maximum amount of gold that can be dug out from the mine.`
Input Format
`A number nA number me11e12..e21e22.... n * m number of elements`
Output Format
`An integer representing Maximum gold available.`
Question Video
Constraints
`1 <= n <= 10^21 <= m <= 10^20 <= e1, e2, .. n * m elements <= 1000`
Sample Input
`660 1 4 2 8 24 3 6 5 0 41 2 4 1 4 62 0 7 3 2 23 1 5 9 2 42 7 0 8 5 1`
Sample Output
`33`

• Editorial

Valid Moves:

Let us say we are at (i, j)th cell Given that valid moves from any cell are either diagonally-up, right, diagonally-down From (i,j) th cell if we move diagonally up will lead us to (i-1, j+1)th cell right will lead us to (i, j+1)th cell diagonally down will lead us to (i+1, j+1)th cell

Approach:

Let gold(i, j) represent the amount of gold present at (i, j)th cell.

Let max_gold(i, j) represent the maximum gold that can be collected if we start from   (i, j)th cell and reach any cell belonging to the last column.

Now we know that from (i, j)th cell we have a choice to move to either (i-1, j+1) or (i, j+1), or (i+1, j+1). But to get the max gold from the current cell, we have to choose the next cell such that the next cell should lead us to the maximum gold collection. This can be recursively written as follows.

max_gold(i, j) = gold(i, j) + MAX{ max_gold(i-1, j+1), max_gold(i, j+1), max_gold(i+1, j+1) }

Tabulation:

1) Create a DB table with the same dimension as the given gold matrix(n rows and m columns).

2) dp[ i ][ j ] represents the maximum gold that can be collected if we start from the (i, j)th cell and reach any of the cells in the last column.

3) Recursive eq:

dp[ i ][ j ] = gold[ i ][ j ] + MAX( dp[ i - 1 ][ j + 1 ], dp[ i ][ j + 1 ], dp[ i + 1 ][ j + 1  ] )4) Base conditions:

a)If current cell is already in the last column i.e., j = m - 1

dp[ i ][ m - 1 ]  = gold[ i ][ m - 1 ]

b)If the current cell belongs to the first row(i = 0), then diagonally up is an invlid move

dp[ i ][ j ] = gold[ i ][ j ] + MAX( dp[ i ][ j + 1 ], dp[ i + 1 ][ j + 1  ] )

c) If the current cell belongs to the last column(i = n - 1), then diagonally down is an invalid move.

dp[ i ][ j ] = gold[ i ][ j ] + MAX( dp[ i - 1 ][ j + 1 ], dp[ i ][ j + 1 ] )

5) Direction of filling the DP table:

To fill dp[ i ][ j ] in O(1) time, we should know the values of the dp[ i-1 ][ j + 1 ], dp[ i ][ j + 1 ], dp[ i + 1 ][ j + 1 ]. I.e., values of the adjacent right columns should be known.

Hence we will fill the DP table column-wise in the right to left direction.

As we can start from any cell in the first column, to collect the maximum gold, we will choose the cell belonging to the first column with max_gold value from the DP table

Example:

As we can start from any of the cells in the first row, to get the maximum gold, we will start with the cell which will lead us to the maximum gold.

Here it is 33, if we start from the cell(4, 0)

Code:

```int goldmines(vector > &gold, int n, int m) {
vector> dp(n, vector (m, 0));

for(int j = m-1; j >= 0; j--) { //filling columns from right to left
for(int i = 0; i < n; i++) { // filling rows from top to bottom
if(j == m - 1) {
//last column
dp[i][j] = gold[i][j];
} else if(i == 0) {
//first row => diagonal up is an invalid move
dp[i][j] = gold[i][j] + max(dp[i][j+1], dp[i+1][j+1]);
} else if(i == n -1) {
//last row => diagonal down is an invalid move
dp[i][j] = gold[i][j] + max(dp[i-1][j+1], dp[i][j+1]);
} else {
dp[i][j] = gold[i][j] + max(dp[i-1][j+1], max(dp[i][j+1], dp[i+1][j+1]));
}
}
}

int max_gold = INT_MIN;
for(int i = 0; i < n; i++) {
//choosing the starting cell which lead us to collect maximum gold
max_gold = max(max_gold, dp[i][0]);
}

return max_gold;
}```

java false

Time complexity:

Each cell of the dp table takes O(1) time. Total number of cells in the dp table = n * m Total time complexity = n * m * O(1) = O(mn) = O(n^2) (assuming n > m)  - Senojiya Jill patel

• Related Topics

Run

Run
Id Name