Cherry Pickup - Leetcode Solution

The Cherry Pickup problem on LeetCode is a dynamic programming problem that requires the efficient utilization of the resources available to find the maximum number of cherries that can be picked up by two people starting from the top-left corner of a grid and reaching the bottom-right corner without crossing each other's path.

The approach to solving this problem can be divided into two phases.

PHASE 1: Finding the maximum number of cherries that can be picked up by one person from the top-left corner to the bottom-right corner

In this phase, we start from the top-left corner and traverse the matrix in the downward and rightward directions to reach the bottom-right corner. While traversing the matrix, we keep a track of the number of cherries picked up so far and store this information in a matrix of equal size to the input matrix. This matrix will represent the maximum number of cherries that can be picked up by one person from the starting position to each cell in the matrix.

We can represent the matrix as a two-dimensional array, dp[i][j], where dp[i][j] represents the maximum number of cherries that can be picked up by one person starting from (0,0) and reaching (i,j).

For each cell (i,j), we calculate the maximum number of cherries that can be picked up by one person starting from (0,0) and reaching (i,j) based on the maximum number of cherries that can be picked up from the cells (i-1,j) and (i,j-1). The value of dp[i][j] is calculated as shown below:

dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])

The value of dp[i][j] represents the maximum number of cherries that can be picked up by one person starting from (0,0) and reaching (i,j).

PHASE 2: Finding the maximum number of cherries that can be picked up by two people from the top-left corner to the bottom-right corner

In this phase, we use the matrix created in the first phase to find the maximum number of cherries that can be picked up by two people starting from the top-left corner and reaching the bottom-right corner without crossing each other's path.

We can represent the two people as two points, (r1,c1) and (r2,c2), where (r1+c1) = (r2+c2). This condition ensures that both the people travel from the top-left corner to the bottom-right corner and never cross each other's paths.

We can define a three-dimensional array, dp[r1][c1][c2], where dp[r1][c1][c2] represents the maximum number of cherries that can be picked up by both people starting from (0,0) and reaching (r1,c1) and (r2,c2) respectively.

The value of dp[r1][c1][c2] can be calculated as:

dp[r1][c1][c2] = grid[r1][c1] + grid[r2][c2] + max(dp[r1-1][c1][c2], dp[r1][c1-1][c2], dp[r1][c1][c2-1], dp[r1-1][c1][c2-1], dp[r1][c1-1][c2-1], dp[r1-1][c1-1][c2], dp[r1-1][c1][c2-1], dp[r1][c1-1][c2-1])

The value of dp[r1][c1][c2] represents the maximum number of cherries that can be picked up by both people starting from (0,0) and reaching (r1,c1) and (r2,c2) respectively.

The time complexity of this approach is O(n^3), where n is the size of the input matrix.

The solution in Python is shown below.

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dp = [[0 for i in range(n)] for j in range(n)]
        dp[0][0] = grid[0][0]
        for i in range(1, n):
            dp[0][i] = dp[0][i-1] + grid[0][i]
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for i in range(1, n):
            for j in range(1, n):
                dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])
        ans = dp[n-1][n-1]
        dp = [[[-1 for i in range(n)] for j in range(n)] for k in range(n)]
        dp[0][0][0] = grid[0][0]
        for k in range(1, 2*n-1):
            for i in range(min(n, k+1)):
                for j in range(min(n, k+1)):
                    if i >= n or j >= n:
                        continue
                    if grid[i][k-i] == -1 or grid[j][k-j] == -1:
                        dp[i][j][k-i] = -1
                        continue
                    if i > 0:
                        if j > 0:
                            dp[i][j][k-i] = max(dp[i][j][k-i], dp[i-1][j-1][k-i] + grid[i][k-i] + grid[j][k-j])
                        if k-j > 0:
                            dp[i][j][k-i] = max(dp[i][j][k-i], dp[i-1][j][k-i-1] + grid[i][k-i] + grid[j][k-j])
                    if k-i > 0:
                        if j > 0:
                            dp[i][j][k-i] = max(dp[i][j][k-i], dp[i][j-1][k-i-1] + grid[i][k-i] + grid[j][k-j])
                        if k-j > 0:
                            dp[i][j][k-i] = max(dp[i][j][k-i], dp[i][j][k-i] = dp[i][j][k-i], dp[i][j-1][k-i] + grid[i][k-i] + grid[j][k-j])
        ans = max(ans, dp[n-1][n-1][n-1])
        return max(0, ans)

1