## Algorithm

Problem Name: 741. Cherry Pickup

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: ```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 != -1`
• `grid[n - 1][n - 1] != -1`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const cherryPickup = grid => {
const n = grid.length
const dp = [...new Array(n)].map(() =>
[...new Array(n)].map(() => Array(n).fill(-Infinity))
)
dp = grid
const go = (x1, y1, x2) => {
const y2 = x1 + y1 - x2
if (x1 < 0 || y1 < 0 || x2 < 0 || y2 < 0) return -1
if (grid[y1][x1] === -1 || grid[y2][x2] === -1) return -1
if (dp[y1][x1][x2] !== -Infinity) return dp[y1][x1][x2]
dp[y1][x1][x2] = Math.max(
go(x1 - 1, y1, x2 - 1),
go(x1, y1 - 1, x2),
go(x1, y1 - 1, x2 - 1),
go(x1 - 1, y1, x2)
)
if (dp[y1][x1][x2] >= 0) {
dp[y1][x1][x2] += grid[y1][x1]
if (x1 !== x2) dp[y1][x1][x2] += grid[y2][x2]
}
return dp[y1][x1][x2]
}
return Math.max(0, go(n - 1, n - 1, n - 1))
}
``````
Copy The Code &

Input

cmd
rid = [[0,1,-1],[1,0,-1],[1,1,1]]

Output

cmd
5

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution(object):
def cherryPickup(self, grid):
if grid[-1][-1] == -1: return 0
memo, n = {}, len(grid)
def dp(i1, j1, i2, j2):
if (i1, j1, i2, j2) in memo: return memo[(i1, j1, i2, j2)]
if n in (i1, j1, i2, j2) or -1 in (grid[i1][j1], grid[i2][j2]): return -1
if i1 == i2 == j1 == j2 == n - 1: return grid[-1][-1]
mx = max(dp(i1+1, j1, i2+1, j2), dp(i1+1, j1, i2, j2+1), dp(i1, j1+1, i2+1, j2), dp(i1, j1+1, i2, j2+1))
if mx == - 1: out = -1
elif i1 == i2 and j1 == j2: out = mx + grid[i1][j1]
else: out = mx + grid[i1][j1] + grid[i2][j2]
memo[(i1, j1, i2, j2)] = out
return out
return max(0, dp(0, 0, 0, 0))
``````
Copy The Code &

Input

cmd
rid = [[0,1,-1],[1,0,-1],[1,1,1]]

Output

cmd
5