LeetCode-Book 精讲64. 最小路径和 —— 二维网格动态规划与原地空间优化【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇技术指南以 LeetCode-Book 仓库中《64. 最小路径和》题解文档为核心系统讲解二维网格上的动态规划Dynamic Programming解题范式从状态定义、转移方程到边界处理再到直接修改原矩阵的空间优化技巧。读完本文你将掌握带边界条件的二维 DP 递推模板并能理解为何该解法能以 $O(M \times N)$ 时间、$O(1)$ 额外空间完成求解可直接迁移到同类型网格寻路问题中。问题定义从左上角走到右下角的最小代价力扣第 64 题最小路径和Minimum Path Sum要求给定一个包含非负整数的 $m \times n$ 网格grid找到一条从左上角(0, 0)到右下角(m-1, n-1)的路径使得路径上的数字总和最小。约束是每次只能向下或者向右移动一步。输入: grid [[1,3,1], [1,5,1], [4,2,1]] 输出: 7 解释: 路径 1→3→1→1→1 的总和最小。只能向右或向下走这一约束是整个问题的灵魂它保证了路径不存在回头路从而使问题具备无后效性——从任意单元格 $(i,j)$ 出发的后续路径只取决于当前位置与到达 $(i,j)$ 的方式无关。这正是动态规划能够成立的先决条件。动态规划解题框架如题解文档所述此题是典型的动态规划题目按状态定义 → 转移方程 → 初始状态 → 返回值四步走即可完整求解。状态定义设 $dp$ 为大小 $m \times n$ 的矩阵其中 $dp[i][j]$ 的值代表直到走到 $(i,j)$ 的最小路径和。也就是说$dp[i][j]$ 记录的是从起点 $(0,0)$ 到达 $(i,j)$ 的所有可行路径中代价最小的那一条的累计和。转移方程题目要求只能向右或向下走换句话说当前单元格 $(i,j)$ 只能从左方单元格 $(i,j-1)$ 或上方单元格 $(i-1,j)$ 走到。因此走到当前单元格 $(i,j)$ 的最小路径和等于从左方单元格与从上方单元格走来的两个最小路径和中较小的那个再加上当前单元格值 $grid[i][j]$。写成公式即$$ dp[i][j] \min(dp[i-1][j],; dp[i][j-1]) grid[i][j] $$但该公式在矩阵边界处会失效会访问到不存在的行或列因此需要按边界情况分四种讨论情况条件转移方程含义① 一般情况$i \neq 0$ 且 $j \neq 0$$dp[i][j] \min(dp[i-1][j],; dp[i][j-1]) grid[i][j]$左边和上边都不是边界取两者较小值② 仅左边是边界$i 0,; j \neq 0$$dp[i][j] dp[i][j-1] grid[i][j]$第一行只能从左方来③ 仅上边是边界$i \neq 0,; j 0$$dp[i][j] dp[i-1][j] grid[i][j]$第一列只能从上方来④ 两者都是边界$i 0,; j 0$$dp[i][j] grid[i][j]$即起点本身直接取原值观察可知第一行情况②是前缀和式的累加第一列情况③同理而内部格子情况①则不断取上、左最小值 自身。初始状态$dp$ 矩阵无需特殊初始化保持初始 $0$ 值即可。因为遍历过程中每个 $dp[i][j]$ 都会被转移方程显式赋值起点情况④也会被单独处理$dp[0][0] grid[0][0]$。返回值返回 $dp$ 矩阵右下角的值 $dp[m-1][n-1]$即走到终点的最小路径和。手工推演理解递推过程以 $3 \times 3$ 的[[1,3,1],[1,5,1],[4,2,1]]为例按行优先顺序填充 $dp$起点$dp[0][0] 1$第一行情况②$dp[0][1] 13 4$$dp[0][2] 41 5$第一列情况③$dp[1][0] 11 2$$dp[2][0] 24 6$内部情况①$dp[1][1] \min(2,4) 5 7$$dp[1][2] \min(7,5) 1 6$$dp[2][1] \min(6,7) 2 8$$dp[2][2] \min(8,6) 1 7$最终右下角为 $7$与示例答案一致。这个过程体现了一个重要性质每个格子的值只依赖其左方和上方格子因此只需按先行后列或先列后行的顺序单次遍历即可完成全部递推。空间优化直接在原矩阵上修改题解文档特别指出我们完全不需要建立 $dp$ 矩阵浪费额外空间直接遍历修改grid[i][j]即可。这是因为$$ grid[i][j] \min(grid[i-1][j],; grid[i][j-1]) grid[i][j] $$原 $grid$ 矩阵元素中被覆盖为 $dp$ 元素后都处于当前遍历点的左上方不会再被后续任何计算使用到。原因如下每个格子 $grid[i][j]$ 只可能被右方格子 $(i,j1)$ 和下方格子 $(i1,j)$ 读取在行优先遍历中处理 $(i,j1)$ 与 $(i1,j)$ 时早已晚于处理 $(i,j)$此时 $(i,j)$ 的覆盖值已经就绪而位于 $(i,j)$ 左上方的旧值不会再有读取方。于是原矩阵被就地改造成 $dp$ 矩阵空间复杂度从 $O(M \times N)$ 降为 $O(1)$。这是滚动数组/状态压缩思想在二维网格 DP 中的直接体现——与一维场景如 53. 最大子数组和 中直接用nums充当 $dp$ 列表如出一辙。复杂度分析时间复杂度 $O(M \times N)$双层循环遍历整个 $grid$ 矩阵的全部 $M \times N$ 个元素每个元素仅做常数次比较与加法运算。空间复杂度 $O(1)$直接修改原矩阵不使用额外空间。若采用新建 $dp$ 矩阵的朴素写法空间复杂度则为 $O(M \times N)$。两种写法在时间上没有差别但原地写法在面试与工程实践中更受青睐。多语言代码实现与仓库源码佐证LeetCode-Book 仓库的selected_coding_interview目录收录了本题的 Python 与 Java 解法源码与题解文档给出的代码一一对应。Python 实现题解文档中的核心代码如下class Solution: def minPathSum(self, grid: [[int]]) - int: for i in range(len(grid)): for j in range(len(grid[0])): if i j 0: continue elif i 0: grid[i][j] grid[i][j - 1] grid[i][j] elif j 0: grid[i][j] grid[i - 1][j] grid[i][j] else: grid[i][j] min(grid[i - 1][j], grid[i][j - 1]) grid[i][j] return grid[-1][-1]仓库源码 lc_64_minimum_path_sum.py 中的Solution.minPathSum与该实现完全一致双层循环按行优先遍历用if / elif / else分支出题解中的四种边界情况最终return grid[-1][-1]取右下角值。文件头标注了作者 krahets 与创建时间符合仓库Solution Code Test Case Driver Code的统一文件模板当前该文件的测试用例标注为TODO等待补充。Java 实现class Solution { public int minPathSum(int[][] grid) { for(int i 0; i grid.length; i) { for(int j 0; j grid[0].length; j) { if(i 0 j 0) continue; else if(i 0) grid[i][j] grid[i][j - 1] grid[i][j]; else if(j 0) grid[i][j] grid[i - 1][j] grid[i][j]; else grid[i][j] Math.min(grid[i - 1][j], grid[i][j - 1]) grid[i][j]; } } return grid[grid.length - 1][grid[0].length - 1]; } }仓库源码 lc_64_minimum_path_sum.java 中Solution类置于package lc_64_minimum_path_sum;下并通过import include.*;引入仓库自带的工具类如 PrintUtil.java 等均位于codes/java/include/目录。注意 Python 与 Java 在边界判定上的细微差异Java 使用i 0 j 0Python 使用i j 0链式比较语义等价。关于 C 版本从仓库目录结构看selected_coding_interview/codes/cpp 下已收录lc_53_maximum_subarray、lc_54_spiral_matrix等同批次题目但暂未包含本题lc_64_minimum_path_sum的 C 文件。如需 C 解法可参照上文的转移方程与边界分支用std::vectorstd::vectorint原地修改并返回grid.back().back()复杂度结论不变。从源码结构看仓库的配套生态本题解属于 LeetCode-Book 仓库的《Krahets 笔面试精选 88 题》板块目录selected_coding_interview。根据 README.md 的说明该仓库整体包含三大部分LeetCode-Book ├── leetbook_ioa # 《图解算法数据结构》题解和专栏文档 ├── selected_coding_interview # 《Krahets 笔面试精选 88 题》题解文档 └── sword_for_offer # 《剑指 Offer》题解文档、代码、刷题计划题解文档位于 selected_coding_interview/docs/64. 最小路径和.md对应的 Python 代码与 Java 代码分别存放于codes/python/与codes/java/按题目编号组织为子目录。代码文件统一以lc_题号_题名命名包含 Solution Code 与 Driver Code 模板方便读者直接运行验证。举一反三二维网格 DP 的迁移掌握了本题的状态定义 四分支转移 原地压缩模板后可以迁移到以下同族问题LCR 166. 珠宝的最高价值《图解算法数据结构》在 $m \times n$ 棋盘中从左上走到右下求最大价值和转移方程形如 $dp[i][j] \max(dp[i-1][j], dp[i][j-1]) grid[i][j]$与本题几乎完全同构只是把 $\min$ 换成 $\max$。53. 最大子数组和一维 DP 的经典范式同样使用原数组充当 $dp$ 列表的原地压缩空间复杂度 $O(N) \to O(1)$是理解本题压缩原理的最佳前置练习。网格类问题变体如不同路径组合计数、地下城游戏逆序 DP等核心仍是明确状态含义、写对边界分支。小结最小路径和是二维网格动态规划的入门必做题其核心要点可归纳为三点状态定义$dp[i][j]$ 表示走到 $(i,j)$ 的最小路径和转移方程$dp[i][j] \min(dp[i-1][j], dp[i][j-1]) grid[i][j]$并按仅左边界 / 仅上边界 / 起点三种特殊分支处理边界空间压缩由于每个格子只依赖左方与上方且旧值不会被再次读取可以直接原地修改grid实现 $O(M \times N)$ 时间、$O(1)$ 空间的最终解法。结合 LeetCode-Book 仓库中的 Python 与 Java 源码对照阅读即可完整掌握从题解思路到可运行代码的闭环。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Book 精讲：64. 最小路径和 —— 二维网格动态规划与原地空间优化
LeetCode-Book 精讲64. 最小路径和 —— 二维网格动态规划与原地空间优化【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇技术指南以 LeetCode-Book 仓库中《64. 最小路径和》题解文档为核心系统讲解二维网格上的动态规划Dynamic Programming解题范式从状态定义、转移方程到边界处理再到直接修改原矩阵的空间优化技巧。读完本文你将掌握带边界条件的二维 DP 递推模板并能理解为何该解法能以 $O(M \times N)$ 时间、$O(1)$ 额外空间完成求解可直接迁移到同类型网格寻路问题中。问题定义从左上角走到右下角的最小代价力扣第 64 题最小路径和Minimum Path Sum要求给定一个包含非负整数的 $m \times n$ 网格grid找到一条从左上角(0, 0)到右下角(m-1, n-1)的路径使得路径上的数字总和最小。约束是每次只能向下或者向右移动一步。输入: grid [[1,3,1], [1,5,1], [4,2,1]] 输出: 7 解释: 路径 1→3→1→1→1 的总和最小。只能向右或向下走这一约束是整个问题的灵魂它保证了路径不存在回头路从而使问题具备无后效性——从任意单元格 $(i,j)$ 出发的后续路径只取决于当前位置与到达 $(i,j)$ 的方式无关。这正是动态规划能够成立的先决条件。动态规划解题框架如题解文档所述此题是典型的动态规划题目按状态定义 → 转移方程 → 初始状态 → 返回值四步走即可完整求解。状态定义设 $dp$ 为大小 $m \times n$ 的矩阵其中 $dp[i][j]$ 的值代表直到走到 $(i,j)$ 的最小路径和。也就是说$dp[i][j]$ 记录的是从起点 $(0,0)$ 到达 $(i,j)$ 的所有可行路径中代价最小的那一条的累计和。转移方程题目要求只能向右或向下走换句话说当前单元格 $(i,j)$ 只能从左方单元格 $(i,j-1)$ 或上方单元格 $(i-1,j)$ 走到。因此走到当前单元格 $(i,j)$ 的最小路径和等于从左方单元格与从上方单元格走来的两个最小路径和中较小的那个再加上当前单元格值 $grid[i][j]$。写成公式即$$ dp[i][j] \min(dp[i-1][j],; dp[i][j-1]) grid[i][j] $$但该公式在矩阵边界处会失效会访问到不存在的行或列因此需要按边界情况分四种讨论情况条件转移方程含义① 一般情况$i \neq 0$ 且 $j \neq 0$$dp[i][j] \min(dp[i-1][j],; dp[i][j-1]) grid[i][j]$左边和上边都不是边界取两者较小值② 仅左边是边界$i 0,; j \neq 0$$dp[i][j] dp[i][j-1] grid[i][j]$第一行只能从左方来③ 仅上边是边界$i \neq 0,; j 0$$dp[i][j] dp[i-1][j] grid[i][j]$第一列只能从上方来④ 两者都是边界$i 0,; j 0$$dp[i][j] grid[i][j]$即起点本身直接取原值观察可知第一行情况②是前缀和式的累加第一列情况③同理而内部格子情况①则不断取上、左最小值 自身。初始状态$dp$ 矩阵无需特殊初始化保持初始 $0$ 值即可。因为遍历过程中每个 $dp[i][j]$ 都会被转移方程显式赋值起点情况④也会被单独处理$dp[0][0] grid[0][0]$。返回值返回 $dp$ 矩阵右下角的值 $dp[m-1][n-1]$即走到终点的最小路径和。手工推演理解递推过程以 $3 \times 3$ 的[[1,3,1],[1,5,1],[4,2,1]]为例按行优先顺序填充 $dp$起点$dp[0][0] 1$第一行情况②$dp[0][1] 13 4$$dp[0][2] 41 5$第一列情况③$dp[1][0] 11 2$$dp[2][0] 24 6$内部情况①$dp[1][1] \min(2,4) 5 7$$dp[1][2] \min(7,5) 1 6$$dp[2][1] \min(6,7) 2 8$$dp[2][2] \min(8,6) 1 7$最终右下角为 $7$与示例答案一致。这个过程体现了一个重要性质每个格子的值只依赖其左方和上方格子因此只需按先行后列或先列后行的顺序单次遍历即可完成全部递推。空间优化直接在原矩阵上修改题解文档特别指出我们完全不需要建立 $dp$ 矩阵浪费额外空间直接遍历修改grid[i][j]即可。这是因为$$ grid[i][j] \min(grid[i-1][j],; grid[i][j-1]) grid[i][j] $$原 $grid$ 矩阵元素中被覆盖为 $dp$ 元素后都处于当前遍历点的左上方不会再被后续任何计算使用到。原因如下每个格子 $grid[i][j]$ 只可能被右方格子 $(i,j1)$ 和下方格子 $(i1,j)$ 读取在行优先遍历中处理 $(i,j1)$ 与 $(i1,j)$ 时早已晚于处理 $(i,j)$此时 $(i,j)$ 的覆盖值已经就绪而位于 $(i,j)$ 左上方的旧值不会再有读取方。于是原矩阵被就地改造成 $dp$ 矩阵空间复杂度从 $O(M \times N)$ 降为 $O(1)$。这是滚动数组/状态压缩思想在二维网格 DP 中的直接体现——与一维场景如 53. 最大子数组和 中直接用nums充当 $dp$ 列表如出一辙。复杂度分析时间复杂度 $O(M \times N)$双层循环遍历整个 $grid$ 矩阵的全部 $M \times N$ 个元素每个元素仅做常数次比较与加法运算。空间复杂度 $O(1)$直接修改原矩阵不使用额外空间。若采用新建 $dp$ 矩阵的朴素写法空间复杂度则为 $O(M \times N)$。两种写法在时间上没有差别但原地写法在面试与工程实践中更受青睐。多语言代码实现与仓库源码佐证LeetCode-Book 仓库的selected_coding_interview目录收录了本题的 Python 与 Java 解法源码与题解文档给出的代码一一对应。Python 实现题解文档中的核心代码如下class Solution: def minPathSum(self, grid: [[int]]) - int: for i in range(len(grid)): for j in range(len(grid[0])): if i j 0: continue elif i 0: grid[i][j] grid[i][j - 1] grid[i][j] elif j 0: grid[i][j] grid[i - 1][j] grid[i][j] else: grid[i][j] min(grid[i - 1][j], grid[i][j - 1]) grid[i][j] return grid[-1][-1]仓库源码 lc_64_minimum_path_sum.py 中的Solution.minPathSum与该实现完全一致双层循环按行优先遍历用if / elif / else分支出题解中的四种边界情况最终return grid[-1][-1]取右下角值。文件头标注了作者 krahets 与创建时间符合仓库Solution Code Test Case Driver Code的统一文件模板当前该文件的测试用例标注为TODO等待补充。Java 实现class Solution { public int minPathSum(int[][] grid) { for(int i 0; i grid.length; i) { for(int j 0; j grid[0].length; j) { if(i 0 j 0) continue; else if(i 0) grid[i][j] grid[i][j - 1] grid[i][j]; else if(j 0) grid[i][j] grid[i - 1][j] grid[i][j]; else grid[i][j] Math.min(grid[i - 1][j], grid[i][j - 1]) grid[i][j]; } } return grid[grid.length - 1][grid[0].length - 1]; } }仓库源码 lc_64_minimum_path_sum.java 中Solution类置于package lc_64_minimum_path_sum;下并通过import include.*;引入仓库自带的工具类如 PrintUtil.java 等均位于codes/java/include/目录。注意 Python 与 Java 在边界判定上的细微差异Java 使用i 0 j 0Python 使用i j 0链式比较语义等价。关于 C 版本从仓库目录结构看selected_coding_interview/codes/cpp 下已收录lc_53_maximum_subarray、lc_54_spiral_matrix等同批次题目但暂未包含本题lc_64_minimum_path_sum的 C 文件。如需 C 解法可参照上文的转移方程与边界分支用std::vectorstd::vectorint原地修改并返回grid.back().back()复杂度结论不变。从源码结构看仓库的配套生态本题解属于 LeetCode-Book 仓库的《Krahets 笔面试精选 88 题》板块目录selected_coding_interview。根据 README.md 的说明该仓库整体包含三大部分LeetCode-Book ├── leetbook_ioa # 《图解算法数据结构》题解和专栏文档 ├── selected_coding_interview # 《Krahets 笔面试精选 88 题》题解文档 └── sword_for_offer # 《剑指 Offer》题解文档、代码、刷题计划题解文档位于 selected_coding_interview/docs/64. 最小路径和.md对应的 Python 代码与 Java 代码分别存放于codes/python/与codes/java/按题目编号组织为子目录。代码文件统一以lc_题号_题名命名包含 Solution Code 与 Driver Code 模板方便读者直接运行验证。举一反三二维网格 DP 的迁移掌握了本题的状态定义 四分支转移 原地压缩模板后可以迁移到以下同族问题LCR 166. 珠宝的最高价值《图解算法数据结构》在 $m \times n$ 棋盘中从左上走到右下求最大价值和转移方程形如 $dp[i][j] \max(dp[i-1][j], dp[i][j-1]) grid[i][j]$与本题几乎完全同构只是把 $\min$ 换成 $\max$。53. 最大子数组和一维 DP 的经典范式同样使用原数组充当 $dp$ 列表的原地压缩空间复杂度 $O(N) \to O(1)$是理解本题压缩原理的最佳前置练习。网格类问题变体如不同路径组合计数、地下城游戏逆序 DP等核心仍是明确状态含义、写对边界分支。小结最小路径和是二维网格动态规划的入门必做题其核心要点可归纳为三点状态定义$dp[i][j]$ 表示走到 $(i,j)$ 的最小路径和转移方程$dp[i][j] \min(dp[i-1][j], dp[i][j-1]) grid[i][j]$并按仅左边界 / 仅上边界 / 起点三种特殊分支处理边界空间压缩由于每个格子只依赖左方与上方且旧值不会被再次读取可以直接原地修改grid实现 $O(M \times N)$ 时间、$O(1)$ 空间的最终解法。结合 LeetCode-Book 仓库中的 Python 与 Java 源码对照阅读即可完整掌握从题解思路到可运行代码的闭环。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考