题目描述
思路解析
一句话答案：LeetCode 1463 摘樱桃 II：两机器人从顶行两角同步下行，求最大樱桃。DP 状态是两机器人的列对 (c1,c2)，逐行枚举 9 种落点、同格只算一次，时间 O(rows·cols²·9)、空间 O(cols²)。
摘樱桃 II 里两个机器人到底要干什么
给一张 rows 行 cols 列的网格 grid，坐标 (i,j)（行在前列在后，从 0 起）处有 grid[i][j] 颗樱桃。机器人 1 从 (0,0)、机器人 2 从 (0,cols−1) 出发走到最后一行，每步走下一行的左下、正下、右下之一，各收沿途樱桃，同格被两个同时踩到只算一次。求两条路合计最多收多少。
题面例子 grid=[[3,1,1],[2,5,1],[1,5,5],[2,1,1]] 答案 24。两条路互相牵制，没法分开各算。
两个机器人为什么不能各求各的最长路
让两个机器人各自求最长路再相加会错：同格只算一次把两条路绑死，各自最优常撞同一批高樱桃格，重合被算两遍、虚高。枚举所有走法配对更不行：每个机器人近 3^(rows−1) 条路，配对是平方级，用 O(...)（大 O 记号，规模变大时运算量怎么涨）记就是指数，跑不完。
状态为什么必须同时装下两个机器人的列
两机器人每步都往下移一行，所以两个永远停在同一行——正因如此，状态才只需装下两列 (c1,c2)、行号不进状态。局面只差各在哪列。用动态规划，状态 dp[c1][c2] 指两机器人分别在第 c1、c2 列时的最大樱桃。状态只两列，数为 cols²、非 cols。初始只有 dp[0][cols−1] = grid[0][0] + grid[0][cols−1]（cols 为 1 时同格只加一次）。
每步 9 种落点怎么转移，同格为什么只加一次
从局面 dp[c1][c2] 往下一行，两机器人各三方向（左下/正下/右下）、3×3=9 种落点，越界的丢掉。落点在第 nc1、nc2 列，收益 gain = grid[r][nc1]，nc1 ≠ nc2 时再加 grid[r][nc2]，同格 nc1 == nc2 只加一份。转移让 ndp[nc1][nc2] 取原值与 dp[c1][c2] + gain 的较大值；一行算完把 dp 换成 ndp 再往下。
拿题面 4 行 3 列，dp 怎么一行行填到 24
第 0 行 dp[0][2] = 3 + 1 = 4。第 1 行从 (0,2) 出发，机器人 1 落第 0 列收 2、机器人 2 落第 1 列收 5，共 7，dp[0][1] = 4 + 7 = 11。第 2 行两机器人各右移一列，收本行 5 和 5，dp[1][2] = 11 + 10 = 21。第 3 行各左移一列收 2 和 1，dp[0][1] = 21 + 3 = 24，扫末行取最大即 24。注意 dp[0][1] 第 1 行是 11、第 3 行成 24：不同行的同名格，滚动数组逐行覆盖，不是矛盾。
同格那份樱桃多加一次，24 为什么会算成更大
复杂度：每行 cols² 个局面各枚举 9 方向、共 rows 行，时间 O(rows·cols²·9)；滚动数组只存当前行，空间 O(cols²)。
同格忘去重、nc1 == nc2 时仍加两份，dp 会虚高偏大。走不到的局面初值要设成很小的负数（代码里 -10^9），设成 0 会被当合法起点、凭空冒樱桃。单列 cols == 1 时初始化也别加两份。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住三件事:状态是「两机器人的列对 (c1,c2)」、每行枚举 9 种落点组合取最大、两机器人同格时樱桃只加一次。下面逐帧套它。
总览 · 两个起点：这是 4 行 3 列的樱桃网格。机器人 1 在左上角 (0,0)、机器人 2 在右上角 (0,2);它们要同步逐行下移直到最后一行。下面把每一行的「两机器人列对」状态 dp 都算出来。
初始:第 0 行：机器人 1 站在 (0,0) 收 3 颗(紫),机器人 2 站在 (0,2) 收 1 颗(青)。它们分列两端、不同格,所以 dp[0][2] = 3 + 1 = 4,其余状态暂时都是「走不到」。
第 1 行 · 准备：两机器人在第 0 行,沿最优来到列对 (0,2),此时累计 4 颗。要往第 1 行走:各自先按左下、正下、右下枚举 3 个方向(共 9 种方向组合),越界的丢掉。机器人 1 的界内落点是列 0、1(2 个),机器人 2 的界内落点是列 1、2(2 个),所以本行实际有效组合 4 种,逐一算收益取最大。
第 1 行 · 机器人 1 选向：先看机器人 1:它在第 0 行的列 0(蓝),下一行能落到列 0 或 1(界内的方向,橙色高亮)。这些落点脚下分别能拿 2、5 颗樱桃。机器人 2 的来源格(列 2)也标成蓝,但它不是机器人 1 的落点。
第 1 行 · 机器人 2 选向：再看机器人 2:它在第 0 行的列 2(蓝),下一行能落到列 1 或 2(橙色高亮),脚下分别能拿 5、1 颗樱桃。机器人 1 的两个候选与机器人 2 的两个候选两两配对,就是要比较的 4 种落点组合。
第 1 行 · 算收益：其中最优的一组落点是列对 (0,1)。机器人 1 落 (1,0) 收 2,机器人 2 落 (1,1) 收 5,不同格、各算,本行收益 = 2 + 5 = 7。
第 1 行 · 对比：反例:若两机器人都挤到同一列 1,樱桃 5 只算一次,本行只收 5 颗,明显比分开落点的 7 颗少。所以仍按 9 个方向组合枚举、越界的跳过,界内有效的都要比一遍、取最大,绝不能让它们随便重合。
第 1 行 · 结算：dp[0][1] = 上一行 dp[0][2](4) + 本行收益 = 11。这是走到第 1 行、列对 (0,1) 能攒到的最多樱桃(蓝=已走定)。继续下一行。
第 2 行 · 准备：两机器人在第 1 行,沿最优来到列对 (0,1),此时累计 11 颗。要往第 2 行走:各自先按左下、正下、右下枚举 3 个方向(共 9 种方向组合),越界的丢掉。机器人 1 的界内落点是列 0、1(2 个),机器人 2 的界内落点是列 0、1、2(3 个),所以本行实际有效组合 6 种,逐一算收益取最大。
第 2 行 · 机器人 1 选向：先看机器人 1:它在第 1 行的列 0(蓝),下一行能落到列 0 或 1(界内的方向,橙色高亮)。这些落点脚下分别能拿 1、5 颗樱桃。机器人 2 的来源格(列 1)也标成蓝,但它不是机器人 1 的落点。
第 2 行 · 机器人 2 选向：再看机器人 2:它在第 1 行的列 1(蓝),下一行能落到列 0 或 1 或 2(橙色高亮),脚下分别能拿 1、5、5 颗樱桃。机器人 1 的两个候选与机器人 2 的三个候选两两配对,就是要比较的 6 种落点组合。
第 2 行 · 算收益：其中最优的一组落点是列对 (1,2)。机器人 1 落 (2,1) 收 5,机器人 2 落 (2,2) 收 5,不同格、各算,本行收益 = 5 + 5 = 10。
第 2 行 · 结算：dp[1][2] = 上一行 dp[0][1](11) + 本行收益 = 21。这是走到第 2 行、列对 (1,2) 能攒到的最多樱桃(蓝=已走定)。继续下一行。
第 3 行 · 准备：两机器人在第 2 行,沿最优来到列对 (1,2),此时累计 21 颗。要往第 3 行走:各自先按左下、正下、右下枚举 3 个方向(共 9 种方向组合),越界的丢掉。机器人 1 的界内落点是列 0、1、2(3 个),机器人 2 的界内落点是列 1、2(2 个),所以本行实际有效组合 6 种,逐一算收益取最大。
第 3 行 · 机器人 1 选向：先看机器人 1:它在第 2 行的列 1(蓝),下一行能落到列 0 或 1 或 2(界内的方向,橙色高亮)。这些落点脚下分别能拿 2、1、1 颗樱桃。机器人 2 的来源格(列 2)也标成蓝,但它不是机器人 1 的落点。
第 3 行 · 机器人 2 选向：再看机器人 2:它在第 2 行的列 2(蓝),下一行能落到列 1 或 2(橙色高亮),脚下分别能拿 1、1 颗樱桃。机器人 1 的三个候选与机器人 2 的两个候选两两配对,就是要比较的 6 种落点组合。
第 3 行 · 算收益：其中最优的一组落点是列对 (0,1)。机器人 1 落 (3,0) 收 2,机器人 2 落 (3,1) 收 1,不同格、各算,本行收益 = 2 + 1 = 3。
第 3 行 · 结算：dp[0][1] = 上一行 dp[1][2](21) + 本行收益 = 24。这是走到第 3 行、列对 (0,1) 能攒到的最多樱桃(蓝=已走定)。到这里已经到达最后一行,下一步扫最后一行所有 dp 取最大。
收官:扫最后一行：走到最后一行,扫一遍所有 dp[c1][c2] 取最大,得到 dp[0][1] = 24,就是两机器人合计能收的最多樱桃。
回放:两条最优路径：绿色就是两机器人各自的最优路线。机器人 1:(0,0)→(1,0)→(2,1)→(3,0);机器人 2:(0,2)→(1,1)→(2,2)→(3,1)。一路收集、同格只算一次,合计 24 颗。这就是答案。
边界:单列被迫同格收一遍;两行一步到底;0 樱桃格照常处理。
两点延伸:同步逐行是「同一行」保证的;扩到 k 个机器人是 cols^k 状态。
参考代码
from typing import Listclass Solution: def cherryPickup(self, grid: List[List[int]]) -> int: rows, cols = len(grid), len(grid[0]) dp = [[-10**9] * cols for _ in range(cols)] dp[0][cols - 1] = grid[0][0] + (grid[0][cols - 1] if cols > 1 else 0) for r in range(1, rows): ndp = [[-10**9] * cols for _ in range(cols)] for c1 in range(cols): for c2 in range(cols): if dp[c1][c2] < 0: continue for d1 in (-1, 0, 1): for d2 in (-1, 0, 1): nc1, nc2 = c1 + d1, c2 + d2 if 0 <= nc1 < cols and 0 <= nc2 < cols: gain = grid[r][nc1] + (grid[r][nc2] if nc1 != nc2 else 0) ndp[nc1][nc2] = max(ndp[nc1][nc2], dp[c1][c2] + gain) dp = ndp return max(max(row) for row in dp)复杂度
- 时间：O(rows · cols² · 9)，每行枚举两机器人的列对 (c1,c2) 共 cols² 个状态,每个状态再枚举 9 种方向组合;乘以 rows 行
- 空间：O(cols²)，用滚动数组只存当前行的 dp[c1][c2],两机器人列对共 cols² 个状态;若不滚动则是 O(rows · cols²)
易错点
面试追问把动画讲成自己的话
追问为什么可以让两个机器人「同步逐行」走,而不用管它们各自的步数节奏?
追问如果机器人数量变成 3 个,这套方法还能用吗?复杂度怎么变?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题