最小路径和

给定一个包含非负整数的 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.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

最小路径和是非常经典的二维动态规划（DP）入门题目。它的核心思想是：要到达当前的格子，只能从它的“左边”或者“上边”走过来。因此，到达当前格子的最小路径和，取决于它左边和上边格子的最小路径和的较小值。

核心思路

1. 状态定义

   定义 $dp[i][j]$ 为从左上角 $(0,0)$ 到达位置 $(i,j)$ 的最小路径和。

2. 状态转移方程

   由于每次只能向下或向右移动，因此到达 $(i,j)$ 的上一步只有两种可能：

   • 从上方 $(i-1, j)$ 向下走一步；
   • 从左方 $(i, j-1)$ 向右走一步。

   为了使到达 $(i,j)$ 的路径和最小，我们需要选两者中较小的一个，再加上当前格子的数字：

   $dp[i][j] = \min(dp[i-1][j], dp[i][j-1]) + grid[i][j]$

3. 边界条件与初始化

   • 起点：$dp[0][0] = grid[0][0]$
   • 第一行：只能从左边一直往右走，所以 $dp[0][j] = dp[0][j-1] + grid[0][j]$
   • 第一列：只能从上面一直往下走，所以 $dp[i][0] = dp[i-1][0] + grid[i][0]$

参考代码

可以借用原矩阵 grid 或额外数组进行递推：

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

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

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

        // 3. 递推计算其余位置
        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 \times n)$，需要遍历网格中的每一个格子。
• 空间复杂度：
  • 直接修改原数组：$O(1)$，不需要额外的空间。
  • 一维数组优化（滚动数组）：$O(n)$。