> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/cherry-pickup.md).

# Cherry Pickup

In a 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;
* -1 means the cell contains a thorn that blocks your way.

Your task is to collect maximum number of cherries possible 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:**

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

**Note:**

* `grid` is an `N` by `N` 2D array, with `1 <= N <= 50`.
* Each `grid[i][j]` is an integer in the set `{-1, 0, 1}`.
* It is guaranteed that grid\[0]\[0] and grid\[N-1]\[N-1] are not -1.

```java
class Solution {
    // Take 2 persons starting from top-left together.
    // Now we can easily see that a state is defined by 4 variables:
    // R1, C1, R2, C2
    // But if they start from same position, we can say that they will be
    // at T manhattan distance from (0, 0).
    // The 2 points will follow this equation: R + C = T
    // Time Complexity -> O(N^3)
    // Space Complexity -> O(N^3)
    Integer[][][] dp;

    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        dp = new Integer[n][n][2 * n];
        int ans = helper(grid, 0, 0, 0);
        return ans == Integer.MIN_VALUE ? 0 : ans;
    }

    int[][] options = { { 1, 0 }, { 0, 1 }, { 0, 0 }, { 1, 1 } };

    public int helper(int[][] grid, int R1, int R2, int T) {
        int C1 = T - R1, C2 = T - R2, n = grid.length;
        if (C1 >= n || C2 >= n || R1 >= n || R2 >= n || grid[R1][C1] == -1 || grid[R2][C2] == -1)
            return Integer.MIN_VALUE;
        // At this point it is guaranteed, that both points will be at (n-1, n-1)
        if (R1 == n - 1 && C1 == n - 1)
            return grid[R1][C1];
        if (dp[R1][R2][T] != null)
            return dp[R1][R2][T];
        int ans = Integer.MIN_VALUE;
        for (int[] option : options)
            ans = Math.max(ans, helper(grid, R1 + option[0], R2 + option[1], T + 1));
        if (ans != Integer.MIN_VALUE) {
            ans += grid[R1][C1];
            if (R1 != R2 || C1 != C2)
                ans += grid[R2][C2];
        }
        dp[R1][R2][T] = ans;
        return ans;
    }
}
```