64. 最小路径和#

大家好！继续我们的二维动态规划探索之旅，今天要一起攻克的是LeetCode上另一道经典题目：最小路径和。这道题是”不同路径”的近亲，同样考察我们在网格上的动态规划思维，但有了一个新的挑战——我们不仅要到达终点，还要寻找代价最小的那条路径。让我们一起深入这个问题！

🌟 问题的本质：从成本到最优解#

在”不同路径”中，我们关注的是路径的数量；而在”最小路径和”中，我们关注的是路径的质量。这反映了动态规划的两大核心问题类型：

计数问题：有多少种方法/路径？
最优化问题：最大/最小值是多少？

这种转变也反映了我们在实际生活中常面临的问题：不仅要知道有多少种选择，更要找出最佳选择。

问题描述#

题目目标#

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使路径上的数字总和最小。说明：每次只能向下或者向右移动一步。

示例 1#

输入： grid = [[1,3,1],[1,5,1],[4,2,1]] 输出： 7 网格示意：

1 3 1
1 5 1
4 2 1

text

说明： 图示把输入结构和输出结果并排展开后，会更容易直接看清题目的变化过程。

🎯 问题描述：带权重的网格漫步#

给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

例如：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：路径 1→3→1→1→1 的总和最小，为 7。

plaintext

🤔 从小例子开始思考#

让我们从简单的例子开始：

2x2网格：
[1, 3]
[2, 1]

可能的路径：
1. 右→下：1 + 3 + 1 = 5
2. 下→右：1 + 2 + 1 = 4

最小路径和为4

plaintext

再看一个稍复杂的例子：

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

plaintext

💡 发现规律：最优子结构#

通过分析，我们发现一个关键洞察：

要到达位置(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) {
        // 边界条件：网格为空或行/列为空时，无法形成有效路径，直接返回 0
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        // m 表示网格行数
        int m = grid.length;
        // n 表示网格列数
        int n = grid[0].length;
        // dp[i][j] 表示从起点 (0,0) 走到 (i,j) 的最小路径和
        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];
        }

        // 填充其余位置：每个点都可以从“上方”或“左方”到达，取两者较小值
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 当前格子的最小路径和 = 当前格子值 + min(上方最小路径和, 左方最小路径和)
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
            }
        }

        // 右下角即题目要求的最小路径和
        return dp[m-1][n-1];
    }
}

java

🎨 图解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]

plaintext

所以最小路径和是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) {
        // m 表示网格总行数
        int m = grid.length;
        // n 表示网格总列数
        int n = grid[0].length;
        // 一维 dp：dp[j] 表示“当前处理行”到达第 j 列的最小路径和
        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]（更新前）表示上方路径和，dp[j-1] 表示左方路径和
                // 取更小者并加上当前格子值，即可得到当前位置最小路径和
                dp[j] = Math.min(dp[j], dp[j-1]) + grid[i][j];
            }
        }

        // 最后一列对应右下角的最小路径和
        return dp[n-1];
    }
}

java

优化后，空间复杂度从O(m×n)降至O(n)，这在面对大型网格时尤为重要。

🔍 最优路径的追踪#

有时我们不仅需要知道最小路径和，还需要知道具体的路径。可以通过额外存储每个位置的选择来实现：

class Solution {
    public List<int[]> getMinPath(int[][] grid) {
        // m 表示行数
        int m = grid.length;
        // n 表示列数
        int n = grid[0].length;
        // dp[i][j] 记录从起点到 (i,j) 的最小路径和
        int[][] dp = new int[m][n];
        // choices[i][j] 记录 (i,j) 来自哪里：0 表示上方，1 表示左方（用于回溯路径）
        int[][] choices = new int[m][n];

        // 初始化和填充 dp 与 choices 数组
        // ...省略类似前面的初始化代码...

        // path 用于存储最终路径上的坐标点
        List<int[]> path = new ArrayList<>();
        // 从终点开始回溯，i/j 分别表示当前回溯到的行/列
        int i = m-1, j = n-1;
        // 先把终点加入路径
        path.add(new int[]{i, j});

        // 只要还没回到起点 (0,0)，就继续根据 choices 回退
        while (i > 0 || j > 0) {
            // 若当前点来自上方，则回溯到上一行
            if (choices[i][j] == 0) {
                i--;
            } else {
                // 否则来自左方，回溯到前一列
                j--;
            }
            // 回溯得到的是“从后往前”的点，所以插到列表头部保持起点到终点顺序
            path.add(0, new int[]{i, j});
        }

        // 返回一条最小路径（坐标序列）
        return path;
    }
}

java

🎭 变体问题：不同约束下的最小路径和#

实际应用中，我们可能会遇到各种变体：

有障碍物：某些格子无法通过，需要绕行
对角线移动：除了向右和向下，还可以斜向移动
负权重：格子值可能为负，需要避免环路

每种变体都会改变我们的状态转移方程，但核心思想仍然是：通过已知的最优子结构，构建当前位置的最优解。

💡 解题技巧与总结#

边界处理：二维DP中，边界初始化非常重要
状态压缩：当依赖关系简单时，可以压缩空间
路径追踪：需要记录决策过程，以便回溯
问题建模：将复杂问题转化为网格路径问题

🎓 面试指南#

面试官常常会在此类问题上加入变体，如何应对？

先解决基础问题，明确DP状态和转移方程
分析变体带来的新约束，相应调整转移方程
考虑时间和空间复杂度，是否可以优化
实现代码时注意边界情况处理

🔗 相似题目与延伸#

三角形最小路径和
最大正方形
矩阵中的最长递增路径

🤔 思考题#

如果网格中允许向左和向上移动（但不允许形成环），如何修改算法？

二维动态规划不仅是算法面试的高频考点，也是解决实际路径规划问题的重要工具。通过掌握”最小路径和”这类问题，我们不仅强化了DP的基本思路，也培养了解决更复杂优化问题的能力。希望这篇文章能帮助你在算法之路上更进一步！