摘樱桃

难度: Hard

给你一个 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：

输入：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

提示：

n == grid.length
n == grid[i].length
1 <= n <= 50
grid[i][j] 为 -1、0 或 1
grid[0][0] != -1
grid[n - 1][n - 1] != -1

Submission

运行时间: 204 ms

内存: 16.9 MB

from typing import List

class Solution: # 3 维 DP
    def cherryPickup(self, grid: List[List[int]]) -> int:
        if grid[0][0] == -1:
            return 0
        n = len(grid)
        k = 2*n-1
        dp = [[[0 for i in range(n)] for j in range(n)] for k in range(2)] # 三维 DP
        dp[0][0][0] = grid[0][0]
        for sum in range(1, k): # TO MODIFY
            flag = False
            now  = sum % 2
            last = (sum-1) % 2
            for x1 in range(n):
                if x1 > sum: # 越界
                    break
                y1 = sum - x1
                if y1 >= n:
                    continue
                
                if grid[x1][y1] == -1: # 如果当前点不能走
                    dp[sum%2][x1] = [-1]*n
                    # print(f"dp[{sum}][{x1}] = {dp[now][x1]}")
                    continue
                top  = grid[x1-1][y1] if x1>0 else -1
                left = grid[x1][y1-1] if y1>0 else -1
                if top == left == -1: # 走到当前点的两个 point 都是不能走的，那么也没法走到当前点
                    dp[now][x1] = [-1]*n
                    # print(f"dp[{sum}][{x1}] = {dp[now][x1]}")
                    continue
                # 否则遍历
                for x2 in range(n):
                    if x2 > sum:
                        break
                    y2 = sum - x2
                    if y2 >= n:
                        continue
                    if grid[x2][y2] == -1: # 当前点不能走
                        dp[now][x1][x2] = -1
                        continue
                    top2  = grid[x2-1][y2] if x2>0 else -1
                    left2 = grid[x2][y2-1] if y2>0 else -1
                    if top2 == left2 == -1:
                        dp[now][x1][x2] = -1
                        grid[x2][y2] = -1
                        continue
                    top1  = dp[last][x1-1][x2]   if (x1>0 and y2>0) else 0
                    left1 = dp[last][x1-1][x2-1] if (x1>0 and x2>0) else 0
                    top2  = dp[last][x1][x2-1]   if (y1>0 and x2>0) else 0
                    left2 = dp[last][x1][x2]     if (y1>0 and y2>0) else 0
                    dp[now][x1][x2] = max(left1, left2, top1, top2) + grid[x1][y1] + grid[x2][y2]
                    if x1 == x2:
                        dp[now][x1][x2] -= grid[x1][y1]
                flag = True # 能运行到这一步，说明存在点都可以走
            if not flag:
                return 0
        return dp[0][n-1][n-1] if dp[0][n-1][n-1]!=-1 else 0

Explain

本题解使用三维动态规划（DP）的方式解决问题。解决的主要策略是同时考虑从(0,0)到(n-1,n-1)的前进路径和从(n-1,n-1)返回到(0,0)的返回路径。这里的关键在于，任何时间点上的两条路径所在的网格之和应该相等。我们使用dp数组，其中dp[t][x1][x2]表示在时间步t，第一条路径在点(x1, t-x1)和第二条路径在点(x2, t-x2)时可以摘到的最大樱桃数。动态规划的转移方程考虑了从左边或上边转移到当前点的所有可能性，同时考虑两个路径可能在同一个点重合的情况。如果两条路径在同一点相遇，则该点的樱桃只计算一次。如果某一步没有有效的移动方式，则直接返回0，表示无法完成任务。

时间复杂度: O(n^3)

空间复杂度: O(n^2)

from typing import List

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        if grid[0][0] == -1:
            return 0
        n = len(grid)
        k = 2*n-1
        dp = [[[0 for i in range(n)] for j in range(n)] for k in range(2)] # 三维 DP, 滚动数组
        dp[0][0][0] = grid[0][0]
        for sum in range(1, k):
            flag = False
            now  = sum % 2
            last = (sum-1) % 2
            for x1 in range(min(sum+1, n)):
                y1 = sum - x1
                if y1 >= n or grid[x1][y1] == -1:
                    continue
                for x2 in range(min(sum+1, n)):
                    y2 = sum - x2
                    if y2 >= n or grid[x2][y2] == -1:
                        continue
                    choices = [
                        dp[last][x1-1][x2] if x1>0 else -1,
                        dp[last][x1][x2-1] if x2>0 else -1,
                        dp[last][x1-1][x2-1] if x1>0 and x2>0 else -1,
                        dp[last][x1][x2] if x1>0 and x2>0 else -1
                    ]
                    best_prev = max([x for x in choices if x != -1], default=-1)
                    if best_prev == -1:
                        continue
                    cherries = grid[x1][y1] + (grid[x2][y2] if x1 != x2 else 0)
                    dp[now][x1][x2] = best_prev + cherries
            if not any(any(dp[now][x][y] != -1 for y in range(n)) for x in range(n)):
                return 0
        return max(dp[now][n-1][n-1], 0) # 确保返回非负值

Explore

这个问题涉及两条路径同时在一个网格中行走并尽可能多地摘樱桃。使用三维动态规划可以有效处理这种情况，因为它能同时跟踪两条路径的状态并计算最大樱桃数。三维DP通过时间步`t`和两条路径的位置`x1`和`x2`来表示状态，能够考虑两条路径的相互作用，如重合和同时选择最优路径。其他算法，如贪心或二维DP，无法有效处理两条路径可能的交互和重叠，可能导致无法找到全局最优解。

如果两条路径在同一点相遇而计算两次樱桃数，则会导致樱桃的重复计算，这不符合题目要求的实际情况。实际上，当两个人同时到达同一个格子时，只能摘取一次樱桃。因此，在DP转移方程中，如果`x1`与`x2`相等（即两路径在同一个点），则这个点的樱桃数只加一次，否则分别为两条路径添加各自位置的樱桃数。这样可以确保每个樱桃只被计算一次。

在算法实现中，对边界条件进行了特别处理。例如，当`x1`或`x2`为0时，我们只从可能的方向（即上方或左方）进行状态转移，而不是从不存在的格子转移，这通过条件判断如`if x1>0`来实现。同时，确保`y1`和`y2`（计算为`sum - x1`和`sum - x2`）不超过网格的边界，即不大于`n-1`。这些条件判断确保了引用的数组索引总是有效和存在的，从而避免了数组越界错误。

在动态规划中，初始化是非常重要的步骤，它定义了递推的起点。对于这个问题，`dp[0][0][0]`代表两条路径都从网格的左上角(0,0)开始，因此初始樱桃数为`grid[0][0]`。这是因为在开始时，两条路径都在起点只有一个可能的位置，且这是计算的起始状态。其他的`dp`值不需要初始化为具体的樱桃数，因为它们会在接下来的状态转移中被覆盖。仅初始化`dp[0][0][0]`是因为这是唯一已知的初始条件，其他状态依赖于从起点出发的状态转移。