Goldmine

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 n
A number m
e11
e12..
e21
e22..
.. n * m number of elements

Output Format

An integer representing Maximum gold available.

Question Video Constraints

1 <= n <= 10^2
1 <= m <= 10^2
0 <= e1, e2, .. n * m elements <= 1000

Sample Input

6
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

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.

  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 = 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

• Asked in Companies
• Related Topics