Leetcode 1463. Cherry Pickup II

Problem Explanation

In this problem, we are given a grid (2D array) where each element of the grid indicates the number of cherries in the respective cell. We have two robots operating on this grid: Robot #1 starting at the top-left corner, and Robot #2 starting at the top-right corner. The robots can move down to the adjacent cell, either straight (i+1,j), left (i+1, j-1), or right(i+1, j+1). Both robots must reach the bottom row. Our aim is to calculate the maximum number of cherries that can be collected by both the robots, following the given operating rules.

Walkthrough an Example

Consider the example, Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]. Robot #1 starts at the top left (cell with 3 cherries) and Robot #2 starts at the top-right (cell with 1 cherry). Both robots will choose paths that result in the maximum number of cherries. Robot #1 will follow path 3 (from cell with 3 cherries) -> 2 -> 5 -> 2 (collecting 12 cherries) and Robot #2 will follow path 1 -> 5 -> 5 -> 1 (collecting 12 cherries as well). So, the total number of cherries collected is 12+12 = 24.

Solution Approach

The problem boils down to choosing the optimal moves for each robot such that the combined total of cherries picked is maximized. This hints towards using dynamic programming as we need to keep track of the maximum cherries picked up for every possible state. The state can be defined by the position of both robots (i.e., the row where the robots currently are (x) and their respective columns (y1 for Robot 1 and y2 for Robot 2)).

We will use a 3D array dp[x][y1][y2] where dp[x][y1][y2] represents the maximum cherries we can collect with Robot#1 on cell (x, y1) and Robot#2 on cell (x, y2).

Both robots start from the top (i.e., x = 0) and must move down, so x will serve as our main parameter to check if we have considered all cells, if x == m (m is the number of rows in the grid), that means both robots have reached the bottom.

Below are the solutions in Python, Java, JavaScript, C++, and C#.

Python Solution

1
2python
3class Solution: 
4    def cherryPickup(self, grid: List[List[int]]) -> int:
5        m = len(grid)
6        n = len(grid[0])
7        dp = [[[-1]*n for _ in range(n)] for _ in range(m)]
8
9        def helper(x, y1, y2): 
10            if x==m: 
11                 return 0
12            if y1<0 or y1==n or y2<0 or y2==n: 
13                return 0
14            if dp[x][y1][y2] != -1: 
15                return dp[x][y1][y2]
16
17            ans = grid[x][y1] 
18            if y1 != y2: 
19                ans += grid[x][y2]
20            max_v = 0
21            for dx1 in range(-1, 2): 
22               for dx2 in range(-1, 2): 
23                   # moving both robots
24                   max_v = max(max_v, helper(x+1, y1+dx1, y2+dx2))
25            ans += max_v
26            dp[x][y1][y2] = ans 
27            return ans 
28        return helper(0, 0, n-1)

Java Solution

1
2java
3class Solution {
4  int m, n;
5  Integer[][][] dp;
6public int cherryPickup(int[][] grid) {
7    m = grid.length;
8    n = grid[0].length;
9    dp = new Integer[m][n][n];
10    return helper(grid, 0, 0, n - 1);
11}
12
13private int helper(int[][] grid, int x, int y1, int y2) {
14    if (x == m) return 0;
15    if (y1 < 0 || y1 >= n || y2 < 0 || y2 >= n) return Integer.MIN_VALUE;
16
17    if (dp[x][y1][y2] != null)
18        return dp[x][y1][y2];
19
20    int ans = grid[x][y1];
21    if (y1 != y2)
22        ans += grid[x][y2];
23    int max = 0;
24    for (int dx1 = -1; dx1 <= 1; dx1++)
25        for (int dx2 = -1; dx2 <= 1; dx2++)
26            max = Math.max(max, helper(grid, x + 1, y1 + dx1, y2 + dx2));
27    ans += max;
28    dp[x][y1][y2] = ans;
29    return ans;
30}
31}

JavaScript Solution

1
2javascript
3var cherryPickup = function(grid) {
4    let m = grid.length;
5    let n = grid[0].length;
6    let dp = new Array(m).fill(0).map(() => new Array(n).fill(0).map(() => new Array(n).fill(-1)));
7
8    return helper(0, 0, n - 1);
9    
10    function helper(x, y1, y2) {
11        if (x === m)
12            return 0;
13        if (y1 < 0 || y1 >= n || y2 < 0 || y2 >= n) 
14            return -Infinity;
15        if (dp[x][y1][y2] !== -1)
16            return dp[x][y1][y2];
17
18        let ans = grid[x][y1];
19        if (y1 !== y2)
20            ans += grid[x][y2];
21        let max = 0;
22        for (let dx1 = -1; dx1 <= 1; dx1++) {
23            for (let dx2 = -1; dx2 <= 1; dx2++) {
24                max = Math.max(max, helper(x + 1, y1 + dx1, y2 + dx2));
25            }
26        }
27        ans += max;
28        dp[x][y1][y2] = ans;
29        return ans;
30    }
31};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int dp[70][70][70] = {};
6    int cherryPickup(vector<vector<int>>& grid) {
7        memset(dp, -1, sizeof(dp));
8        int m = grid.size(), n = grid[0].size();
9        return max(0, helper(grid, m, n, 0, 0, n-1));
10    }
11    int helper(vector<vector<int>>& grid, int m, int n, int x, int y1, int y2) {
12        if (y1<0 || y1>=n || y2<0 || y2>=n) return INT_MIN;
13        else if (x == m) return 0;
14        else if (dp[x][y1][y2] != -1) return dp[x][y1][y2];
15        else
16        {
17            int ans = grid[x][y1] + (y1 != y2 ? grid[x][y2] : 0);
18            for (int i = -1; i <= 1; ++i)
19                for (int j = -1; j <= 1; ++j)
20                    ans = max(ans, helper(grid, m, n, x + 1, y1 + i, y2 + j) + grid[x][y1] + (y1 != y2 ? grid[x][y2] : 0));
21            dp[x][y1][y2] = ans;
22            return ans;
23        }
24    }
25};

C# Solution

1
2csharp
3public class Solution {
4    public int CherryPickup(int[][] grid) {
5        int m = grid.Length, n = grid[0].Length;
6        int[,,] dp = new int[71,71,71];
7        for(var i=0;i<71;i++)
8            for(var j=0;j<71;j++)
9                for(var k=0;k<71;k++)
10                    dp[i,j,k] = -1;
11        
12        return Math.Max(0, DFS(grid,dp,0,0,n-1));
13    }
14    
15    private int DFS(int[][] grid, int[,,] dp, int x, int y1, int y2){
16        if(x==grid.Length) return 0;
17        if(dp[x,y1,y2]!=-1) return dp[x,y1,y2];
18        int ans = grid[x][y1];
19        if(y1!=y2) ans+=grid[x][y2];
20        
21        for(int i=y1-1;i<=y1+1;i++){
22            if(i<0 || i>=grid[0].Length) continue;
23            for(int j=y2-1;j<=y2+1;j++){
24                if(j<0 || j>=grid[0].Length) continue;
25                
26                ans = Math.Max(ans, DFS(grid,dp,x+1,i,j) + grid[x][y1] + (y1==y2?0:grid[x][y2]));
27            }
28        }
29        
30        return dp[x,y1,y2] = ans;
31    }
32}

Ensure to leave an empty line between text and code blocks when writing in markdown syntax.To conclude, we have presented approaches to find an optimal solution for the "Cherry Pickup" problem. The idea is to think not in terms of a single robot's task, but rather taking the positions of both robots into consideration. We have used dynamic programming to solve this problem. The time complexity is O(n^3) as there would be nnn states and the total number of states would be the total size of the DP array.

In each solution, Python, Java, JavaScript, C++ and C#, we created a 3D DP array and defined a recursive function to simulate the steps of Robot #1 and Robot #2. We iterated over all the possible positions that the robots could be after one move. We used max function so that we always picked the path that yielded the most cherries.

These programs are a practical implementation of dynamic programming and can be a good exercise for anyone trying to understand and master this concept. Also, it can be a good starting point for creating more complex programs with more robots and larger grids or expanding the concept to 3D grids.

Challenging problems like these often appear in coding interviews, so mastering these solutions can be highly beneficial. The key to solving such problems is understanding the problem constraints, identifying the sub-problems and combining their solutions to obtain the result.