Solving Leetcode Hard Dynamic Programming Problem

LeetCode is a very popular Interview Preparation website with brilliant quality Data Structure and Algorithms question to prepare for your SDE/SWE interviews.

In this post, we will looking at a Hard-rated Dynamic Programming question from Leetcode, Cherry Pickup II, and how to determine if a given problem is Dynamic Programming problem or can it solved with a greedy approach.

Given a rows x cols matrix grid representing a field of cherries. Each cell in grid represents the number of cherries that you can collect.

You have two robots that can collect cherries for you, Robot #1 is located at the top-left corner (0,0) , and Robot #2 is located at the top-right corner (0, cols-1) of the grid.

Return the maximum number of cherries collection using both robots by following the rules below:

From a cell (i,j), robots can move to cell (i+1, j-1) , (i+1, j) or (i+1, j+1).

• When any robot is passing through a cell, It picks it up all cherries, and the cell becomes an empty cell (0).

• When both robots stay on the same cell, only one of them takes the cherries.

• Both robots cannot move outside of the grid at any moment.

• Both robots should reach the bottom row in the grid.

Constraints:

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100 

Now, moving towards thinking for an answer, the biggest hint we can get that this question requires dynamic programming is the line "return maximum number of cherries", which gives the clue that this is a optimization problem. Optimization problems require the maximization or minimization of the situation/problem at hand.

Though you may be tempted to ask me as to how we can be sure that this problem cannot be solved by another optimzation algorithm technique - Greedy as compared to dynamic programming.

In case you don't know, Greedy algorithm aims to find optimality by using local optimal (greedy approach) at each step in comparison to Dynamic Programming which aims to find global optimal in the given context.

Thinking of a simple example like this one can help you to clear your doubt:

If we were to choose local optimal cell at each step, we would keep choosing the cells with value 10 and both the robots will move down their respective rows without moving diagonally without reaching the cell with value 100, hence missing out on the most optimal solution.
Even the example 2 is indicative of the failure of the greedy method in the sense that if we were to choose local best cells robot1 would move down from its initial position to the cell with value 2 in second row instead of cell with value 0, but would not be able to reach cells with values 9 and 5 in row 3 and 4 respectively.

Thus, a good way to decide whether a problem requires greedy or DP, is to come up with a logic as to why a locally optimal method may or may not fail for the given situation.

Now coming towards thinking of a DP solution, the things that should be considered:

• Both the robots need to reach the bottom-most row and in each step they move down to next row, so we can move the robots at the time and it won't effect our answer.

• The constraints on the matrix size is low (70 each for dimension), hence even a O(n^3) solution is possible without giving time limit exceeds error.

• To prevent excess conditions and as well loss of generality, we shall consider that robot 1 will always be on the same cell on to the left of robot 2 throughout their moves. To move robot2 to the left of robot1 requires to robots to cross each other once either when they are on the same cell or on adjacent cells on the previous row before their current move. So instead of making robot2 cross robot1(my making robot1 move to down-right and robot2 down-left) we can make robot1 move down-left and robot2 down-right and keep them from crossing over. This will not affect our answer, and will conditions concise when writing the code.

Now, when computing the DP, our answer depends on 3 states/variables, our current row r, robot1 current column c1, and robot2 current column c2. So, our starting state is
dp[0][0][#cols - 1]

From any state dp[i][j][k], there are a maximum of nine types of moves (3 types of moves for each robot) possible as long as robots stay inside the matrix and don't cross each other and robot1 stays on left of robot2.

Now we have to write the standard DP to move from dp[0][0][#cols - 1] to the final row. Here's a Top-Down DP Solution in CPP.

class Solution {
public:
    int rows, cols;
    int cherryPickup(vector<vector<int>>& grid) {
        rows = (int)grid.size();
        cols = (int)grid[0].size();

        // initializing a 3D array dp
        vector<vector<vector<int>>> dp(rows, vector<vector<int>> (cols, vector<int>(cols, -1)));
        int ans = solve(dp, 0, 0, cols - 1, grid);
        return ans;
    }


    int solve(vector<vector<vector<int>>> &dp, int r, int c1, int c2, vector<vector<int>> &grid) {
        if(r >= rows) return 0;
        if(c1 < 0 or c2 < 0 or c1 >= cols or c2 >= cols or c1 > c2) return 0; 
        if(dp[r][c1][c2] != -1) return dp[r][c1][c2];

        int cur= grid[r][c1];
        if(c1 != c2) cur+= grid[r][c2];

        int mx = 0;
        mx = max({mx, solve(dp, r + 1, c1, c2, grid), 
solve(dp, r + 1, c1, c2 - 1, grid), solve(dp, r + 1, c1 + 1, c2 - 1, grid), 
solve(dp, r + 1, c1 + 1, c2, grid)});

        if(c1)
            mx= max({mx, solve(dp, r + 1, c1 - 1, c2, grid), 
solve(dp, r+1, c1-1, c2-1, grid)});

        if(c2 + 1 < cols)
            mx= max({mx, solve(dp, r + 1, c1, c2 + 1, grid), 
solve(dp, r + 1, c1 + 1, c2 + 1, grid)});

        if(c1 and c2 + 1 < cols)
            mx= max(mx, solve(dp, r + 1, c1 - 1, c2 + 1, grid));


        return dp[r][c1][c2] = mx + cur;
    }
};

Thanks for reading! If you liked this post, show some love and support with awesome reactions and comments.