LeetCode — Cherry Pickup II
Problem Link: https://leetcode.com/problems/cherry-pickup-ii/
Problem Description: Given a rows x cols matrix representing a field of cherries. Each cell in the 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.
Approach Used: Dynamic Programming
Explanation: At every instance, we will be moving downwards (next row) but horizontally we will have three options — left, centre, right. This scenario will be there for both robots. So total possible moves at each instance would be a total 3(moves for Robot 1) X 3(moves for Robot 2) i.e. 9 moves. We will check for al these 9 moves and pick the best one until we reach the last row and can’t move forward. Intuitively, this already looks like a recursion problem. To optimize the time complexity we can use a 3d matrix where dp[i][j][k] will denote when we are at the ith row and robot 1 is in the jth column and robot 2 is in the kth column.
Code: (Java)
public int cherryPickupUtil(int[][] grid, int m, int n, int i, int r1_j, int r2_j, int[][][] dp){
//if we have crossed the last row then no cherries can be collected (base case) if(i==m)
return 0; //checking if it is a valid case (both robots inside the grid)
if(r1_j<0 || r1_j>=n || r2_j<0 || r2_j>=n){
return Integer.MIN_VALUE;
} //if we have already encountered this case before
if(dp[i][r1_j][r2_j] != -1)
return dp[i][r1_j][r2_j]; //this will contain the final answer after all the recursive calls
int ans = Integer.MIN_VALUE; //total number of cherries collected from this row
int curr_value = grid[i][r1_j] + grid[i][r2_j]; //scenario where both robots land on the same (but only one can take the cherries)
if(r1_j == r2_j)
curr_value-=grid[i][r1_j]; //all possible 9 moves
ans = Math.max(ans, curr_value+cherryPickupUtil(grid, m, n, i+1, r1_j-1, r2_j-1, dp));
ans = Math.max(ans, curr_value+cherryPickupUtil(grid, m, n, i+1, r1_j-1, r2_j+1, dp));
ans = Math.max(ans, curr_value+cherryPickupUtil(grid, m, n, i+1, r1_j-1, r2_j, dp));
ans = Math.max(ans, curr_value+cherryPickupUtil(grid, m, n, i+1, r1_j, r2_j-1, dp));
ans = Math.max(ans, curr_value+cherryPickupUtil(grid, m, n, i+1, r1_j, r2_j, dp));
ans = Math.max(ans, curr_value+cherryPickupUtil(grid, m, n, i+1, r1_j, r2_j+1, dp));
ans = Math.max(ans, curr_value+cherryPickupUtil(grid, m, n, i+1, r1_j+1, r2_j-1, dp));
ans = Math.max(ans, curr_value+cherryPickupUtil(grid, m, n, i+1, r1_j+1, r2_j, dp));
ans = Math.max(ans, curr_value+cherryPickupUtil(grid, m, n, i+1, r1_j+1, r2_j+1, dp));//adding this to a dp matrix (so it can be used in future)
dp[i][r1_j][r2_j] = ans;
return dp[i][r1_j][r2_j];
}
public int cherryPickup(int[][] grid) { int[][][] dp = new int[grid.length][grid[0].length][grid[0].length]; for(int i=0; i<grid.length; i++){
for(int j=0;j<grid[0].length; j++){
Arrays.fill(dp[i][j], -1);
}
} return cherryPickupUtil(grid, grid.length, grid[0].length, 0,0, grid[0].length-1, dp);
}
Complexity:
Space complexity : O(m*n*n) . Since we used a 3d matrix to store the result of recursion.
Time complexity: O(m*n*n). Since we are going in each row once but in the worst case we could traverse all columns in all combination of robot 1 and robot 2.
Here m is the number of rows of the grid and n is the number of columns.
