Redirecting to
NADOS


  Prev   Next

Goldmine







It's never the changes we want that change everything.
~ Junot Diaz

Goldmine

Hey there coder. Enjoying DP till now? Well, guess what ? Things are about to get even more interesting. After all, Gold is involved, you know that one thing we all are running after?

Important Links : Question Video, Solution Video

This question is quite similar to the previous question "Min Cost in Maze Traversal" so you should watch that video first before attempting this question.

Enough chit chat. Let's get on with the question.

Problem Discussion :

Have you read the problem statement? It's fairly simple. Let's catch you up on that or you can just watch the question video.

  • You are given a grid of size n*m where n and m represent rows and columns respectively and the grid as a whole represents a gold mine.
  • You are standing in front of the left wall and are supposed to dig to the right wall. You can start from any row in the left wall.
  • You are allowed to move 1 cell right-up (d1), 1 cell right (d2) or 1 cell right-down (d3).
  • Each cell has a value that is the amount of gold available in the cell.
  • You are required to identify the maximum amount of gold that can be dug out from the mine.
img

In Figure 1, you can see that you can start from any row of the start column and have to reach any row in the end column such that the maximum amount of gold can be collected.

If we are in cell '1' (as in Figure 1) then we have 3 choices to make 1 step: right-up ('3'), right ('2') or right-down ('0').

Some of the paths that can be taken are depicted with a blue line.

Reader, you already know how we start such questions. We break the question in 3 parts: Storage & Meaning, Direction and Travel & Solve.

Approach :
STORAGE & MEANING

It's fairly simple. We make an array for DP of the dimensions same as that of the gold mine i.e. n*m.

The meaning assigned to a single cell in this grid is that "if we would have started from this cell, what is the maximum amount of gold we could have collected".

DIRECTION

We always try to solve the question for a simpler and smaller problem via which we move on to the bigger problem.

We want you to meditate on the fact that if we had started from any cell of the "end" column ,then the maximum amount of gold we could have collected is the same as the amount of gold corresponding to the cell value in the input array (according to the "Meaning" we assigned to a single cell).

Why do you think it is so?

It's because we can only take a step in the right direction. In the end column, taking a step anywhere to the right isn't possible because the grid comes to an end after that.

Hence our smaller problem lies at the "end" column. So we move from right to the left direction while calculating the maximum amount.

img

Figure 2 is the DP array (drawn in green to differentiate from the input array).

TRAVERSE & SOLVE
img

Once we have all the maximum amounts for the "end" column, we try to calculate the maximum amount for the column before that. We first calculate it for 'A'.

A' has 2 options whether to go to the right i.e. '2' or right down i.e. '4'.Since, 4>2, then for maximum amount of gold, 'A' goes to 4. Hence we store the sum of the original value at the cell A i.e. 8 (refer Figure 1) and the value 4. Hence we store 8+4=12 at A.

We highly recommend you to watch "Path with Maximum Gold" to understand the traversal path better.

Let's now calculate it for the remaining rows of the column.

img

B. This cell has 3 options: 2, 4 and 6. Since 6 is the largest of them, therefore the value of cell B is 0+6=6.

C. This cell has 3 options: 4, 6 and 2. Since 6 is the largest of them, therefore the value of cell C is 4+6=10.

D. This cell has 3 options: 6, 2 and 4. Since 6 is the largest of them, therefore the value of cell D is 2+6=8.

E. This cell has 3 options: 2, 4 and 1. Since 4 is the largest of them, therefore the value of cell E is 2+4=6.

F. This cell has 2 options: 4 and 1. Since 4 is the largest of them, therefore the value of cell F is 5+4=9.

This way you can solve the maximum amount for all the columns.

We insist you on trying to find the maximum values at the rest of the cells yourself. The final DP array should look something like this:

img

Now that we have filled the entire grid, we look at the "start" column and think which cell of the "start" column would be wise to start our journey of collecting gold from? We obviously chose the cell with maximum value i.e. 33. Don't understand why?

Go and check the "meaning" of the grid again. "Each cell is assigned with the maximum amount of gold that would be collected if we start from that cell". Hence, 33 is the maximum value that could be traced out of all the paths if we started from that cell.

The required path for amount 33 would like this:

img

You must have got a little hang of dynamic programming questions by now , which is why we want you to first give writing the code a try yourself. It's okay if you fail. DP problems are made just to practice failing so that one day winning feels extra special.

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { Scanner scn=new Scanner(System.in); int n=scn.nextInt(); int m=scn.nextInt(); int[][] arr=new int[n][m]; for(int i=0;i< n;i++){ for(int j=0;j< m;j++){ //1 arr[i][j]=scn.nextInt(); } } int[][]dp=new int[n][m]; //2 for(int j=m-1;j>=0;j--){ //3 for(int i=n-1;i>=0;i--){ //4 if(j==m-1){ dp[i][j]=arr[i][j]; //5 } else if(i==0){ //6 dp[i][j]=arr[i][j]+Math.max(dp[i][j+1],dp[i+1][j+1]); } else if(i==n-1){ //7 dp[i][j]=arr[i][j]+Math.max(dp[i][j+1],dp[i-1][j+1]); } else{ //8 dp[i][j]=arr[i][j]+Math.max(dp[i][j+1],Math.max(dp[i+1][j+1], dp [i-1][j+1])); } } } int max=dp[0][0]; //9 for(int i=1;i< n;i++){ if(dp[i][0]>max) //10 max=dp[i][0]; } System.out.println(max); //11 } }
java; true";
CODE DISCUSSION
  1. Array arr[n][m] is taken as the input for dimensions n and m.
  2. We make a new array dp[n][m] with the same dimensions as arr where each cell stores the maximum amount of gold that would be collected if we start from that cell.
  3. Since we start from the last/ "end" column of the grid, therefore our loop runs from m-1 to 0th row.
  4. For every column, we start traversing from a row at the extremities hence the row iteration runs from n-1 to 0 row (or 0 to n-1).
  5. As we have already discussed in the "traversal" section, if we are at the "end" column then the maximum value at every cell in the DP array is the value of the input cell itself.
  6. If one is at the first row of a column then there isn't an option of going right up available. Hence, the value at the cell is the value of the input array added to the maximum of right and right down.
  7. If one is at the last row of a column then there isn't an option of going right down available. Hence, the value at the cell is the value of the input array added to the maximum of right up and right.
  8. If it is neither of the above 2 cases, then the value at the cell is the sum of the values of the input array and the maximum of right up, right and right down.
  9. Now that the dp grid is filled , we initialize a variable "max" with dp[0][0].
  10. For every row of the first column we compare "max" and if we find a value greater than "max", then it becomes our new max.
  11. We print the maximum amount of gold stored in this "max".
Analysis
Time Complexity :

O(n2)

This time complexity is quadratic because nested loops are used.

SPACE COMPLEXITY :

O(n2)

Since we use a 2D array for Dynamic Programming, therefore the space used is of complexity n2.

We encourage you to watch the video "Goldmine" for a clearer explanation of this problem.

With this we conclude our question "Goldmine". We'll bring you many such interesting questions as we move further along the lecture. So keep with us on this path of Dynamic Programming!

Dynamic Programming
2D Arrays
Author: Shreeya Gupta
 
Run
Id Name