What is the main DP strategy for Cherry Pickup II?

Use a 3D DP array DP[i][j][k] where i is the row, j and k are columns of robot1 and robot2, tracking maximum cherries collected from that state.

Why do we need to check overlapping cells?

If both robots occupy the same cell, counting cherries twice would overestimate the total; the DP must count such cells only once.

Can we reduce space complexity?

Yes, by using a rolling 2D DP for only the current and next row instead of storing the full 3D array for all rows.

How do we handle moves in DP transitions?

Consider all 3x3 combinations of next moves (down-left, down, down-right) for both robots to ensure all paths are explored.

What makes Cherry Pickup II challenging in interviews?

Managing two robots with overlapping positions requires careful state definition and transition logic, testing both DP and edge-case handling skills.

#1463

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

摘樱桃 II

给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。请你按照如下规则，返回两个机器人能收集的最多樱…

数组动态规划矩阵

题目描述

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

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j_1][j_2]$ 表示两个机器人分别在第 $i$ 行的位置 $j_1$ 和 $j_2$ 时能够摘到的最多樱桃数目。初始时 $f[0][0][n-1] = grid[0][0] + grid[0][n-1]$ ，其余值均为 $-1$ 。答案为 $\max_{0 \leq j_1, j_2 < n} f[m-1][j_1][j_2]$ 。

考虑 $f[i][j_1][j_2]$ ，如果 $j_1 \neq j_2$ ，那么机器人在第 $i$ 行能摘到的樱桃数目为 $grid[i][j_1] + grid[i][j_2]$ ；如果 $j_1 = j_2$ ，那么机器人在第 $i$ 行能摘到的樱桃数目为 $grid[i][j_1]$ 。我们可以枚举两个机器人的上一个状态 $f[i-1][y1][y2]$ ，其中 $y_1, y_2$ 分别是两个机器人在第 $i-1$ 行的位置，那么有 $y_1 \in \{j_1-1, j_1, j_1+1\}$ 且 $y_2 \in \{j_2-1, j_2, j_2+1\}$ 。状态转移方程如下：

f[i][j_1][j_2] = \max_{y_1 \in \{j_1-1, j_1, j_1+1\}, y_2 \in \{j_2-1, j_2, j_2+1\}} f[i-1][y_1][y_2] + \begin{cases} grid[i][j_1] + grid[i][j_2], & j_1 \neq j_2 \\ grid[i][j_1], & j_1 = j_2 \end{cases}

其中 $f[i-1][y_1][y_2]$ 为 $-1$ 时需要忽略。

最终的答案即为 $\max_{0 \leq j_1, j_2 < n} f[m-1][j_1][j_2]$ 。

时间复杂度 $O(m \times n^2)$ ，空间复杂度 $O(m \times n^2)$ 。其中 $m$ 和 $n$ 分别是网格的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        f = [[[-1] * n for _ in range(n)] for _ in range(m)]
        f[0][0][n - 1] = grid[0][0] + grid[0][n - 1]
        for i in range(1, m):
            for j1 in range(n):
                for j2 in range(n):
                    x = grid[i][j1] + (0 if j1 == j2 else grid[i][j2])
                    for y1 in range(j1 - 1, j1 + 2):
                        for y2 in range(j2 - 1, j2 + 2):
                            if 0 <= y1 < n and 0 <= y2 < n and f[i - 1][y1][y2] != -1:
                                f[i][j1][j2] = max(f[i][j1][j2], f[i - 1][y1][y2] + x)
        return max(f[-1][j1][j2] for j1, j2 in product(range(n), range(n)))

speed

复杂度分析

指标	值
时间	complexity is O(rows * cols^2 * 9) because for each row and pair of robot positions, there are 3x3 next moves. Space complexity is O(rows * cols^2) for the DP array. Optimizations can reduce it to O(cols^2) per row.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checking if you consider both robots simultaneously and handle overlapping cells.
question_mark
Watching if DP is defined correctly to avoid recomputation and ensure transitions cover all next moves.
question_mark
Observing whether you can reduce space from full 3D to 2D rolling array optimization.

warning

常见陷阱

外企场景

error
Counting cherries twice when both robots occupy the same cell.
error
Using a 2D DP ignoring the second robot's position, leading to incorrect totals.
error
Failing to iterate all 3x3 move combinations for the next row, missing optimal paths.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Single robot cherry pickup with only one path, simpler 2D DP suffices.
arrow_right_alt
Allow diagonal jumps longer than one cell, requiring extended DP transitions.
arrow_right_alt
Grid with obstacles where some cells cannot be visited, adding conditional checks in DP.

help

常见问题

外企场景

继续练习

#1444 切披萨的方案数 #1504 统计全 1 子矩形 #1349 参加考试的最大学生数