题目描述
思路解析动画文字版
记住三件事:状态是「两机器人的列对 (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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题