企业官网建设流程全解析

多维动态规划实战：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）——使用记忆化或填表法求解具有重叠子问题的优化问题；
• 多维 DP（Multi-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 种移动组合。两人落到同一格时只计一次樱桃，避免重复计数。

算法步骤

1. 定义递归函数dfs(r1, c1, r2, c2)，返回当人 1 在(r1, c1)、人 2 在(r2, c2)时能收集的最大樱桃数。
2. 非法剪枝：任一坐标越界，或任一人落在荆棘-1上，返回一个很大的负数（如-1000），使该路径作废。
3. 终点基例：两人都到达(n-1, n-1)时，返回该格樱桃值。
4. 尝试 4 种组合：两人都向下、两人都向右、一人向下另一人向右、以及相反。
5. 累加两人当前位置的樱桃；若(r1, c1) == (r2, c2)，减去一份避免重复。
6. 返回最大值；若最终结果为负，返回0（表示不存在有效路径）。

代码实现（Python）

class 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 维记忆化表，即可避免重复计算，把指数时间降为多项式时间。

算法步骤

1. 创建 4 维 DP 数组，初始化为负无穷，用于标记已访问状态；
2. 复用与解法一完全相同的dfs(r1, c1, r2, c2)；
3. 计算前先查表：若当前状态已被缓存，直接返回缓存值；
4. 计算完一个状态后，先写回 DP 数组再返回；
5. 其余逻辑与递归版完全一致。

代码实现（Python）

class 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初始化四维vector，Go 用-1 << 30，Rust 用i32::MIN，Swift 用Int.min，Kotlin 用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 维。

算法步骤

1. 只用(r1, c1, r2)作为状态建立 3D DP 表；
2. 每次动态计算c2 = r1 + c1 - r2；
3. 对全部四个坐标（含推算出的c2）做越界检查；
4. 基例：人 1 到达(n-1, n-1)时返回该格樱桃值；
5. 枚举 4 种移动组合，递归求最大并缓存；
6. 累加两人当前位置樱桃，位置相同时避免重复计数。

代码实现（Python）

class 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，由较小子问题逐步构建答案。

算法步骤

1. 创建三维 DP 数组，维度[n][n][n]，初始化为足够小的负值（如 Python 的-inf、C++ 的-1000000000、Java/C#/Kotlin/Swift/Rust 用MIN_VALUE / 2，防止加法溢出）；
2. 对(r1, c1, r2)从大到小三重循环；
3. 每步计算c2 = r1 + c1 - r2，越界则continue；
4. 任一人落在荆棘上则continue；
5. 基例：位于终点(n-1, n-1)时直接存入该格樱桃值；
6. 否则从 4 个已经算好的未来状态中取最大值（注意对r1+1、c1+1、r2+1做越界保护，越界视为-1000）；
7. 累加当前樱桃，两人同格时不重复计数；
8. 返回dp[0][0][0]，若为负则夹取到0。

代码实现（Python）

class 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.cpp（Cherry 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)$。

算法步骤

1. 建立二维prev数组（尺寸[n][n]），代表上一层步数的状态；
2. 用起点樱桃值初始化prev[0][0]；
3. 对步数k从1到2n-2迭代：
   • 新建二维dp表示当前层；
   • 枚举合法(r1, r2)对，其中c1 = k - r1、c2 = k - r2均在界内：
     • 从上一层的 4 种转移（两人各自来自上方或左方）取最大值；
     • 累加当前樱桃，r1 != r2时才累加第二份；
   • 令prev = dp进入下一层；
4. 返回prev[n-1][n-1]，若为负则夹取到0。

代码实现（Python）

class 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)$。

五种解法复杂度总览

面试或刷题时，通常以解法三（自顶向下、状态清晰）或解法五（空间最优）作为最终提交版本；解法一、二用于建立直觉，解法四用于对比「递归 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 II（1463）的对照

本仓库还收录了同一主题的进阶题 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