多维动态规划实战：LeetCode 741 Cherry Pickup 五种解法，从指数级递归到 O(n²) 空间优化

多维动态规划实战LeetCode 741 Cherry Pickup 五种解法从指数级递归到 O(n²) 空间优化【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于本仓库 articles/cherry-pickup.md 中的完整解法链系统讲解 LeetCode 741「摘樱桃Cherry Pickup」这一经典高难度Hard动态规划题。你将掌握「往返路径等价于双人同时前进」的核心建模技巧、从指数递归到 O(n⁴)/O(n³)/O(n²) 的完整优化路径以及多语言Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust下的统一实现范式可直接迁移到 articles/cherry-pickup-ii.md 所对应的 1463「Cherry Pickup II」等姊妹题。问题背景与前置知识Cherry Pickup 的题面可以概括为在n × n的网格中单元格取值0空、1有一颗樱桃或-1荆棘不可通行。一个人从左上角(0, 0)出发只能向右或向下走到达右下角(n-1, n-1)时采摘途经的所有樱桃随后再从右下角返回左上角只能向左或向上走再次采摘途经樱桃。每个单元格的樱桃只能被采摘一次要求返回两趟能采摘的最大樱桃数。动手解题前原文档建议你熟悉以下三个前置技能动态规划Dynamic Programming——使用记忆化或填表法求解具有重叠子问题的优化问题多维 DPMulti-dimensional DP——用 3 维或 4 维状态同时追踪多个路径位置网格寻路Path Finding in Grids——理解二维矩阵中的移动约束与障碍处理。这些前置知识与本仓库其他 DP 文章如 articles/maximum-subarray.md、articles/minimum-path-sum.md一脉相承但本问题的独特之处在于状态需要同时描述两条路径。核心洞察一去一回等价于两人同往第一趟从左上到右下、第二趟从右下返回左上——如果直接按时间顺序模拟第二趟的最优解依赖于第一趟采摘后的网格状态贪心地先求第一趟最优是错误的方向详见后文「常见陷阱」。原文档给出的关键建模是由于网格是正方形、只允许右/下移动返回路径的每一个位置都可以与去程路径按「曼哈顿步数」对称映射。因此可以将问题等价地转化为两个人同时从(0, 0)出发都只向右或向下移动同时到达(n-1, n-1)。两人采摘的并集恰好等于一去一回实际能采摘的樱桃集合两人落在同一格时樱桃只计一次。两人每步各自都有「向右」或「向下」两种选择于是每一步共有2 × 2 4种移动组合。用四个变量(r1, c1)与(r2, c2)分别记录两人的位置即可穷举所有同步路径。解法一递归Recursion直觉不要思考一个人去再回来而是模拟两个人从左上角同时出发走向右下角。由于两条路径最终都必须到达终点我们用(r1, c1)和(r2, c2)追踪两人位置每一步枚举 4 种移动组合。两人落到同一格时只计一次樱桃避免重复计数。算法步骤定义递归函数dfs(r1, c1, r2, c2)返回当人 1 在(r1, c1)、人 2 在(r2, c2)时能收集的最大樱桃数。非法剪枝任一坐标越界或任一人落在荆棘-1上返回一个很大的负数如-1000使该路径作废。终点基例两人都到达(n-1, n-1)时返回该格樱桃值。尝试 4 种组合两人都向下、两人都向右、一人向下另一人向右、以及相反。累加两人当前位置的樱桃若(r1, c1) (r2, c2)减去一份避免重复。返回最大值若最终结果为负返回0表示不存在有效路径。代码实现Pythonclass Solution: def cherryPickup(self, grid: List[List[int]]) - int: n len(grid) def dfs(r1, c1, r2, c2): if r1 n or c1 n or r2 n or c2 n or grid[r1][c1] -1 or grid[r2][c2] -1: return -1000 if r1 n - 1 and r2 n - 1 and c1 n - 1 and c2 n - 1: return grid[r1][c1] res dfs(r1 1, c1, r2 1, c2) res max(res, dfs(r1 1, c1, r2, c2 1)) res max(res, dfs(r1, c1 1, r2 1, c2)) res max(res, dfs(r1, c1 1, r2, c2 1)) res grid[r1][c1] grid[r2][c2] res - (grid[r1][c1] if (r1 r2 and c1 c2) else 0) return res return max(0, dfs(0, 0, 0, 0))原文档为本题提供了Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 共 9 种语言的完整递归实现详见 articles/cherry-pickup.md各语言逻辑逐行等价。以 Java 为例只需把递归函数作为带grid与n参数的私有方法并用Math.max求四路最大值public class Solution { public int cherryPickup(int[][] grid) { int n grid.length; return Math.max(0, dfs(0, 0, 0, 0, grid, n)); } private int dfs(int r1, int c1, int r2, int c2, int[][] grid, int n) { if (r1 n || c1 n || r2 n || c2 n || grid[r1][c1] -1 || grid[r2][c2] -1) return -1000; if (r1 n - 1 c1 n - 1 r2 n - 1 c2 n - 1) return grid[r1][c1]; int res dfs(r1 1, c1, r2 1, c2, grid, n); res Math.max(res, dfs(r1 1, c1, r2, c2 1, grid, n)); res Math.max(res, dfs(r1, c1 1, r2 1, c2, grid, n)); res Math.max(res, dfs(r1, c1 1, r2, c2 1, grid, n)); res grid[r1][c1] grid[r2][c2]; if (r1 r2 c1 c2) res - grid[r1][c1]; return res; } }复杂度时间复杂度$O(16 ^ n)$——每一步产生 4 个分支路径长度为 $2n-1$指数爆炸空间复杂度$O(n)$为递归调用栈深度。$O(16^n)$ 在n稍大时完全不可行因此必须引入记忆化消除重叠子问题。解法二动态规划自顶向下Top-Down直觉递归解法存在大量重叠子问题同一组位置(r1, c1, r2, c2)可以通过不同路径到达。把每个状态的结果存入 4 维记忆化表即可避免重复计算把指数时间降为多项式时间。算法步骤创建 4 维 DP 数组初始化为负无穷用于标记已访问状态复用与解法一完全相同的dfs(r1, c1, r2, c2)计算前先查表若当前状态已被缓存直接返回缓存值计算完一个状态后先写回 DP 数组再返回其余逻辑与递归版完全一致。代码实现Pythonclass Solution: def cherryPickup(self, grid: List[List[int]]) - int: n len(grid) dp [[[[float(-inf)] * n for _ in range(n)] for _ in range(n)] for _ in range(n)] def dfs(r1, c1, r2, c2): if r1 n or c1 n or r2 n or c2 n or grid[r1][c1] -1 or grid[r2][c2] -1: return -1000 if r1 n - 1 and r2 n - 1 and c1 n - 1 and c2 n - 1: return grid[r1][c1] if dp[r1][c1][r2][c2] ! float(-inf): return dp[r1][c1][r2][c2] res dfs(r1 1, c1, r2 1, c2) res max(res, dfs(r1 1, c1, r2, c2 1)) res max(res, dfs(r1, c1 1, r2 1, c2)) res max(res, dfs(r1, c1 1, r2, c2 1)) res grid[r1][c1] grid[r2][c2] if r1 r2 and c1 c2: res - grid[r1][c1] dp[r1][c1][r2][c2] res return res return max(0, dfs(0, 0, 0, 0))注意不同语言的负无穷写法Java 用Integer.MIN_VALUE并四重循环初始化C 用INT_MIN初始化四维vectorGo 用-1 30Rust 用i32::MINSwift 用Int.minKotlin 用Int.MIN_VALUE——这些细节原文档的 9 语言实现中均已逐一给出。复杂度时间复杂度$O(n ^ 4)$空间复杂度$O(n ^ 4)$4 维表。解法三自顶向下优化——状态降维到 O(n³)直觉观察到一个不变式两人始终走相同步数。人 1 在(r1, c1)时已走r1 c1步人 2 也走了相同步数因此已知r2即可推出c2 r1 c1 - r2。状态从 4 维降为 3 维。算法步骤只用(r1, c1, r2)作为状态建立 3D DP 表每次动态计算c2 r1 c1 - r2对全部四个坐标含推算出的c2做越界检查基例人 1 到达(n-1, n-1)时返回该格樱桃值枚举 4 种移动组合递归求最大并缓存累加两人当前位置樱桃位置相同时避免重复计数。代码实现Pythonclass Solution: def cherryPickup(self, grid: List[List[int]]) - int: n len(grid) dp [[[float(-inf)] * n for _ in range(n)] for _ in range(n)] def dfs(r1, c1, r2): c2 r1 c1 - r2 if r1 n or c1 n or r2 n or c2 n or grid[r1][c1] -1 or grid[r2][c2] -1: return -1000 if r1 n - 1 and c1 n - 1: return grid[r1][c1] if dp[r1][c1][r2] ! float(-inf): return dp[r1][c1][r2] res dfs(r1 1, c1, r2 1) res max(res, dfs(r1 1, c1, r2)) res max(res, dfs(r1, c1 1, r2 1)) res max(res, dfs(r1, c1 1, r2)) res grid[r1][c1] if (r1, c1) ! (r2, c2): res grid[r2][c2] dp[r1][c1][r2] res return res return max(0, dfs(0, 0, 0))与 4D 版相比本版的去重逻辑改为「先加人 1 的樱桃若两人不在同一格再加人 2 的樱桃」效果等价但省去了减法分支。复杂度时间复杂度$O(n ^ 3)$空间复杂度$O(n ^ 3)$。解法四动态规划自底向上Bottom-Up直觉不用递归 记忆化而是从终点开始、逆序迭代填充 DP 表按(r1, c1, r2)从(n-1, n-1, n-1)到(0, 0, 0)反向遍历用c2 r1 c1 - r2推导c2由较小子问题逐步构建答案。算法步骤创建三维 DP 数组维度[n][n][n]初始化为足够小的负值如 Python 的-inf、C 的-1000000000、Java/C#/Kotlin/Swift/Rust 用MIN_VALUE / 2防止加法溢出对(r1, c1, r2)从大到小三重循环每步计算c2 r1 c1 - r2越界则continue任一人落在荆棘上则continue基例位于终点(n-1, n-1)时直接存入该格樱桃值否则从 4 个已经算好的未来状态中取最大值注意对r11、c11、r21做越界保护越界视为-1000累加当前樱桃两人同格时不重复计数返回dp[0][0][0]若为负则夹取到0。代码实现Pythonclass Solution: def cherryPickup(self, grid: List[List[int]]) - int: n len(grid) dp [[[float(-inf)] * n for _ in range(n)] for _ in range(n)] for r1 in reversed(range(n)): for c1 in reversed(range(n)): for r2 in reversed(range(n)): c2 r1 c1 - r2 if c2 0 or c2 n: continue if grid[r1][c1] -1 or grid[r2][c2] -1: continue if r1 n - 1 and c1 n - 1: dp[r1][c1][r2] grid[r1][c1] else: res max( dp[r1 1][c1][r2 1] if r1 1 n and r2 1 n else -1000, dp[r1 1][c1][r2] if r1 1 n else -1000, dp[r1][c1 1][r2 1] if c1 1 n and r2 1 n else -1000, dp[r1][c1 1][r2] if c1 1 n else -1000 ) if res -1000: continue res grid[r1][c1] if (r1, c1) ! (r2, c2): res grid[r2][c2] dp[r1][c1][r2] res return max(0, dp[0][0][0])这种「从终点逆推、由未来状态取 max」的填表顺序与姊妹题 cpp/1463-cherry-pickup-ii.cpp 中自底向上的实现思路完全一致——后者同样从最后一行向上迭代对每个(i, j, k)枚举机器人 1 与机器人 2 的 9 种列偏移组合取最大值// 摘自 cpp/1463-cherry-pickup-ii.cppCherry Pickup II 自底向上版 for (int i rows - 1; i 0; --i) { for (int j 0; j cols; j) { for (int k 0; k cols; k) { int cherries grid[i][j] (j ! k ? grid[i][k] : 0); if (i rows - 1) { dp[i][j][k] cherries; } else { int maxCherries 0; for (int dj -1; dj 1; dj) { for (int dk -1; dk 1; dk) { int nj j dj, nk k dk; if (nj 0 nj cols nk 0 nk cols) { maxCherries max(maxCherries, dp[i 1][nj][nk]); } } } dp[i][j][k] cherries maxCherries; } } } } return dp[0][0][cols - 1];两者的共同点是重叠去重j ! k时樱桃才累加两次与自底向上的依赖方向是理解整类「双人网格收集」问题的模板。复杂度时间复杂度$O(n ^ 3)$空间复杂度$O(n ^ 3)$。解法五空间优化——O(n²) 滚动数组直觉状态按总步数k r1 c1 r2 c2分层推进而第k层只依赖第k-1层。因此无需保留全部n³个状态只需两个[n][n]二维数组在「当前层 / 上一层」之间交替滚动空间从 $O(n^3)$ 降到 $O(n^2)$。算法步骤建立二维prev数组尺寸[n][n]代表上一层步数的状态用起点樱桃值初始化prev[0][0]对步数k从1到2n-2迭代新建二维dp表示当前层枚举合法(r1, r2)对其中c1 k - r1、c2 k - r2均在界内从上一层的 4 种转移两人各自来自上方或左方取最大值累加当前樱桃r1 ! r2时才累加第二份令prev dp进入下一层返回prev[n-1][n-1]若为负则夹取到0。代码实现Pythonclass Solution: def cherryPickup(self, grid: List[List[int]]) - int: n len(grid) prev [[float(-inf)] * n for _ in range(n)] prev[0][0] grid[0][0] for k in range(1, 2 * n - 1): dp [[float(-inf)] * n for _ in range(n)] for r1 in range(max(0, k - (n - 1)), min(n, k 1)): c1 k - r1 if c1 n or grid[r1][c1] -1: continue for r2 in range(max(0, k - (n - 1)), min(n, k 1)): c2 k - r2 if c2 n or grid[r2][c2] -1: continue val prev[r1][r2] if r1 0: val max(val, prev[r1 - 1][r2]) if r2 0: val max(val, prev[r1][r2 - 1]) if r1 0 and r2 0: val max(val, prev[r1 - 1][r2 - 1]) if val 0: continue val grid[r1][c1] if r1 ! r2: val grid[r2][c2] dp[r1][r2] val prev dp return max(0, prev[n - 1][n - 1])注意这里r1/r2的合法范围被约束为max(0, k - (n - 1))到min(n - 1, k)保证c1、c2不越界if val 0: continue用于丢弃不可达状态对应无路可走时保持-inf。复杂度时间复杂度$O(n ^ 3)$每层仍枚举所有合法(r1, r2)对空间复杂度$O(n ^ 2)$。五种解法复杂度总览解法思路时间复杂度空间复杂度1. 递归双人同步枚举 4 种移动$O(16 ^ n)$$O(n)$栈2. 自顶向下 DP4 维记忆化$O(n ^ 4)$$O(n ^ 4)$3. 自顶向下优化由c2 r1 c1 - r2降维$O(n ^ 3)$$O(n ^ 3)$4. 自底向上 DP从终点逆推填表$O(n ^ 3)$$O(n ^ 3)$5. 空间优化按步数滚动两层$O(n ^ 3)$$O(n ^ 2)$面试或刷题时通常以解法三自顶向下、状态清晰或解法五空间最优作为最终提交版本解法一、二用于建立直觉解法四用于对比「递归 vs 迭代」两种 DP 写法。常见陷阱Common Pitfalls原文档专门总结了五类高频错误这里逐一展开1. 当作两条独立路径先后求解先对去程做贪心或 DP、摘掉樱桃后再对返程单独求解。这种做法必然失败最优的整体方案可能要求去程走一条局部次优的路径以换取返程能采摘更多樱桃。两条路径必须放在同一个状态空间中同时决策——这正是本文双人建模的根本原因。2. 路径重叠时重复计数两人落在同一格(r1, c1) (r2, c2)时忘记减去一份樱桃。该格只能采摘一次# 错误总是累加两份 res grid[r1][c1] grid[r2][c2] # 正确重叠时减去一份 if r1 r2 and c1 c2: res - grid[r1][c1]3. 荆棘-1处理不当碰到荆棘时返回0而不是很大的负数。返回0会让非法路径在取最大值时看起来是可行的。必须返回-1000或float(-inf)之类足够小的值确保非法路径永远不会被选中。4. 忘记处理不存在有效路径的情形返回前不检查结果是否为负。如果整张网格被荆棘封锁、没有有效路径算法会返回一个负数。正确答案应夹取为max(0, result)。5. 用了 4 维状态却未做降维没有意识到c2可由c1、r1、r2直接推导——因为两人步数恒等r1 c1 r2 c2。利用该约束可将状态空间从 $O(n^4)$ 降到 $O(n^3)$这是从解法二到解法三的关键跃迁。延伸与姊妹题 Cherry Pickup II1463的对照本仓库还收录了同一主题的进阶题 articles/cherry-pickup-ii.md 及其多语言实现如 cpp/1463-cherry-pickup-ii.cpp、kotlin/1463-cherry-pickup-ii.kt。两者对比非常有助于吃透该类问题741本文方形网格、只允许右/下移动、含荆棘、双人同步前进、状态(r1, c1, r2)1463姊妹题rows × cols矩形网格、双机器人从顶部两角同时下行、每行可向左/中/右移动、无荆棘、状态(r, c1, c2)并用c1 c2约束消除对称重复状态。可以看到两道题共享同一套思维范式——用「同时移动的两个主体」建模用「同格去重」保证计数正确用「步数/行数对齐」压缩状态。掌握 741 的五级解法链后1463 只需把移动组合从 4 种换成 9 种、把降维约束从「步数相等」换成「同行枚举」即可直接套用 cpp/1463-cherry-pickup-ii.cpp 中的自底向上模板。总结Cherry Pickup 是检验多维 DP 功底的经典题目。本文沿 articles/cherry-pickup.md 给出的五级解法链从 $O(16^n)$ 的朴素递归出发依次经历 4 维记忆化$O(n^4)$、步数约束降维$O(n^3)$、自底向上填表$O(n^3)$与按层滚动$O(n^2)$ 空间并完整覆盖了「独立路径求解」「重叠去重」「荆棘作废」「无解夹取」「状态降维」五大陷阱。所有解法在本仓库文档中均有 9 种语言的完整实现可供对照查阅配合姊妹题 1463 的源码 cpp/1463-cherry-pickup-ii.cpp 一起练习即可系统掌握「双主体网格收集」这一类面试高频难题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考