741. 摘樱桃

Powered by:NEFU AB-IN

Link

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) 之间不存在一条可经过的路径，则无法摘到任何一个樱桃。

思路

1. 首先不能走一个来回，这样不方便定义状态，可以转换状态，当做两个人同时从起点走到终点
2. 定义状态为两人从 (0,0) 出发，都走了 t 步，分别走到 (i 1 ,j) 和 (i 2,k)，可以得到的樱桃个数的最大值。
   1. 注意这里记忆化搜索的状态定义，不能说走到这个格子能获得的樱桃个数为状态，因为这只是这个状态集合中的一个数，如果定义为走到这个格子得到的樱桃个数的最大值，这才能代表这个集合，才是唯一的值
3. 状态优化：定义 dfs(t,j,k) 表示两人从 (0,0) 出发，都走了 t 步，分别走到 (t−j,j) 和 (t−k,k)，可以得到的樱桃个数的最大值。因为t相当于一共走的步数
4. 状态转移为两个人从左和上转移而来，所以四个状态过来，然后加上自己这个地方有没有樱桃

代码

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)