16 Answer Key Exercises Dynamic Programming and Divide and Conquer

In this problem, we will assume that both robots will move to the next row at the same time so that they both stay in the same row. This will be the first preview to solve this problem.

As described in the problem statement, we can move in 3 directions (i+1, j-1) , (i+1, j) or (i+1, j+1). All in the next row but with a different column.

Since we have 3 directions for each robot, there are therefore in each row 9 (3 x 3) states that we can move towards. (3 states for the first robot and 3 states for the second robot so it's 3 x 3).

And as the hint says, we need to have a 4 row DP array. Since this is a 3-dimensional array, there will be a 2-dimensional array which will be n*n, i.e. no. of column * no. of column. Where the row will be defined by the position of the Robot1 column and the column will specify the position of the Robot2 column.

Initially, we know that robot1 is at position 0 and robot2 is at position column – 1, which is the last column.

We have to fill dp[0] i.e. 1st row and in this 1st row column position for robot will be (0, 2) because 0 means column position for robot1 and 2 means position column for robot2 in the grid.

When we fill the space we get the value 3 + 1 which is 4

Now we need to fill the 2nd row. And in the 2nd line also there will be an n*m matrix. If we take robot1's previous position as 0, we have 3 columns it can go into in the next row, i.e. col {-1, 0, 1}. As col1 is out of range, we discard this "-1" and keep only "0, 1"

And the same robot2 is in 2, we can either reach the col {1, 2, 3}. Since col3 is out of bounds, we discard "3" and keep only "1, 2"

Now when we create the combination of all the columns that robot1 and robot2 can be we get 4 values and when we fill it it will be:

So if we look for (0, 1) the value that returns will be grid[0][1] + grid[1][1] + prev. But for (1,1) it will be grid[1][1] + prev.

If we now talk about code. Let's take dp[row][column][column] our dynamic programming. At the beginning col1=0 and col2=column-1 (robot location).

We have the solution max=dp[0][col1][col2].

Here is the code to fill for each increasing value of dp[raw][][]

// now comes apart where we need to iterate over each row;
        for(int i = 1; i < row; i++){ // each row starting with 1
            // In this each row of dp, we need to excise our logic picking that particular column, as the starting position
            // we need to loop on all the columns precise in this row
            // as i told there will be n*m column
            for(int c1 = 0; c1 < collar; c1++){ 
                for(int c2 = 0; c2 < collar; c2++){
                    // now from every column we need to fill the cube; for all the combinations or all the cell we can reach; with respective robot1 & robot2
                    // now we need to 1st take the previous value, that we discussed
                    int prev = dp[i - 1][c1][c2]; 
                    yew(prev >= 0){ // if that the case, we need to perform our operation, if it is a -ve value it means that we haven't reach yet that particular cell. And above that's why we initialize the whole array with -1
                        // Now we need to iterate over all the combinations of column that c1 & c2 can be in. For that we had define a direction array at the top
                        for(int d1: direction){ // for c1 we have the direction "d1" and we iterate over it
                            col1 = d1 + c1; // and column1 will be d1 + c1
                            for(int d2: direction){ // for c2 we have the direction "d2" and we iterate over it
                                col2 = d2 + c2; // and column2 will be d2 + c2
                            // Now we need to check is the new col1 & col2 are in the range of 0 & col. And for that we need to create a new method, which will check is the new col1 & col2 are in the range
                                yew(inRange(col1, collar) && inRange(col2, collar)){
                                    dp[i][col1][col2] = Math.max(dp[i][col1][col2], prev+(col1 == col2 ? grid[i][col1] : (grid[i][col1] + grid[i][col2]))); // if the value are int this range, we need to update the col1 & col2 position in the i'th row
                                    max = Math.max(max, dp[i][col1][col2]); // we need to update the maximum at each step. Taking max of max value & also the new column that we have filled
                                }
                            }
                        }
                    }
                    
                }
            }
        }
        return max; //eturn max at the end

Let's call dp' the upward approach. Here's better optimized code using a top-down approach to the original problem.

dp[k][i][j] indicates if the two robots start from grid[k][i] and grid[k][j] the maximum total number of cherries they can finally pick up. Note that they can only move down.

After filling dp, the final answer is dp[0][0][COL_NUM – 1]

For the last grid line, we have dp[-1][i][j] = grid[-1][i] if i == j else grid[-1][i] + grid[-1][ j]. Note that if 2 robots stay in the same place, they can only pick up once.

For the other rows, we have to iterate over all the 3*3 direction combinations they can choose from in the next layer and find the maximum, because for each robot there are 3 directions they can move. 

We will therefore have the following code:

It's not very optimal. Here is a better optimized code in python (in 2D with a DFS approach):