# Cherry Pickup II
**Difficulty:** HARD
[External](https://leetcode.com/problems/cherry-pickup-ii)
Canonical: https://scaleengineer.com/dsa/problems/cherry-pickup-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Rubrik](https://scaleengineer.com/companies/rubrik)
---
## Problem
You are given a `rows x cols` matrix `grid` representing a field of cherries where `grid[i][j]` represents the number of cherries that you can collect from the `(i, j)` cell.

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)`.

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 passes through a cell, It picks up all cherries, and the cell becomes an empty cell.
* When both robots stay in the same cell, only one takes the cherries.
* Both robots cannot move outside of the grid at any moment.
* Both robots should reach the bottom row in `grid`.

**Example 1:**

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

**Input:** grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
**Output:** 24
**Explanation:** Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.

**Example 2:**

![](https://assets.glich.co/dsa/cherry-pickup-ii/image1.png) 

**Input:** grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
**Output:** 28
**Explanation:** Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

**Constraints:**

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

# Approaches
## Brute-Force Recursion
This approach directly translates the problem's state transitions into a recursive function. The state is defined by the current row and the column positions of the two robots. Since both robots move down one row at a time, they are always in the same row.
**Time:** O(9^rows). At each row, the function branches into 9 recursive calls. The depth of the recursion is `rows`, leading to an exponential number of calls. · **Space:** O(rows) for the recursion call stack.
**Pros:** Simple to understand and implement as it directly models the problem statement.
**Cons:** Extremely inefficient due to a massive number of redundant computations for the same subproblems.; Will result in a 'Time Limit Exceeded' error on any non-trivial input size.
### Explanation
We define a recursive function, say `solve(row, col1, col2)`, which calculates the maximum cherries that can be collected from the current `row` to the bottom, given robot 1 is at `(row, col1)` and robot 2 is at `(row, col2)`. The function works as follows:

- **Base Case:** When the robots reach the last row (`row == rows - 1`), they collect the cherries in their respective cells and the recursion stops. The value returned is `grid[row][col1] + grid[row][col2]` (or just `grid[row][col1]` if they are in the same cell).
- **Recursive Step:** For any other row, the function calculates the cherries collected at the current cells. Then, it explores all possible next moves for both robots. Robot 1 can move to `col1-1`, `col1`, or `col1+1` in the next row, and similarly for robot 2. This gives `3 * 3 = 9` possible combinations of next positions. The function recursively calls itself for each of these 9 combinations and takes the maximum result. This maximum is added to the cherries collected at the current row.
- **Boundary Checks:** The function must handle cases where a robot moves outside the grid boundaries. Such paths are invalid and should return a value that ensures they are not chosen (e.g., a very small negative number).
- The initial call to the function is `solve(0, 0, cols - 1)`.

```java
class Solution {
    public int cherryPickup(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        return solve(0, 0, cols - 1, grid);
    }

    private int solve(int row, int col1, int col2, int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        // Boundary checks for columns
        if (col1 < 0 || col1 >= cols || col2 < 0 || col2 >= cols) {
            return Integer.MIN_VALUE;
        }

        // Cherries at the current step
        int cherries = grid[row][col1];
        if (col1 != col2) {
            cherries += grid[row][col2];
        }

        // Base case: last row
        if (row == rows - 1) {
            return cherries;
        }

        // Recursive step: explore all 9 possible next moves
        int maxFutureCherries = 0;
        for (int dc1 = -1; dc1 <= 1; dc1++) {
            for (int dc2 = -1; dc2 <= 1; dc2++) {
                maxFutureCherries = Math.max(maxFutureCherries, solve(row + 1, col1 + dc1, col2 + dc2, grid));
            }
        }

        return cherries + maxFutureCherries;
    }
}
```
### Algorithm
- Define a recursive function `solve(row, col1, col2)` that returns the maximum cherries collected from the current `row` downwards, with robots at `(row, col1)` and `(row, col2)`.
- **Base Case:** If `row` is the last row, return the cherries at the robots' positions. If `col1` or `col2` are out of bounds, return a very small number to signify an invalid path.
- **Recursive Step:** For the current state `(row, col1, col2)`, calculate the cherries collected at this step. Then, explore all 9 possible next positions (`col1 + d1`, `col2 + d2` where `d1, d2` are in `{-1, 0, 1}`) in the next row by making recursive calls. 
- The result for the current state is the sum of current cherries and the maximum value returned from the 9 recursive calls.
- The initial call is `solve(0, 0, cols - 1)`.

## Dynamic Programming with Memoization (Top-Down)
The brute-force recursive approach suffers from re-calculating the same subproblems multiple times. A subproblem is defined by the state `(row, col1, col2)`. We can optimize this by storing the result of each subproblem in a memoization table (a 3D array) the first time it's computed. Subsequent calls for the same state will simply return the stored result.
**Time:** O(rows * cols * cols). Each state `(row, col1, col2)` is computed exactly once. The computation for each state involves a constant number of operations (a loop of 9). · **Space:** O(rows * cols * cols). This is dominated by the space required for the memoization table. The recursion stack depth adds O(rows).
**Pros:** Drastically more efficient than brute-force and guaranteed to solve the problem within time limits.; Often more intuitive to write than the bottom-up tabulation approach.
**Cons:** Uses significant space for the 3D memoization table.; Recursion overhead can make it slightly slower than an equivalent iterative (tabulation) solution.
### Explanation
This approach enhances the brute-force recursion by adding a cache, or memoization table, to store the results of subproblems. This is a top-down dynamic programming technique.

- We use a 3D array, `memo[rows][cols][cols]`, to store the results of our recursive function `solve(row, col1, col2)`.
- The `memo` array is initialized with a special value (e.g., `null` or -1) to indicate that a state has not yet been computed.
- Inside the recursive function, before any computation, we check if `memo[row][col1][col2]` already contains a valid result. If it does, we return it immediately.
- If the result is not in the memo table, we compute it as in the brute-force approach.
- Before returning the computed result, we store it in `memo[row][col1][col2]` for future use.
- This technique ensures that each unique state `(row, col1, col2)` is computed only once, dramatically improving performance.

```java
class Solution {
    public int cherryPickup(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        Integer[][][] memo = new Integer[rows][cols][cols];
        return solve(0, 0, cols - 1, grid, memo);
    }

    private int solve(int row, int col1, int col2, int[][] grid, Integer[][][] memo) {
        int rows = grid.length;
        int cols = grid[0].length;

        if (col1 < 0 || col1 >= cols || col2 < 0 || col2 >= cols) {
            return Integer.MIN_VALUE;
        }

        if (memo[row][col1][col2] != null) {
            return memo[row][col1][col2];
        }

        int cherries = grid[row][col1];
        if (col1 != col2) {
            cherries += grid[row][col2];
        }

        if (row == rows - 1) {
            return cherries;
        }

        int maxFutureCherries = 0;
        for (int dc1 = -1; dc1 <= 1; dc1++) {
            for (int dc2 = -1; dc2 <= 1; dc2++) {
                maxFutureCherries = Math.max(maxFutureCherries, solve(row + 1, col1 + dc1, col2 + dc2, grid, memo));
            }
        }

        memo[row][col1][col2] = cherries + maxFutureCherries;
        return memo[row][col1][col2];
    }
}
```
### Algorithm
- Create a 3D memoization array `memo[rows][cols][cols]` and initialize it with a value like -1 to indicate uncomputed states.
- Use the same recursive function `solve(row, col1, col2)` as in the brute-force approach.
- At the beginning of the function, check if `memo[row][col1][col2]` is already computed (i.e., not -1). If so, return the stored value immediately.
- If the state is not memoized, compute the result as before.
- Before returning the newly computed result, store it in `memo[row][col1][col2]` to avoid re-computation in the future.

## Tabulation with Space Optimization (Bottom-Up DP)
This is the most efficient approach. It builds the solution iteratively from the bottom up, which avoids recursion overhead. Furthermore, it optimizes the space complexity by recognizing that to compute the maximum cherries for a given row, we only need the results from the immediately following row.
**Time:** O(rows * cols * cols). We have a loop for rows, and nested loops for `c1`, `c2`, and the 9 possible moves. · **Space:** O(cols * cols). We only need space for two 2D arrays of size `cols x cols` to store the DP states for the current and next rows.
**Pros:** Most efficient in terms of both time and space.; Avoids recursion overhead, which can lead to a slight performance gain.; Uses significantly less memory than non-optimized DP approaches.
**Cons:** Can be less intuitive to formulate and implement compared to the top-down memoization approach.
### Explanation
This bottom-up DP approach, also known as tabulation, iteratively builds the solution. We can optimize space because the calculation for any row `r` only depends on the results from row `r+1`.

- We use a 2D table, `dp` of size `cols x cols`, to store the maximum cherries that can be collected from a given row to the end.
- **Initialization:** We start by populating `dp` as if it represents the last row (`rows - 1`). For each pair of columns `(c1, c2)`, `dp[c1][c2]` is initialized with `grid[rows-1][c1] + grid[rows-1][c2]` (or just `grid[rows-1][c1]` if `c1 == c2`).
- **Iteration:** We then iterate backward from the second to last row (`r = rows - 2`) up to the first row (`r = 0`). In each iteration, we compute a `current_dp` table for row `r`. For each pair of columns `(c1, c2)`, we find the maximum possible sum from the next row (`r+1`) by checking all 9 states reachable from `(c1, c2)`. The values for row `r+1` are already stored in our `dp` table. The result `current_dp[c1][c2]` is the sum of cherries at `(r, c1)` and `(r, c2)` plus this maximum value from the next row.
- After computing the `current_dp` table for row `r`, we update `dp = current_dp` to be used for the calculation of the previous row (`r-1`).
- **Final Result:** After the main loop completes, `dp` holds the results for row 0. The answer is `dp[0][cols - 1]`, corresponding to the robots' initial positions.

```java
class Solution {
    public int cherryPickup(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        int[][] dp = new int[cols][cols];

        // Initialize for the last row
        for (int c1 = 0; c1 < cols; c1++) {
            for (int c2 = 0; c2 < cols; c2++) {
                if (c1 == c2) {
                    dp[c1][c2] = grid[rows - 1][c1];
                } else {
                    dp[c1][c2] = grid[rows - 1][c1] + grid[rows - 1][c2];
                }
            }
        }

        // Iterate from the second to last row up to the first
        for (int r = rows - 2; r >= 0; r--) {
            int[][] current_dp = new int[cols][cols];
            for (int c1 = 0; c1 < cols; c1++) {
                for (int c2 = 0; c2 < cols; c2++) {
                    int maxNextRow = 0;
                    // Find max cherries from the next row
                    for (int dc1 = -1; dc1 <= 1; dc1++) {
                        for (int dc2 = -1; dc2 <= 1; dc2++) {
                            int nc1 = c1 + dc1;
                            int nc2 = c2 + dc2;
                            if (nc1 >= 0 && nc1 < cols && nc2 >= 0 && nc2 < cols) {
                                maxNextRow = Math.max(maxNextRow, dp[nc1][nc2]);
                            }
                        }
                    }
                    
                    int currentCherries = grid[r][c1];
                    if (c1 != c2) {
                        currentCherries += grid[r][c2];
                    }
                    current_dp[c1][c2] = currentCherries + maxNextRow;
                }
            }
            dp = current_dp;
        }

        return dp[0][cols - 1];
    }
}
```
### Algorithm
- Create a 2D DP array `dp[cols][cols]`.
- **Initialization:** Populate `dp` with the results for the last row (`rows - 1`). `dp[c1][c2]` will be the sum of cherries at `(rows-1, c1)` and `(rows-1, c2)`.
- **Iteration:** Loop `row` from `rows - 2` down to `0`.
  - Inside the loop, create a new 2D array `current_dp[cols][cols]`.
  - For each state `(row, c1, c2)`, calculate the maximum cherries from the next row by looking up the 9 possible next states in the `dp` table (which holds values for `row + 1`).
  - `current_dp[c1][c2] = (cherries at current cells) + (max value from dp)`. 
  - After the inner loops for `c1` and `c2` are done, replace the old `dp` table with `current_dp` (`dp = current_dp`).
- **Result:** After the main loop finishes, the answer is `dp[0][cols - 1]`.

# Solutions
### Java

```java
class Solution {
public
  int cherryPickup(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][][] f = new int[m][n][n];
    for (var g : f) {
      for (var h : g) {
        Arrays.fill(h, -1);
      }
    }
    f[0][0][n - 1] = grid[0][0] + grid[0][n - 1];
    for (int i = 1; i < m; ++i) {
      for (int j1 = 0; j1 < n; ++j1) {
        for (int j2 = 0; j2 < n; ++j2) {
          int x = grid[i][j1] + (j1 == j2 ? 0 : grid[i][j2]);
          for (int y1 = j1 - 1; y1 <= j1 + 1; ++y1) {
            for (int y2 = j2 - 1; y2 <= j2 + 1; ++y2) {
              if (y1 >= 0 && y1 < n && y2 >= 0 && y2 < n &&
                  f[i - 1][y1][y2] != -1) {
                f[i][j1][j2] = Math.max(f[i][j1][j2], f[i - 1][y1][y2] + x);
              }
            }
          }
        }
      }
    }
    int ans = 0;
    for (int j1 = 0; j1 < n; ++j1) {
      for (int j2 = 0; j2 < n; ++j2) {
        ans = Math.max(ans, f[m - 1][j1][j2]);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int cherryPickup(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int f[m][n][n];
    memset(f, -1, sizeof(f));
    f[0][0][n - 1] = grid[0][0] + grid[0][n - 1];
    for (int i = 1; i < m; ++i) {
      for (int j1 = 0; j1 < n; ++j1) {
        for (int j2 = 0; j2 < n; ++j2) {
          int x = grid[i][j1] + (j1 == j2 ? 0 : grid[i][j2]);
          for (int y1 = j1 - 1; y1 <= j1 + 1; ++y1) {
            for (int y2 = j2 - 1; y2 <= j2 + 1; ++y2) {
              if (y1 >= 0 && y1 < n && y2 >= 0 && y2 < n &&
                  f[i - 1][y1][y2] != -1) {
                f[i][j1][j2] = max(f[i][j1][j2], f[i - 1][y1][y2] + x);
              }
            }
          }
        }
      }
    }
    int ans = 0;
    for (int j1 = 0; j1 < n; ++j1) {
      for (int j2 = 0; j2 < n; ++j2) {
        ans = max(ans, f[m - 1][j1][j2]);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) f = [[[- 1] * n for _ in range(n)] for _ in range(m)] f[0][0][n - 1] = grid[0][0] + grid[0][n - 1] for i in range(1, m): for j1 in range(n): for j2 in range(n): x = grid[i][j1] + (0 if j1 == j2 else grid[i][j2]) for y1 in range(j1 - 1, j1 + 2): for y2 in range(j2 - 1, j2 + 2): if 0 <= y1 < n and 0 <= y2 < n and f[i - 1][y1][y2] != - 1: f[i][j1][j2] = max(f[i][j1][j2], f[i - 1][y1][y2] + x) return max(f[- 1][j1][j2] for j1, j2 in product(range(n), range(n)))

```