难度: Hard
原题连接
内容描述
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.
思路 1 - 时间复杂度: O(N^3)- 空间复杂度: O(N^3)******
可以看成两个人同时从(0, 0)出发到达(N-1, N-1)所能摘得的最多cherry，如果两个人到过同一个cherry点，注意要去重
记忆化搜索
beats 96.88%
class Solution:
def cherryPickup(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
N, cache = len(grid), {}
def dp(r1, c1, c2):
if (r1, c1, c2) in cache:
return cache[(r1, c1, c2)]
r2 = r1 + c1 - c2
if r1 >= N or r2 >= N or c1 >= N or c2 >= N or \
grid[r1][c1] == -1 or grid[r2][c2] == -1:
return -float('inf')
elif r1 == c1 == N - 1:
return grid[r1][c1]
else:
tmp = grid[r1][c1] + (c1 != c2) * grid[r2][c2]
tmp += max(dp(r1+1, c1, c2+1), dp(r1, c1+1, c2+1),
dp(r1+1, c1, c2), dp(r1, c1+1, c2))
cache[(r1, c1, c2)] = tmp
return tmp
return max(0, dp(0, 0, 0))思路 2 - 时间复杂度: O(N^3)- 空间复杂度: O(N^3)******
Bottom up
Assupmtion:
Go from (0, 0) -> (n-1, n-1) -> (0, 0) can be opt to two men go from (0, 0) -> (n-1, n-1) together, but when they go into
the same cell, the cur state can only be added 1 (use once)
Using DP to solve the problem:
1. dp[x1][y1][x2] to represent the largest ans we can get when first guy (marked as A) at(x1, y1) and second guy(marked as B) at (x2, x1 + y1 - x2)
* because we can only go right and down, so we have x1 + y1 = x2 + y2
2. Induction: every time we calculate the maximum of :
* dp[x1 - 1][y1][x2] : A down, B right
* dp[x1][y1 - 1][x2] : A right, B right
* dp[x1 - 1][y1][x2 - 1]: A down, B down
* dp[x1][y1 - 1][x2 - 1]: A right, B down
if the Max of these values is negative, then we don't have a path to this point
else we have: dp[x1][y1][x2] = Max + grid[x1 - 1][y1 - 1] + grid[x2 - 1][y2 - 1](if x1 != x2 && y1 != y2) else we
only add once.
3. Base case;
we use dp[][][]from 1 - n, so we have:
dp[1][1][1] = 1 and all other values are MIN_VALUE
4. Ans:
dp[n][n][n]
5. Direction:
from top left -> bottom right
6. Time:
O(n^3)
Space:
O(n^3)
摘自Java O(N^3) DP solution w/ specific explanation
beats 56.25%
class Solution:
def cherryPickup(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
N = len(grid)
dp = [[[-float('inf')] * (N+1) for i in range(N+1)] for j in range(N+1)]
dp[1][1][1] = grid[0][0]
for x1 in range(1, N+1):
for y1 in range(1, N+1):
for x2 in range(1, N+1):
if x1 == y1 == x2 == 1: # 初始值不能改变
continue
y2 = x1 + y1 - x2 # x1 + y1 = x2 + y2
# have already detected || out of boundary || cannot access
if dp[x1][y1][x2] > 0 or y2 < 1 or y2 > N or \
grid[x1-1][y1-1] == -1 or grid[x2-1][y2-1] == -1:
continue
cur = max(dp[x1-1][y1][x2], dp[x1-1][y1][x2-1],
dp[x1][y1-1][x2], dp[x1][y1-1][x2-1])
dp[x1][y1][x2] = cur + grid[x1 - 1][y1 - 1] + (x1 != x2) * grid[x2 - 1][y2 - 1]
return max(0, dp[-1][-1][-1])思路 3 - 时间复杂度: O(N^3)- 空间复杂度: O(N^2)******
压缩空间, 参考solution3
class Solution:
def cherryPickup(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
N = len(grid)
dp = [[float('-inf')] * N for _ in range(N)]
dp[0][0] = grid[0][0]
for t in range(1, 2 * (N-1) + 1):
dp2 = [[float('-inf')] * N for _ in range(N)]
for i in range(max(0, t-(N-1)), min(N-1, t) + 1): # r1 = t-c1, r2 = t-c2
for j in range(max(0, t-(N-1)), min(N-1, t) + 1):
if grid[i][t-i] == -1 or grid[j][t-j] == -1:
continue
val = grid[i][t-i] + (i != j) * grid[j][t-j]
dp2[i][j] = max(dp[pi][pj] + val
for pi in (i-1, i) for pj in (j-1, j)
if pi >= 0 and pj >= 0)
dp = dp2
return max(0, dp[N-1][N-1])