摘樱桃 II

难度: Hard

给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。

你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。

请你按照如下规则，返回两个机器人能收集的最多樱桃数目：

从格子 (i,j) 出发，机器人可以移动到格子 (i+1, j-1)，(i+1, j) 或者 (i+1, j+1) 。
当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。
当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。
两个机器人在任意时刻都不能移动到 grid 外面。
两个机器人最后都要到达 grid 最底下一行。

示例 1：

输入：grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
输出：24
解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (3 + 2 + 5 + 2) = 12 。
机器人 2 摘的樱桃数目为 (1 + 5 + 5 + 1) = 12 。
樱桃总数为： 12 + 12 = 24 。

示例 2：

输入：grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
输出：28
解释：机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。
机器人 1 摘的樱桃数目为 (1 + 9 + 5 + 2) = 17 。
机器人 2 摘的樱桃数目为 (1 + 3 + 4 + 3) = 11 。
樱桃总数为： 17 + 11 = 28 。

示例 3：

输入：grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
输出：22

示例 4：

输入：grid = [[1,1],[1,1]]
输出：4

提示：

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100

Submission

运行时间: 358 ms

内存: 16.5 MB

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        dp = [[0] * (n + 2) for _ in range(n + 2)]
        dp2 = [[0] * (n + 2) for _ in range(n + 2)]
        dp[1][-2] = grid[0][0] + grid[0][-1]
        res = 0
        for row in range(1, m):
            for i in range(min(row + 1, n)):
                for j in range(max(i + 1, n - row - 1), n):
                    tmp = 0
                    for r1 in [-1, 0, 1]:
                        for r2 in [-1, 0, 1]:
                            tmp = max(tmp, dp[i + 1 + r1][j + 1 + r2])
                    dp2[i + 1][j + 1] = grid[row][i] + grid[row][j] + tmp
                    if row == m - 1 and res <dp2[i + 1][j + 1]:
                        res = dp2[i + 1][j + 1]
            dp, dp2 = dp2, dp
        return res

Explain

此题解采用动态规划的方法解决两个机器人同时从不同位置出发摘樱桃的问题。设dp[i][j]为机器人1在位置i、机器人2在位置j时能摘到的最多樱桃数量。因为机器人只能向下或对角线方向移动，所以我们需要从上一行的相关位置更新当前位置的最大值。由于两个机器人不能占据同一个格子，故在遍历时确保两个机器人不在同一列。循环遍历每一行，对于每个可能的机器人位置组合，计算可能的最大樱桃数，并根据上一行的状态转移而来。最终，最后一行中的最大值就是答案。

时间复杂度: O(m*n^2)

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

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        # 初始化DP表，扩展两行两列便于处理边界情况
        dp = [[0] * (n + 2) for _ in range(n + 2)]
        dp2 = [[0] * (n + 2) for _ in range(n + 2)]
        # 初始状态，两个机器人分别在左上角和右上角
        dp[1][-2] = grid[0][0] + grid[0][-1]
        res = 0
        # 遍历每一行
        for row in range(1, m):
            # 遍历可能的机器人1的位置
            for i in range(min(row + 1, n)):
                # 遍历可能的机器人2的位置，确保不在同一列
                for j in range(max(i + 1, n - row - 1), n):
                    tmp = 0
                    # 考虑来自上一行的所有可能位置
                    for r1 in [-1, 0, 1]:
                        for r2 in [-1, 0, 1]:
                            tmp = max(tmp, dp[i + 1 + r1][j + 1 + r2])
                    # 更新当前位置的最大樱桃数
                    dp2[i + 1][j + 1] = grid[row][i] + (grid[row][j] if i != j else 0) + tmp
                    # 更新最终结果
                    if row == m - 1 and res < dp2[i + 1][j + 1]:
                        res = dp2[i + 1][j + 1]
            # 交换dp和dp2，为下一行准备
            dp, dp2 = dp2, dp
        return res

Explore

在动态规划中，考虑上一行的9种可能状态是因为每个机器人可以向下移动或者向左下、右下对角线移动。因此，对于每个机器人位置组合(i, j)，必须考虑从(i-1, j-1)，(i-1, j)，(i-1, j+1)以及(j-1, i-1)，(j-1, i)，(j-1, i+1)等组合转移过来的情况。这样的状态转移设计确保了从任何可能的路径到达当前位置的最大樱桃数都被计算在内，从而确保不遗漏任何可能的路径。

初始化DP表时扩展两行两列主要是为了简化边界条件的处理。扩展的两行两列允许在进行状态转移时不需要额外检查数组越界的问题。例如，当机器人处于网格的边缘时，如果没有这两行两列的扩展，我们需要特别处理机器人向网格外移动的情况。通过扩展，我们可以保证即使在网格边缘也能按照同样的状态转移逻辑来更新DP表，从而简化代码并减少出错的可能。

在题解中，处理两个机器人同时到达同一个格子的情况通过确保他们不会在同一时间出现在同一列来实现。具体的实现逻辑是在更新DP表时，在内层循环中对机器人2的位置进行限制，使其始终大于机器人1的列位置。这样做可以避免两个机器人抵达同一格子，从而在计算樱桃总数时不会重复计算同一个格子上的樱桃。

题解中这样设置机器人1和机器人2的位置遍历范围是为了确保机器人只在有效的格子内移动，并且避免重复计算。机器人1的位置遍历范围`min(row + 1, n)`确保了机器人不会超出当前行的实际列数，并且随着行数增加，机器人可以访问的列数也相应增加，直到最多为n列。机器人2的位置从`max(i + 1, n - row - 1)`开始，确保了它始终在机器人1的右侧，同时也确保了在行数较少时不会超出列的界限。这样的设置帮助确保了遍历是高效和正确的。