08、最小路径和

今天要说的题目是最小路径和，我认为这是一道非常非常经典的题目，建议各位都掌握一下

https://leetcode.cn/problems/minimum-path-sum/

题目描述

给定一个包含非负整数的 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
解释：路径 1→2→3→6 或 1→2→5→6 总和都是 12

约束条件:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

问题理解

移动规则

只能向右或向下移动：

从 (i, j) 可以移动到：
1. (i, j+1) - 向右
2. (i+1, j) - 向下

不能向左或向上移动！

路径示例

网格：
1  3  1
1  5  1
4  2  1

所有可能路径（部分）：

路径1: 1→3→1→1→1 = 7 ✓ 最小
路径2: 1→3→1→5→1 = 11
路径3: 1→1→5→1→1 = 9
路径4: 1→1→5→2→1 = 10
路径5: 1→1→4→2→1 = 9

问题：找到总和最小的路径

动态规划思路

如何到达 (i, j)？

只有两种可能：
1. 从上方 (i-1, j) 向下移动
2. 从左边 (i, j-1) 向右移动

选择路径和较小的那个：
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

这个公式想出来之后，这个题目就完全没有难度啦

动态规划解法⭐

DP 五部曲

1. 确定 dp 数组及下标含义
   dp[i][j] 表示从 (0,0) 到 (i,j) 的最小路径和

2. 确定递推公式
   dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

   当前格子的值 + min(从上来, 从左来)

3. dp 数组如何初始化
   第一行：只能从左边来
   dp[0][j] = dp[0][j-1] + grid[0][j]

   第一列：只能从上面来
   dp[i][0] = dp[i-1][0] + grid[i][0]

   起点：
   dp[0][0] = grid[0][0]

4. 确定遍历顺序
   从左到右，从上到下
   for i in [0, m):
       for j in [0, n):

5. 举例推导 dp 数组
   见下方详细示例

详细图解示例

以示例1为例：grid = [[1,3,1], [1,5,1], [4,2,1]]

原始网格：
1  3  1
1  5  1
4  2  1

步骤1: 初始化第一行和第一列

第一行（只能向右走）：
dp[0][0] = 1
dp[0][1] = dp[0][0] + 3 = 1 + 3 = 4
dp[0][2] = dp[0][1] + 1 = 4 + 1 = 5

第一列（只能向下走）：
dp[0][0] = 1
dp[1][0] = dp[0][0] + 1 = 1 + 1 = 2
dp[2][0] = dp[1][0] + 4 = 2 + 4 = 6

当前 dp 数组：
1  4  5
2  ?  ?
6  ?  ?


步骤2: 计算 dp[1][1]
从上：dp[0][1] + grid[1][1] = 4 + 5 = 9
从左：dp[1][0] + grid[1][1] = 2 + 5 = 7
dp[1][1] = grid[1][1] + min(dp[0][1], dp[1][0]) = 7

当前 dp 数组：
1  4  5
2  7  ?
6  ?  ?


步骤3: 计算 dp[1][2]
从上：dp[0][2] + grid[1][2] = 5 + 1 = 6
从左：dp[1][1] + grid[1][2] = 7 + 1 = 8
dp[1][2] = grid[1][2] + min(dp[0][2], dp[1][1]) = 6

当前 dp 数组：
1  4  5
2  7  6
6  ?  ?


步骤4: 计算 dp[2][1]
从上：dp[1][1] + grid[2][1] = 7 + 2 = 9
从左：dp[2][0] + grid[2][1] = 6 + 2 = 8
dp[2][1] = grid[2][1] + min(dp[1][1] , dp[2][0]) = 8

当前 dp 数组：
1  4  5
2  7  6
6  8  ?


步骤5: 计算 dp[2][2]
从上：dp[1][2] + grid[2][2] = 6 + 1 = 7
从左：dp[2][1] + grid[2][2] = 8 + 1 = 9
dp[2][2] = grid[2][2] + min(dp[1][2], dp[2][1]) = 7

最终 dp 数组：
1  4  5
2  7  6
6  8  7

答案：dp[2][2] = 7 ✓

最优路径：
1(0,0) → 3(0,1) → 1(0,2) → 1(1,2) → 1(2,2)
路径和：1 + 3 + 1 + 1 + 1 = 7

代码实现

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        // 创建 dp 数组
        vector<vector<int>> dp(m, vector<int>(n));

        // 初始化起点
        dp[0][0] = grid[0][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++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }

        // 填充其余位置
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
            }
        }

        return dp[m-1][n-1];
    }
};

时间复杂度: O(m × n)，遍历整个网格

空间复杂度: O(m × n)，dp 数组

空间优化⭐⭐

优化思路

观察到 dp[i][j] 只依赖 dp[i-1][j] 和 dp[i][j-1]，可以原地修改 grid 或使用一维数组。

方法1：原地修改（利用原来的 grid 数组）

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        // 初始化第一行
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j-1];
        }

        // 初始化第一列
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i-1][0];
        }

        // 填充其余位置
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
            }
        }

        return grid[m-1][n-1];
    }
};

时间复杂度: O(m × n)

空间复杂度: O(1)，原地修改