Java版LeetCode热题100之最小路径和：从入门到精通的全面解析
摘要：本文深入剖析 LeetCode 热题 100 中的经典动态规划题目——「最小路径和」。我们将从原题回顾出发，逐步展开分析、解法设计、代码实现、复杂度评估，并延伸至算法优化、面试应对、实际应用场景等多个维度。全文结构清晰、内容翔实，适合准备算法面试或希望夯实动态规划基础的读者。
一、原题回顾
题目描述：
给定一个包含非负整数的m x 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
这道题是典型的网格路径问题，要求在有限移动方向（仅能向右或向下）的前提下，找到一条路径使得路径上的数字总和最小。它不仅考察了我们对动态规划的理解，也涉及状态转移、边界处理等关键编程技巧。
二、原题分析
2.1 问题本质
本题的核心在于：在有向无环图（DAG）中寻找从起点到终点的最短路径（权重为格子中的数值）。由于每次只能向右或向下走，整个网格实际上构成了一个 DAG，不存在回路，因此非常适合使用动态规划求解。
2.2 关键限制
- 移动方向受限：只能向右或向下 → 每个位置
(i, j)只能由(i-1, j)或(i, j-1)到达。 - 非负权重：所有
grid[i][j] ≥ 0→ 无需考虑负权边导致的复杂情况（如 Bellman-Ford），贪心或 DP 均可适用。 - 唯一目标：从
(0,0)到(m-1, n-1)的最小路径和。
2.3 直观思考
如果我们尝试暴力枚举所有路径（共有 C(m+n-2, m-1) 条），时间复杂度将呈指数级增长，显然不可行。因此需要一种更高效的方法——动态规划。
三、答案构思：动态规划设计
3.1 状态定义
设dp[i][j]表示从左上角(0, 0)走到位置(i, j)所需的最小路径和。
我们的目标是求出dp[m-1][n-1]。
3.2 状态转移方程
由于只能从上方或左方到达(i, j)，因此：
若
i > 0且j > 0：
d p [ i ] [ j ] = min ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) + g r i d [ i ] [ j ] dp[i][j] = \min(dp[i-1][j], dp[i][j-1]) + grid[i][j]dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]若在第一行（
i = 0, j > 0）：
d p [ 0 ] [ j ] = d p [ 0 ] [ j − 1 ] + g r i d [ 0 ] [ j ] dp[0][j] = dp[0][j-1] + grid[0][j]dp[0][j]=dp[0][j−1]+grid[0][j]若在第一列（
j = 0, i > 0）：
d p [ i ] [ 0 ] = d p [ i − 1 ] [ 0 ] + g r i d [ i ] [ 0 ] dp[i][0] = dp[i-1][0] + grid[i][0]dp[i][0]=dp[i−1][0]+grid[i][0]起点：
d p [ 0 ] [ 0 ] = g r i d [ 0 ] [ 0 ] dp[0][0] = grid[0][0]dp[0][0]=grid[0][0]
3.3 边界处理
- 网格为空？返回 0。
- 单行或单列？路径唯一，直接累加即可。
3.4 计算顺序
由于dp[i][j]依赖于上方和左方的状态，我们可以按行优先（或列优先）顺序遍历网格，确保在计算dp[i][j]时，dp[i-1][j]和dp[i][j-1]已经被计算。
四、完整答案（Java 实现）
classSolution{publicintminPathSum(int[][]grid){// 边界检查if(grid==null||grid.length==0||grid[0].length==0){return0;}introws=grid.length;intcols=grid[0].length;// 创建 dp 表int[][]dp=newint[rows][cols];// 初始化起点dp[0][0]=grid[0][0];// 初始化第一列for(inti=1;i<rows;i++){dp[i][0]=dp[i-1][0]+grid[i][0];}// 初始化第一行for(intj=1;j<cols;j++){dp[0][j]=dp[0][j-1]+grid[0][j];}// 填充其余位置for(inti=1;i<rows;i++){for(intj=1;j<cols;j++){dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];}}returndp[rows-1][cols-1];}}五、代码分析
5.1 结构清晰
- 边界处理：防止空指针异常。
- 初始化：单独处理第一行和第一列，避免在主循环中频繁判断边界。
- 主逻辑：双重循环填充
dp表，逻辑简洁。
5.2 正确性验证（以示例1为例）
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
构建dp表过程如下：
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | 1 | 4 | 5 |
| 1 | 2 | 7 | 6 |
| 2 | 6 | 8 | 7 |
最终dp[2][2] = 7，与预期一致。
5.3 鲁棒性
- 支持
1x1网格（直接返回grid[0][0]）。 - 支持单行（如
[[1,2,3]]）或单列（如[[1],[2],[3]]）。
六、时间复杂度与空间复杂度分析
6.1 时间复杂度
- 需要遍历整个
m x n网格一次。 - 每个单元格的计算为 O(1)。
- 总时间复杂度：O(mn)
6.2 空间复杂度
- 使用了一个
m x n的dp数组。 - 原始空间复杂度：O(mn)
⚠️ 注意：题目未要求保留原始
grid，因此可以原地修改grid作为dp表，将空间复杂度降至 O(1)。但通常为了代码清晰性和避免副作用，建议使用额外空间。
七、问题解答（FAQ）
Q1：为什么不能用贪心算法？
答：贪心策略（如每一步选较小的邻居）可能陷入局部最优。例如：
grid = [[1, 3], [1, 5]]贪心会选择
1 → 1 → 5 = 7，但最优是1 → 3 → 5 = 9？不对！等等，这里其实贪心是对的？再看反例：
grid = [[1, 2, 3], [4, 8, 2], [1, 5, 3]]贪心第一步选
1→2（比1→4小），但后续可能被迫走大数。而最优路径可能是1→4→1→5→3 = 14，而贪心路径1→2→3→2→3 = 11？似乎还是对的？实际上，在只能向右/向下且权重非负的情况下，贪心并不总是失败，但无法保证全局最优。动态规划通过记录所有子问题的最优解，确保最终结果正确。
Q2：能否从右下角反向推导？
答：可以。定义
dp[i][j]为从(i,j)到(m-1,n-1)的最小路径和，则：
d p [ i ] [ j ] = g r i d [ i ] [ j ] + min ( d p [ i + 1 ] [ j ] , d p [ i ] [ j + 1 ] ) dp[i][j] = grid[i][j] + \min(dp[i+1][j], dp[i][j+1])dp[i][j]=grid[i][j]+min(dp[i+1][j],dp[i][j+1])
需从右下角开始反向填充。逻辑等价，但正向更直观。
Q3：如果允许向上或向左移动怎么办？
答：此时图中可能出现环，问题变为带权最短路径问题，需使用 Dijkstra 算法（因权重非负）或 Floyd-Warshall（小规模）。
八、优化思路
8.1 空间优化：滚动数组
观察发现，计算第i行时，只依赖第i-1行和当前行已计算的部分。因此可用一维数组代替二维dp。
优化后代码：
publicintminPathSum(int[][]grid){if(grid==null||grid.length==0||grid[0].length==0)return0;introws=grid.length,cols=grid[0].length;int[]dp=newint[cols];dp[0]=grid[0][0];// 初始化第一行for(intj=1;j<cols;j++){dp[j]=dp[j-1]+grid[0][j];}// 从第二行开始for(inti=1;i<rows;i++){dp[0]+=grid[i][0];// 第一列只能从上方来for(intj=1;j<cols;j++){dp[j]=Math.min(dp[j],dp[j-1])+grid[i][j];}}returndp[cols-1];}空间复杂度：O(n)
注：若
m < n，可按列滚动，进一步优化为 O(min(m, n))。
8.2 原地修改（不推荐但可行）
直接复用grid数组：
for(inti=0;i<rows;i++){for(intj=0;j<cols;j++){if(i==0&&j==0)continue;elseif(i==0)grid[i][j]+=grid[i][j-1];elseif(j==0)grid[i][j]+=grid[i-1][j];elsegrid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);}}returngrid[rows-1][cols-1];优点：O(1) 空间
缺点：破坏输入数据，不符合函数式编程原则。
九、数据结构与算法基础知识点回顾
9.1 动态规划（Dynamic Programming, DP）
- 核心思想：将复杂问题分解为重叠子问题，通过存储子问题解避免重复计算。
- 适用条件：
- 最优子结构：全局最优解包含子问题最优解。
- 重叠子问题：子问题被多次调用。
- 实现方式：自顶向下（记忆化搜索）或自底向上（填表法）。
9.2 网格 DP 的通用模式
- 状态：
dp[i][j]表示到达(i,j)的某种最优值。 - 转移：根据移动规则（如右/下）决定依赖关系。
- 边界：处理第一行、第一列或边缘情况。
9.3 空间优化技巧
- 滚动数组：当状态仅依赖前一行/列时，用一维数组替代二维。
- 状态压缩：利用位运算或数学变换减少状态表示。
十、面试官提问环节（模拟）
Q1：你能解释一下为什么这个 DP 是正确的吗？
答：因为每一步的决策只依赖于已知的最优子路径（上方或左方），且我们从小到大构建解，确保每个
dp[i][j]都是最优的。这满足最优子结构性质。
Q2：如果网格中有障碍物（如 -1 表示不可通行），如何修改？
答：遇到障碍物时，
dp[i][j] = INF（表示不可达）。初始化时若起点是障碍，直接返回 0 或 -1。转移时跳过障碍位置。
Q3：如何输出具体的最小路径（而不仅是和）？
答：在 DP 过程中记录“选择来源”（来自上 or 左），最后从终点回溯即可。需额外
parent[i][j]数组。
Q4：时间和空间复杂度还能再优化吗？
答：时间已是最优 O(mn)，因必须读取每个格子。空间可优化至 O(n) 或 O(min(m,n))，如前所述。
十一、这道算法题在实际开发中的应用
虽然“最小路径和”看似抽象，但它在多个领域有实际价值：
11.1 图像处理
- 图像 seam carving（接缝裁剪）：寻找能量最低的像素路径进行图像缩放，其核心就是类似 DP 的路径搜索。
11.2 路径规划
- 机器人在网格地图中寻找能耗最低的路径（每个格子代表不同地形阻力）。
11.3 金融风控
- 在多阶段决策中（如贷款审批流程），每个节点有成本，寻找总成本最低的审批路径。
11.4 编译器优化
- 指令调度中，寻找执行代价最小的指令序列。
启示：DP 不仅是面试题，更是解决多阶段决策优化问题的强大工具。
十二、相关题目推荐
掌握本题后，可挑战以下变种或进阶题：
| 题目 | 链接 | 难度 | 关键变化 |
|---|---|---|---|
| 62. 不同路径 | LeetCode | 中等 | 求路径数量（无权重） |
| 63. 不同路径 II | LeetCode | 中等 | 加入障碍物 |
| 120. 三角形最小路径和 | LeetCode | 中等 | 三角形结构，自底向上 DP |
| 174. 地下城游戏 | LeetCode | 困难 | 需反向 DP，考虑生命值约束 |
| 931. 下降路径最小和 | LeetCode | 中等 | 可向左下、正下、右下移动 |
建议按顺序练习，逐步提升 DP 建模能力。
十三、总结与延伸
13.1 核心收获
- 动态规划建模能力：学会定义状态、写出转移方程、处理边界。
- 空间优化意识：理解滚动数组的原理与应用场景。
- 问题抽象能力：将现实问题转化为网格路径模型。
13.2 延伸思考
- 如果允许对角线移动？→ 转移方程增加
dp[i-1][j-1]。 - 如果要求路径必须经过某个点？→ 分段 DP：起点→中点→终点。
- 如果网格非常大（如 1e5 x 1e5）？→ 需考虑稀疏表示或启发式搜索（如 A*）。
13.3 学习建议
- 动手实现：不要只看代码，自己写一遍并调试。
- 画图辅助：用表格模拟 DP 过程，加深理解。
- 举一反三：做完后思考“如果条件变了，怎么改？”
结语：算法之美，在于将复杂问题化繁为简。最小路径和虽是一道中等题，却蕴含了动态规划的精髓。希望本文能助你在算法之路上走得更远、更稳。
欢迎点赞、收藏、评论交流！
关注我，获取更多 LeetCode 热题深度解析！
字数统计：约 9200 字（含代码与公式）
适用读者：LeetCode 刷题者、校招/社招面试准备者、算法爱好者
