最小路径和（LeetCode 64）全解：动态规划、二维 DP、一维滚动数组、DFS + 记忆化、原地修改与递归对比

一、题目描述给定一个包含非负整数的m × n网格grid请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。说明每次只能向下或者向右移动一步。示例 1输入grid [[1,3,1],[1,5,1],[4,2,1]]输出7解释因为路径 1→3→1→1→1 的总和最小。示例 2输入grid [[1,2,3],[4,5,6]]输出12约束m grid.lengthn grid[i].length1 m, n 2000 grid[i][j] 200二、问题分析这是一道经典的网格型动态规划Grid DP题目。它的核心特征最优子结构到达(i,j)的最优路径一定由到达其上方(i-1,j)或左方(i,j-1)的最优路径转移而来。重叠子问题从不同路径到达同一格子会重复求解相同子问题。无后效性一旦确定到达某格子的最小路径和后续决策不受之前路径形态影响。因为移动方向被限制为「只能向下或向右」所以不存在回路这为动态规划的递推顺序提供了天然保证。三、状态定义与转移方程3.1 状态定义设dp[i][j]表示从起点(0,0)走到格子(i,j)的最小路径和。3.2 状态转移方程要到达(i,j)只可能从上方或左方来dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])3.3 边界条件起点dp[0][0] grid[0][0]第一行i 0只能从左边来dp[0][j] dp[0][j-1] grid[0][j]第一列j 0只能从上面来dp[i][0] dp[i-1][0] grid[i][0]3.4 最终答案dp[m-1][n-1]四、解法一标准二维动态规划最直观、最规范的写法。新建一个与grid同尺寸的dp数组不修改输入。class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(), n grid[0].size(); // dp[i][j] 从 (0,0) 走到 (i,j) 的最小路径和 vectorvectorint dp(m, vectorint(n, 0)); // 初始化起点 dp[0][0] grid[0][0]; // 第一列只能从上面来 for (int i 1; i m; i) { dp[i][0] dp[i - 1][0] grid[i][0]; } // 第一行只能从左边来 for (int j 1; j n; j) { dp[0][j] dp[0][j - 1] grid[0][j]; } // 其余格子取上面和左边中较小的 for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j]; } } return dp[m - 1][n - 1]; } };复杂度分析时间复杂度O(m × n)空间复杂度O(m × n)优点逻辑清晰状态定义和转移方程一一对应面试推荐首选。缺点额外占用O(m × n)空间。五、解法二一维滚动数组空间优化观察转移方程dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]dp[i][j]只依赖上一行的同列dp[i-1][j]和本行的前一列dp[i][j-1]。因此可以把二维表压缩成一维数组滚动更新。class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(), n grid[0].size(); // dp[j] 表示当前行第 j 列的最小路径和 vectorint dp(n, 0); dp[0] grid[0][0]; // 初始化第一行 for (int j 1; j n; j) { dp[j] dp[j - 1] grid[0][j]; } // 逐行更新 for (int i 1; i m; i) { dp[0] grid[i][0]; // 第一列只能从上面来 for (int j 1; j n; j) { dp[j] min(dp[j], dp[j - 1]) grid[i][j]; // dp[j] 更新前 上一行的值上面 // dp[j-1] 更新后 本行左边的值左边 } } return dp[n - 1]; } };关键点内层循环中dp[j]在赋值前代表「上一行的dp[i-1][j]」赋值后代表「本行的dp[i][j]」。dp[j-1]已经在本次内层循环前一步更新代表「本行左边的dp[i][j-1]」。顺序必须从j 1向右保证左边先更新。复杂度分析时间复杂度O(m × n)空间复杂度O(n)优点不修改输入空间降到O(n)。缺点一维语义略抽象需要理解「滚动更新」的时机。六、解法三原地修改 grid思路与二维 DP 完全一致只是把grid本身当作dp数组使用因为每个格子的原始值在计算完自身后不会再被用到。class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(), n grid[0].size(); for (int i 0; i m; i) { for (int j 0; j n; j) { if (i 0 j 0) continue; else if (i 0) grid[i][j] grid[i][j - 1]; // 第一行 else if (j 0) grid[i][j] grid[i - 1][j]; // 第一列 else grid[i][j] min(grid[i - 1][j], grid[i][j - 1]); } } return grid[m - 1][n - 1]; } };复杂度分析时间复杂度O(m × n)空间复杂度O(1)优点空间最优代码短。缺点修改了输入数组语义上牺牲了可读性不适合要求保留原数据的场景。七、解法四DFS 记忆化自顶向下 DP7.1 为什么需要记忆化朴素 DFS 从(0,0)出发每次向下或向右递归会形成一棵庞大的递归树。很多子问题如(1,1)会被重复访问导致时间复杂度退化为指数级O(2^(mn))在大网格上必然超时。记忆化Memoization的核心思想用一个memo数组缓存每个状态的结果遇到相同状态直接返回。7.2 记忆化通用模板返回类型 dfs(状态参数) { if (终止条件) return 终止值; // 1. 边界 if (memo[状态] ! 未计算标记) return memo[状态]; // 2. 查表 结果 合并( dfs(子状态1), dfs(子状态2), ... ); // 3. 递归 memo[状态] 结果; // 4. 写表 return 结果; // 5. 返回 }7.3 本题实现class Solution { public: int minPathSum(vectorvectorint grid) { int m grid.size(), n grid[0].size(); // memo[i][j] 从 (i,j) 走到右下角的最小路径和 // -1 表示未计算 vectorvectorint memo(m, vectorint(n, -1)); return dfs(grid, 0, 0, memo); } private: int dfs(vectorvectorint grid, int i, int j, vectorvectorint memo) { int m grid.size(), n grid[0].size(); const int INF 1e9; // 1. 边界越界返回极大值保证 min 不会选它 if (i m || j n) return INF; // 2. 终止条件到达右下角 if (i m - 1 j n - 1) return grid[i][j]; // 3. 查表 if (memo[i][j] ! -1) return memo[i][j]; // 4. 递归只能向下或向右 int down dfs(grid, i 1, j, memo); int right dfs(grid, i, j 1, memo); // 5. 写表并返回 memo[i][j] grid[i][j] min(down, right); return memo[i][j]; } };复杂度分析时间复杂度O(m × n)每个状态只算一次空间复杂度O(m × n)memo 数组O(m n)递归栈7.4 记忆化常见坑坑说明未初始化标记memo默认全 0若答案是 0 会误判为「未计算」应用-1或INF标记状态定义不完整若递归还依赖额外参数如剩余步数kmemo必须带上该维度有环图状态间可互相到达时简单记忆化会死循环需要额外visited或改迭代 DP按值传表memo必须按引用传递否则每层递归拷贝效率骤降溢出用INT_MAX作不可达标记时参与加法会溢出建议用1e9