Goldmine
1. You are given a number n, representing the number of rows.Input Format
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 rightup (d1), 1 cell right (d2) or 1 cell rightdown(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.
A number nOutput Format
A number m
e11
e12..
e21
e22..
.. n * m number of elements
An integer representing Maximum gold available.Question Video
1 <= n <= 10^2Sample Input
1 <= m <= 10^2
0 <= e1, e2, .. n * m elements <= 1000
6Sample Output
6
0 1 4 2 8 2
4 3 6 5 0 4
1 2 4 1 4 6
2 0 7 3 2 2
3 1 5 9 2 4
2 7 0 8 5 1
33

Editorial
Valid Moves:
Let us say we are at (i, j)th cell Given that valid moves from any cell are either diagonallyup, right, diagonallydown From (i,j) th cell if we move diagonally up will lead us to (i1, 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 (i1, 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(i1, 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[ i1 ][ 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 columnwise in the right to left direction.
6) Required answer:
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 = m1; 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[i1][j+1], dp[i][j+1]); } else { dp[i][j] = gold[i][j] + max(dp[i1][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

Asked in Companies

Related Topics