# Cherry Pickup
**Difficulty:** HARD
[External](https://leetcode.com/problems/cherry-pickup)
Canonical: https://scaleengineer.com/dsa/problems/cherry-pickup
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Cisco](https://scaleengineer.com/companies/cisco), [Flipkart](https://scaleengineer.com/companies/flipkart), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Snowflake](https://scaleengineer.com/companies/snowflake), [Zomato](https://scaleengineer.com/companies/zomato), [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
You are given an `n x n` `grid` representing a field of cherries, each cell is one of three possible integers.

* `0` means the cell is empty, so you can pass through,
* `1` means the cell contains a cherry that you can pick up and pass through, or
* `-1` means the cell contains a thorn that blocks your way.

Return _the maximum number of cherries you can collect by following the rules below_:

* Starting at the position `(0, 0)` and reaching `(n - 1, n - 1)` by moving right or down through valid path cells (cells with value `0` or `1`).
* After reaching `(n - 1, n - 1)`, returning to `(0, 0)` by moving left or up through valid path cells.
* When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell `0`.
* If there is no valid path between `(0, 0)` and `(n - 1, n - 1)`, then no cherries can be collected.

**Example 1:**

![](https://assets.glich.co/dsa/cherry-pickup/image0.jpg) 

**Input:** grid = [[0,1,-1],[1,0,-1],[1,1,1]]
**Output:** 5
**Explanation:** The player started at (0, 0) and went down, down, right right to reach (2, 2).
4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more cherry.
The total number of cherries picked up is 5, and this is the maximum possible.

**Example 2:**

**Input:** grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
**Output:** 0

**Constraints:**

* `n == grid.length`
* `n == grid[i].length`
* `1 <= n <= 50`
* `grid[i][j]` is `-1`, `0`, or `1`.
* `grid[0][0] != -1`
* `grid[n - 1][n - 1] != -1`

# Approaches
## Dynamic Programming with Memoization
A brute-force approach would explore all possible pairs of paths, which is computationally expensive. We can significantly optimize this by using dynamic programming with memoization. The core idea is to rephrase the problem as two people moving from `(0,0)` to `(n-1,n-1)` simultaneously. The state can be defined by the coordinates of both people. A crucial observation, `r1 + c1 = r2 + c2`, allows us to use a 3D state `(r1, c1, r2)` to represent the system. We use a 3D array to memoize the results of subproblems, avoiding redundant calculations.
**Time:** O(N^3). The number of states is N * N * N. Each state `(r1, c1, r2)` is computed once due to memoization. · **Space:** O(N^3), where N is the dimension of the grid. This is for the memoization table `memo[N][N][N]`.
**Pros:** Guaranteed to find the optimal solution.; Much more efficient than brute-force by avoiding recomputation of subproblems.; The recursive structure is often a direct translation of the problem's recurrence relation.
**Cons:** Requires O(N^3) space for the memoization table, which can be large for bigger N.; Recursive solutions might lead to stack overflow for very deep recursion, although not an issue with N <= 50.
### Explanation
This approach uses a top-down recursive method with a memoization table to store the results of subproblems. The state `(r1, c1, r2)` represents person 1 at `(r1, c1)` and person 2 at `(r2, c2)`, where `c2` is derived from `r1 + c1 - r2`. The function calculates the maximum cherries from this state to the end.

```java
class Solution {
    private int[][][] memo;
    private int[][] grid;
    private int n;

    public int cherryPickup(int[][] grid) {
        this.grid = grid;
        this.n = grid.length;
        // Using r1, c1, r2 as state. c2 is derived.
        this.memo = new int[n][n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // Initialize memo table with -1 to indicate not computed
                java.util.Arrays.fill(memo[i][j], -1);
            }
        }
        
        return Math.max(0, solve(0, 0, 0));
    }

    private int solve(int r1, int c1, int r2) {
        int c2 = r1 + c1 - r2;
        
        // Check if paths are valid
        if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
            return Integer.MIN_VALUE;
        }
        
        // Base case: reached destination
        if (r1 == n - 1 && c1 == n - 1) {
            return grid[r1][c1];
        }
        
        // Check memoization table
        if (memo[r1][c1][r2] != -1) {
            return memo[r1][c1][r2];
        }
        
        // Calculate cherries at current step
        int cherries = 0;
        if (r1 == r2 && c1 == c2) {
            cherries = grid[r1][c1];
        } else {
            cherries = grid[r1][c1] + grid[r2][c2];
        }
        
        // Explore 4 possible next moves
        int futureCherries = Math.max(
            Math.max(solve(r1 + 1, c1, r2 + 1),  // P1 down, P2 down
                     solve(r1 + 1, c1, r2)),     // P1 down, P2 right
            Math.max(solve(r1, c1 + 1, r2 + 1),  // P1 right, P2 down
                     solve(r1, c1 + 1, r2))      // P1 right, P2 right
        );
        
        // If no valid future path, current path is also invalid
        if (futureCherries == Integer.MIN_VALUE) {
            return memo[r1][c1][r2] = Integer.MIN_VALUE;
        }
        
        // Store and return result
        return memo[r1][c1][r2] = cherries + futureCherries;
    }
}
```
### Algorithm
- The problem of a round trip (down-right then up-left) can be modeled as two people starting at `(0, 0)` and moving to `(n-1, n-1)` simultaneously, only moving down or right.
- The state of the system can be defined by the coordinates of both people, `(r1, c1)` and `(r2, c2)`. A key observation is that after the same number of steps, their Manhattan distances from the origin are equal: `r1 + c1 = r2 + c2`. This allows us to reduce the state to three variables, for instance, `(r1, c1, r2)`, from which `c2` can be derived as `c2 = r1 + c1 - r2`.
- We define a recursive function `solve(r1, c1, r2)` that computes the maximum cherries that can be collected from the current positions `(r1, c1)` and `(r2, c2)` to the destination `(n-1, n-1)`.
- To avoid recomputing results for the same state, we use a 3D memoization table `memo[r1][c1][r2]`.
- The base case for the recursion is when both people reach the destination `(n-1, n-1)`. In this case, we return the value of `grid[n-1][n-1]`.
- If any person goes out of bounds or hits a thorn (`-1`), that path is invalid, and we return a very small number (e.g., `Integer.MIN_VALUE`) to prune this path.
- In each recursive step, we calculate the cherries collected at the current positions. If both people are on the same cell, the cherry is counted only once.
- We then make four recursive calls for the next possible combined moves: (down, down), (down, right), (right, down), and (right, right).
- The result for the current state is the sum of current cherries and the maximum value returned by the four recursive calls. This result is stored in the memoization table.
- The initial call is `solve(0, 0, 0)`. The final answer is `max(0, result)` because if no path exists, the function will return a negative value, but we should output 0.

## Space-Optimized Dynamic Programming
The previous DP approach has a space complexity of O(N^3). We can optimize this by noticing that the computation for the current step `k` only requires the results from the previous step `k-1`. This allows us to reduce the space complexity to O(N^2) by using only two 2D arrays to store the DP states for the current and previous steps. This bottom-up iterative approach has the same time complexity but is more memory-efficient.
**Time:** O(N^3). The outer loop for `k` runs `O(N)` times, and the two inner loops for `r1` and `r2` run `O(N)` times each, leading to `O(N*N*N)` operations. · **Space:** O(N^2). We use two N x N arrays to store the DP states for the current and previous steps.
**Pros:** Most optimal solution in terms of space complexity.; Avoids recursion overhead, which can lead to slightly better performance in practice.
**Cons:** The implementation can be more complex to reason about compared to the top-down recursive approach.; The logic for state transitions and boundary conditions needs careful handling.
### Explanation
We build the solution iteratively from the start `(0,0)` to the end `(n-1,n-1)`. Let `dp[r1][r2]` be the maximum cherries collected after `k` steps, with person 1 at row `r1` and person 2 at row `r2`. We iterate through the number of steps `k` and update the DP table.

```java
class Solution {
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int[][] dp = new int[n][n];
        for (int[] row : dp) {
            java.util.Arrays.fill(row, -1); // Use -1 to indicate unreachable states
        }
        dp[0][0] = grid[0][0];

        for (int k = 1; k <= 2 * n - 2; k++) {
            int[][] current_dp = new int[n][n];
            for (int[] row : current_dp) {
                java.util.Arrays.fill(row, -1);
            }

            for (int r1 = 0; r1 < n; r1++) {
                for (int r2 = 0; r2 < n; r2++) {
                    int c1 = k - r1;
                    int c2 = k - r2;

                    if (c1 < 0 || c1 >= n || c2 < 0 || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
                        continue;
                    }

                    int cherries = grid[r1][c1];
                    if (r1 != r2) { // If they are on different cells, add both cherries
                        cherries += grid[r2][c2];
                    }

                    // Find max cherries from previous step (k-1)
                    int prev_max = -1;
                    if (r1 > 0 && r2 > 0 && dp[r1 - 1][r2 - 1] != -1) prev_max = Math.max(prev_max, dp[r1 - 1][r2 - 1]);
                    if (r1 > 0 && dp[r1 - 1][r2] != -1) prev_max = Math.max(prev_max, dp[r1 - 1][r2]);
                    if (r2 > 0 && dp[r1][r2 - 1] != -1) prev_max = Math.max(prev_max, dp[r1][r2 - 1]);
                    if (dp[r1][r2] != -1) prev_max = Math.max(prev_max, dp[r1][r2]);
                    
                    if (prev_max != -1) {
                        current_dp[r1][r2] = cherries + prev_max;
                    }
                }
            }
            dp = current_dp;
        }

        return Math.max(0, dp[n - 1][n - 1]);
    }
}
```
### Algorithm
- This approach is the iterative, or bottom-up, version of the DP solution.
- We use the state `dp[k][r1][r2]` representing the maximum cherries after `k` steps, with person 1 at row `r1` and person 2 at row `r2`.
- We observe that the state at step `k` only depends on the state at step `k-1`. This allows for space optimization.
- We use two 2D arrays, `dp[n][n]` and `current_dp[n][n]`, to store the results for the previous step (`k-1`) and the current step (`k`), respectively.
- We iterate `k` from `1` to `2n-2`.
- In each iteration, we compute `current_dp` based on the values in `dp`.
- For each valid state `(k, r1, r2)`, we calculate the maximum cherries from the four possible previous states at `k-1`: `(k-1, r1-1, r2-1)`, `(k-1, r1-1, r2)`, `(k-1, r1, r2-1)`, and `(k-1, r1, r2)`.
- After iterating through all `r1` and `r2` for a given `k`, we replace `dp` with `current_dp` for the next iteration.
- The final answer is `max(0, dp[n-1][n-1])` after the loop finishes.

# Solutions
### Java

```java
class Solution {
public
  int cherryPickup(int[][] grid) {
    int n = grid.length;
    int[][][] dp = new int[n * 2][n][n];
    dp[0][0][0] = grid[0][0];
    for (int k = 1; k < n * 2 - 1; ++k) {
      for (int i1 = 0; i1 < n; ++i1) {
        for (int i2 = 0; i2 < n; ++i2) {
          int j1 = k - i1, j2 = k - i2;
          dp[k][i1][i2] = Integer.MIN_VALUE;
          if (j1 < 0 || j1 >= n || j2 < 0 || j2 >= n || grid[i1][j1] == -1 ||
              grid[i2][j2] == -1) {
            continue;
          }
          int t = grid[i1][j1];
          if (i1 != i2) {
            t += grid[i2][j2];
          }
          for (int x1 = i1 - 1; x1 <= i1; ++x1) {
            for (int x2 = i2 - 1; x2 <= i2; ++x2) {
              if (x1 >= 0 && x2 >= 0) {
                dp[k][i1][i2] = Math.max(dp[k][i1][i2], dp[k - 1][x1][x2] + t);
              }
            }
          }
        }
      }
    }
    return Math.max(0, dp[n * 2 - 2][n - 1][n - 1]);
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} grid * @return {number} */ var cherryPickup = function ( grid ) { const n = grid . length ; let dp = new Array ( n * 2 - 1 ); for ( let k = 0 ; k < dp . length ; ++ k ) { dp [ k ] = new Array ( n ); for ( let i = 0 ; i < n ; ++ i ) { dp [ k ][ i ] = new Array ( n ). fill ( - 1 e9 ); } } dp [ 0 ][ 0 ][ 0 ] = grid [ 0 ][ 0 ]; for ( let k = 1 ; k < n * 2 - 1 ; ++ k ) { for ( let i1 = 0 ; i1 < n ; ++ i1 ) { for ( let i2 = 0 ; i2 < n ; ++ i2 ) { const j1 = k - i1 , j2 = k - i2 ; if ( j1 < 0 || j1 >= n || j2 < 0 || j2 >= n || grid [ i1 ][ j1 ] == - 1 || grid [ i2 ][ j2 ] == - 1 ) { continue ; } let t = grid [ i1 ][ j1 ]; if ( i1 != i2 ) { t += grid [ i2 ][ j2 ]; } for ( let x1 = i1 - 1 ; x1 <= i1 ; ++ x1 ) { for ( let x2 = i2 - 1 ; x2 <= i2 ; ++ x2 ) { if ( x1 >= 0 && x2 >= 0 ) { dp [ k ][ i1 ][ i2 ] = Math . max ( dp [ k ][ i1 ][ i2 ], dp [ k - 1 ][ x1 ][ x2 ] + t ); } } } } } } return Math . max ( 0 , dp [ n * 2 - 2 ][ n - 1 ][ n - 1 ]); };

```

### CPP

```cpp
class Solution {
public:
  int cherryPickup(vector<vector<int>> &grid) {
    int n = grid.size();
    vector<vector<vector<int>>> dp(
        n << 1, vector<vector<int>>(n, vector<int>(n, -1e9)));
    dp[0][0][0] = grid[0][0];
    for (int k = 1; k < n * 2 - 1; ++k) {
      for (int i1 = 0; i1 < n; ++i1) {
        for (int i2 = 0; i2 < n; ++i2) {
          int j1 = k - i1, j2 = k - i2;
          if (j1 < 0 || j1 >= n || j2 < 0 || j2 >= n || grid[i1][j1] == -1 ||
              grid[i2][j2] == -1)
            continue;
          int t = grid[i1][j1];
          if (i1 != i2)
            t += grid[i2][j2];
          for (int x1 = i1 - 1; x1 <= i1; ++x1)
            for (int x2 = i2 - 1; x2 <= i2; ++x2)
              if (x1 >= 0 && x2 >= 0)
                dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][x1][x2] + t);
        }
      }
    }
    return max(0, dp[n * 2 - 2][n - 1][n - 1]);
  }
};

```

### Python

```python
class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int: n = len(grid) dp = [[[- inf] * n for _ in range(n)] for _ in range((n << 1) - 1)] dp[0][0][0] = grid[0][0] for k in range(1, (n << 1) - 1): for i1 in range(n): for i2 in range(n): j1, j2 = k - i1, k - i2 if (not 0 <= j1 < n or not 0 <= j2 < n or grid[i1][j1] == - 1 or grid[i2][j2] == - 1): continue t = grid[i1][j1] if i1 != i2: t += grid[i2][j2] for x1 in range(i1 - 1, i1 + 1): for x2 in range(i2 - 1, i2 + 1): if x1 >= 0 and x2 >= 0: dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][x1][x2] + t) return max(0, dp[- 1][- 1][- 1])

```