---

0741. 摘樱桃

• 标签：数组、动态规划、矩阵
• 难度：困难

题目链接

• 0741. 摘樱桃 - 力扣

题目大意

描述：

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

说明：

• $n == grid.length$。
• $n == grid[i].length$。
• $1 \le n \le 50$。
• $grid[i][j]$ 为 $-1$、$0$ 或 $1$。
• $grid[0][0] != -1$。
• $grid[n - 1][n - 1] != -1$。

示例：

• 示例 1：

输入：grid = [[0,1,-1],[1,0,-1],[1,1,1]]
输出：5
解释：玩家从 (0, 0) 出发：向下、向下、向右、向右移动至 (2, 2) 。
在这一次行程中捡到 4 个樱桃，矩阵变成 [[0,1,-1],[0,0,-1],[0,0,0]] 。
然后，玩家向左、向上、向上、向左返回起点，再捡到 1 个樱桃。
总共捡到 5 个樱桃，这是最大可能值。

• 示例 2：

输入：grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
输出：0

解题思路

思路 1：动态规划

这道题的关键在于将「往返两次」转化为"两个人同时从起点出发到终点"。

问题转化：

• 一个人从 $(0, 0)$ 走到 $(n-1, n-1)$ 再返回，等价于两个人同时从 $(0, 0)$ 走到 $(n-1, n-1)$。
• 两个人同时走，每次都向右或向下移动一步。
• 如果两个人在同一位置，樱桃只能摘一次。

状态定义：

• 定义 $dp[k][i1][i2]$ 表示两个人都走了 $k$ 步，第一个人在第 $i1$ 行，第二个人在第 $i2$ 行时，能摘到的最多樱桃数。
• 由于 $i + j = k$，所以列数可以通过 $j = k - i$ 计算得出。

状态转移：

• 两个人可以从四个方向转移过来：$(i1-1, i2-1)$、$(i1-1, i2)$、$(i1, i2-1)$、$(i1, i2)$。
• 如果两个人在同一位置，樱桃只计算一次；否则计算两次。

思路 1：代码

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        # dp[k][i1][i2] 表示两个人都走了 k 步，第一个人在第 i1 行，第二个人在第 i2 行
        dp = [[[-1] * n for _ in range(n)] for _ in range(2 * n - 1)]
        dp[0][0][0] = grid[0][0]
        
        for k in range(1, 2 * n - 1):
            for i1 in range(max(0, k - n + 1), min(k + 1, n)):
                for i2 in range(max(0, k - n + 1), min(k + 1, n)):
                    j1, j2 = k - i1, k - i2
                    
                    # 如果当前位置有荆棘，跳过
                    if grid[i1][j1] == -1 or grid[i2][j2] == -1:
                        continue
                    
                    # 从四个方向转移
                    val = -1
                    for pi1 in range(i1 - 1, i1 + 1):
                        for pi2 in range(i2 - 1, i2 + 1):
                            if pi1 >= 0 and pi2 >= 0 and dp[k - 1][pi1][pi2] >= 0:
                                val = max(val, dp[k - 1][pi1][pi2])
                    
                    if val >= 0:
                        # 如果两个人在同一位置，樱桃只计算一次
                        if i1 == i2:
                            val += grid[i1][j1]
                        else:
                            val += grid[i1][j1] + grid[i2][j2]
                        dp[k][i1][i2] = val
        
        return max(0, dp[2 * n - 2][n - 1][n - 1])

思路 1：复杂度分析

• 时间复杂度：$O(n^3)$，其中 $n$ 是网格的边长。需要遍历 $O(n)$ 步，每步需要 $O(n^2)$ 的状态转移。
• 空间复杂度：$O(n^3)$。需要存储 $O(n^3)$ 个状态。