# [LeetCode] 741. Cherry Pickup 捡樱桃

2021年09月15日 阅读数：1

In a N x N `grid` representing a field of cherries, each cell is one of three possible integers. html

• 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:java

• 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:python

```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:post

• `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 and grid[N-1][N-1] are not -1.

64. Minimum Path Sum 相似，但这个题还要返回到起点，并且捡过的位置由1变为0，若是分别计算去时和回来时的路径，就要把捡过的变为0，会很麻烦。ui

Java:code

```public int cherryPickup(int[][] grid) {
int N = grid.length, M = (N << 1) - 1;
int[][] dp = new int[N][N];
dp = grid;

for (int n = 1; n < M; n++) {
for (int i = N - 1; i >= 0; i--) {
for (int p = N - 1; p >= 0; p--) {
int j = n - i, q = n - p;

if (j < 0 || j >= N || q < 0 || q >= N || grid[i][j] < 0 || grid[p][q] < 0) {
dp[i][p] = -1;
continue;
}

if (i > 0) dp[i][p] = Math.max(dp[i][p], dp[i - 1][p]);
if (p > 0) dp[i][p] = Math.max(dp[i][p], dp[i][p - 1]);
if (i > 0 && p > 0) dp[i][p] = Math.max(dp[i][p], dp[i - 1][p - 1]);

if (dp[i][p] >= 0) dp[i][p] += grid[i][j] + (i != p ? grid[p][q] : 0)
}
}
}

return Math.max(dp[N - 1][N - 1], 0);
}
```

Python:htm

```class Solution(object):
def cherryPickup(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
# dp holds the max # of cherries two k-length paths can pickup.
# The two k-length paths arrive at (i, k - i) and (j, k - j),
# respectively.
n = len(grid)
dp = [[-1 for _ in xrange(n)] for _ in xrange(n)]
dp = grid
max_len = 2 * (n-1)
directions = [(0, 0), (-1, 0), (0, -1), (-1, -1)]
for k in xrange(1, max_len+1):
for i in reversed(xrange(max(0, k-n+1), min(k+1, n))):  # 0 <= i < n, 0 <= k-i < n
for j in reversed(xrange(i, min(k+1, n))):          # i <= j < n, 0 <= k-j < n
if grid[i][k-i] == -1 or grid[j][k-j] == -1:
dp[i][j] = -1
continue
cnt = grid[i][k-i]
if i != j:
cnt += grid[j][k-j]
max_cnt = -1
for direction in directions:
ii, jj = i+direction, j+direction
if ii >= 0 and jj >= 0 and dp[ii][jj] >= 0:
max_cnt = max(max_cnt, dp[ii][jj]+cnt)
dp[i][j] = max_cnt
return max(dp[n-1][n-1], 0)　　```

Python:

```class Solution(object):
def cherryPickup(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if grid[-1][-1] == -1: return 0

# set up cache
self.grid = grid
self.memo = {}
self.N = len(grid)

return max(self.dp(0, 0, 0, 0), 0)

def dp(self, i1, j1, i2, j2):
if (i1, j1, i2, j2) in self.memo: return self.memo[(i1, j1, i2, j2)]

# end states: 1. out of grid 2. at the right bottom corner 3. hit a thorn
N = self.N
if i1 == N or j1 == N or i2 == N or j2 == N: return -1
if i1 == N-1 and j1 == N-1 and i2 == N-1 and j2 == N-1: return self.grid[-1][-1]
if self.grid[i1][j1] == -1 or self.grid[i2][j2] == -1: return -1

# now can take a step in two directions at each end, which amounts to 4 combinations in total
dd = self.dp(i1+1, j1, i2+1, j2)
dr = self.dp(i1+1, j1, i2, j2+1)
rd = self.dp(i1, j1+1, i2+1, j2)
rr = self.dp(i1, j1+1, i2, j2+1)
maxComb = max([dd, dr, rd, rr])

# find if there is a way to reach the end
if maxComb == -1:
out = -1
else:
# same cell, can only count this cell once
if i1 == i2 and j1 == j2:
out = maxComb + self.grid[i1][j1]
# different cell, can collect both
else:
out = maxComb + self.grid[i1][j1] + self.grid[i2][j2]

# cache result
self.memo[(i1, j1, i2, j2)] = out
return out　　　　```

C++:

```class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
int n = grid.size(), mx = 2 * n - 1;
vector<vector<int>> dp(n, vector<int>(n, -1));
dp = grid;
for (int k = 1; k < mx; ++k) {
for (int i = n - 1; i >= 0; --i) {
for (int p = n - 1; p >= 0; --p) {
int j = k - i, q = k - p;
if (j < 0 || j >= n || q < 0 || q >= n || grid[i][j] < 0 || grid[p][q] < 0) {
dp[i][p] = -1;
continue;
}
if (i > 0) dp[i][p] = max(dp[i][p], dp[i - 1][p]);
if (p > 0) dp[i][p] = max(dp[i][p], dp[i][p - 1]);
if (i > 0 && p > 0) dp[i][p] = max(dp[i][p], dp[i - 1][p - 1]);
if (dp[i][p] >= 0) dp[i][p] += grid[i][j] + (i != p ? grid[p][q] : 0);
}
}
}
return max(dp[n - 1][n - 1], 0);
}
};
```