最小路径和：动态规划的网格探险
大家好！继续我们的二维动态规划探索之旅，今天要一起攻克的是LeetCode上另一道经典题目：最小路径和。这道题是"不同路径"的近亲，同样考察我们在网格上的动态规划思维，但有了一个新的挑战——我们不仅要到达终点，还要寻找代价最小的那条路径。让我们一起深入这个问题！
🌟 问题的本质：从成本到最优解
在"不同路径"中，我们关注的是路径的数量；而在"最小路径和"中，我们关注的是路径的质量。这反映了动态规划的两大核心问题类型：
- 计数问题：有多少种方法/路径？
- 最优化问题：最大/最小值是多少？
这种转变也反映了我们在实际生活中常面临的问题：不仅要知道有多少种选择，更要找出最佳选择。
🎯 问题描述：带权重的网格漫步
给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。
例如：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：路径 1→3→1→1→1 的总和最小，为 7。🤔 从小例子开始思考
让我们从简单的例子开始：
2x2网格：
[1, 3]
[2, 1]
可能的路径：
1. 右→下：1 + 3 + 1 = 5
2. 下→右：1 + 2 + 1 = 4
最小路径和为4再看一个稍复杂的例子：
3x3网格：
[1, 3, 1]
[1, 5, 1]
[4, 2, 1]
可能的路径有多条，让我们追踪其中几条：
1. 右→右→下→下：1 + 3 + 1 + 1 + 1 = 7
2. 右→下→下→右：1 + 3 + 5 + 2 + 1 = 12
3. 下→右→右→下：1 + 1 + 5 + 1 + 1 = 9
4. 下→下→右→右：1 + 1 + 4 + 2 + 1 = 9
最小路径和为7💡 发现规律：最优子结构
通过分析，我们发现一个关键洞察：
要到达位置(i,j)，并且总和最小，只能通过：
- 从上方(i-1,j)到达，且上方已经是到达该点的最小路径和
- 从左方(i,j-1)到达，且左方已经是到达该点的最小路径和
我们选择其中较小的那个，再加上当前格子的值。
📝 二维动态规划解法
状态定义：
- dp[i][j] 表示：从起点(0,0)到位置(i,j)的最小路径和
状态转移方程：
- dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
// 初始化起点
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];
}
// 填充dp数组
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m-1][n-1];
}
}🎨 图解DP的执行过程
以3x3网格为例：
原始网格：
[1, 3, 1]
[1, 5, 1]
[4, 2, 1]
1. 初始化起点：
dp[0][0] = 1
2. 初始化第一行和第一列：
[1, 4, 5]
[2, □, □]
[6, □, □]
3. 填充dp[1][1]：
[1, 4, 5]
[2, 7, □]
[6, □, □]
解释：取min(2,4)+5=7
4. 填充dp[1][2]：
[1, 4, 5]
[2, 7, 8]
[6, □, □]
解释：取min(7,5)+1=6
... 依此类推
最终得到dp数组：
[1, 4, 5]
[2, 7, 6]
[6, 8, 7]所以最小路径和是7。
📊 执行轨迹分析
当我们填充dp数组时，每个位置的值是如何决定的？让我们看看dp[2][1]这个位置：
可以从dp[1][1]（值为7）向下走，总和为7+2=9 也可以从dp[2][0]（值为6）向右走，总和为6+2=8
因为8<9，所以我们选择从左边过来，得到dp[2][1]=8。
这种"比较+选择"的过程正是动态规划解决最优化问题的核心。
💫 空间优化：降维处理
与"不同路径"类似，我们观察到每个位置只依赖其上方和左方的值，因此可以使用一维数组优化空间：
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[] dp = new int[n];
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] = Math.min(dp[j], dp[j-1]) + grid[i][j];
}
}
return dp[n-1];
}
}优化后，空间复杂度从O(m×n)降至O(n)，这在面对大型网格时尤为重要。
🔍 最优路径的追踪
有时我们不仅需要知道最小路径和，还需要知道具体的路径。可以通过额外存储每个位置的选择来实现：
class Solution {
public List<int[]> getMinPath(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
int[][] choices = new int[m][n]; // 0表示从上方来，1表示从左方来
// 初始化和填充dp与choices数组
// ...省略类似前面的初始化代码...
// 从终点回溯
List<int[]> path = new ArrayList<>();
int i = m-1, j = n-1;
path.add(new int[]{i, j});
while (i > 0 || j > 0) {
if (choices[i][j] == 0) {
i--;
} else {
j--;
}
path.add(0, new int[]{i, j});
}
return path;
}
}🎭 变体问题：不同约束下的最小路径和
实际应用中，我们可能会遇到各种变体：
- 有障碍物：某些格子无法通过，需要绕行
- 对角线移动：除了向右和向下，还可以斜向移动
- 负权重：格子值可能为负，需要避免环路
每种变体都会改变我们的状态转移方程，但核心思想仍然是：通过已知的最优子结构，构建当前位置的最优解。
💡 解题技巧与总结
- 边界处理：二维DP中，边界初始化非常重要
- 状态压缩：当依赖关系简单时，可以压缩空间
- 路径追踪：需要记录决策过程，以便回溯
- 问题建模：将复杂问题转化为网格路径问题
🎓 面试指南
面试官常常会在此类问题上加入变体，如何应对？
- 先解决基础问题，明确DP状态和转移方程
- 分析变体带来的新约束，相应调整转移方程
- 考虑时间和空间复杂度，是否可以优化
- 实现代码时注意边界情况处理
🔗 相似题目与延伸
- 三角形最小路径和
- 最大正方形
- 矩阵中的最长递增路径
🤔 思考题
如果网格中允许向左和向上移动（但不允许形成环），如何修改算法？
作者：忍者算法
公众号：忍者算法
二维动态规划不仅是算法面试的高频考点，也是解决实际路径规划问题的重要工具。通过掌握"最小路径和"这类问题，我们不仅强化了DP的基本思路，也培养了解决更复杂优化问题的能力。希望这篇文章能帮助你在算法之路上更进一步！
#算法面试 #LeetCode #动态规划 #最优化问题 #网格问题