741. 摘樱桃
Powered by:NEFU AB-IN
Link
文章目录
- 741. 摘樱桃
- 题意
- 思路
- 代码
741. 摘樱桃
题意
给你一个 n x n 的网格 grid ，代表一块樱桃地，每个格子由以下三种数字的一种来表示：
0 表示这个格子是空的，所以你可以穿过它。
1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
-1 表示这个格子里有荆棘，挡着你的路。
请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数：
从位置 (0, 0) 出发，最后到达 (n - 1, n - 1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为 0 或者 1 的格子）；
当到达 (n - 1, n - 1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0 ）；
如果在 (0, 0) 和 (n - 1, n - 1) 之间不存在一条可经过的路径，则无法摘到任何一个樱桃。
思路
- 首先不能走一个来回，这样不方便定义状态，可以转换状态，当做两个人同时从起点走到终点
- 定义状态为两人从 (0,0) 出发，都走了 t 步，分别走到 (i 1 ,j) 和 (i 2,k)，可以得到的樱桃个数的最大值。
- 注意这里记忆化搜索的状态定义，不能说走到这个格子能获得的樱桃个数为状态，因为这只是这个状态集合中的一个数，如果定义为走到这个格子得到的樱桃个数的最大值，这才能代表这个集合，才是唯一的值
- 状态优化：定义 dfs(t,j,k) 表示两人从 (0,0) 出发，都走了 t 步，分别走到 (t−j,j) 和 (t−k,k)，可以得到的樱桃个数的最大值。因为t相当于一共走的步数
- 状态转移为两个人从左和上转移而来，所以四个状态过来，然后加上自己这个地方有没有樱桃
代码
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
@lru_cache(None)
def dfs(t: int, j: int, k: int) -> int:
if j < 0 or k < 0 or t < j or t < k or grid[t - j][j] < 0 or grid[t - k][k] < 0:
return -INF
if t == 0: # 此时 j = k = 0
return grid[0][0]
return max(dfs(t - 1, j, k), dfs(t - 1, j, k - 1), dfs(t - 1, j - 1, k), dfs(t - 1, j - 1, k - 1)) + grid[t - j][j] + (grid[t - k][k] if k != j else 0)
n = len(grid)
return max(dfs(n * 2 - 2, n - 1, n - 1), 0)