741. 摘樱桃
·168 words·1 min·
0
·
0
·
Author
Ryan
Table of Contents
问题分析 #
根据描述, 遍历的过程应该是先往右下再往左上.
如果是只往右下, 我们可以建立一个二维数组来记录到达每个位置的时候, 摘了多少樱桃. 对于该问题, 可以理解为是有2条路径, 同时从左上角开始走到右下角.
并且, 这2条路径在遍历的过程中, 应该经过的距离是相同的, 所以用dp[k][i1][i2]来记录, 此时一共遍历了第k步, 第一条路径行号为i1, 第二条行号为i2. 由于一共走了k步, 所以列号分别为j1=k-i1 和 j2=k-i2.
由于两条路径都只能往右下走, 所以第k步收获了多少和第k-1步的位置相关. k-1步时, 2条路径可能的位置是(i1, j1-1), (i1-1,j1-1), (i2-1, j2), (i2, j2-1).
于是有f[k][i1][i2] = max(f[k-1][i1][i2], f[k-1][i1-1][i2], f[k-1][i1][i2-1], f[k-1][i1-1][i2-1])
然后看第k步摘到了多少个樱桃. 如果第k步, 2条路径不在同一个位置也就是i1 != i2, 那么分别加上2个位置的樱桃数目, 否则加一个位置的就可以了.
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
N = len(grid)
f = [[[-inf] * (N+1) for _ in range(N+1) ]for _ in range(2 * N + 1)]
f[2][1][1] = grid[0][0]
for k in range(3, 2*N+1):# 在真实的网格上, 从左上到右下需要2N-1步, k的起始值为2
for i1 in range(1, N+1):
for i2 in range(1, N+1):
j1 = k - i1
j2 = k - i2
# 如果一直在同一行移动, 可能移动出界
if j1 <=0 or j1 > N or j2 <= 0 or j2 > N:
continue
A = grid[i1-1][j1-1]
B = grid[i2-1][j2-1]
if A == -1 or B == -1:
continue
f[k][i1][i2] = max(f[k-1][i1][i2], f[k-1][i1-1][i2], f[k-1][i1][i2-1], f[k-1][i1-1][i2-1]) + A
if i1 != i2: # 2个点不在同一个位置(樱桃数目可以叠加)
f[k][i1][i2] += B
return f[2 * N][N][N] if f[2 * N][N][N] > 0 else 0