64. 最小路径和

题目链接（中等）

题目描述

给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

数据范围：

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

示例

示例 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. 状态定义：dp[i][j] 表示从起点到 (i, j) 的最小路径和。

2. 转移方程：

由于路径只能向下或向右，对于位置 (i, j)，只能从上方 (i-1, j) 向下或从左方 (i, j-1) 向右到达：

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

1. 边界条件：

第一行的每个元素只能从左上角一路向右到达，第一列的每个元素只能从左上角一路向下到达，路径唯一，最小路径和就是沿途数字之和：

• dp[0][0] = grid[0][0]；
• i > 0, j = 0：dp[i][0] = dp[i-1][0] + grid[i][0]；
• i = 0, j > 0：dp[0][j] = dp[0][j-1] + grid[0][j]。

最终答案为 dp[m-1][n-1]。

代码

class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]

        # 第一列：只能从上往下
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] + grid[i][0]
        # 第一行：只能从左往右
        for j in range(1, n):
            dp[0][j] = dp[0][j - 1] + grid[0][j]
        # 其余位置：取上方和左方较小值
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

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

复杂度分析

• 时间复杂度：$O(mn)$，需遍历整个网格计算每个 dp 值。
• 空间复杂度：$O(mn)$，二维 dp 数组与网格大小相同。

方法二：动态规划（滚动数组）

思路及解法

观察转移方程 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]，dp[i][j] 只依赖上一行同列 dp[i-1][j] 和本行左侧 dp[i][j-1]。

因此可以把二维 dp 压成一维数组 f，长度 n：

• 初始 f[0] = grid[0][0]，其余按第一行累加；
• 遍历每一行 i，从左到右更新：
  • j = 0 时，f[0] += grid[i][0]（只能从上方来）；
  • j > 0 时，f[j] = min(f[j], f[j-1]) + grid[i][j]：
    • 更新前的 f[j] 是上一行的 dp[i-1][j]；
    • 更新后的 f[j-1] 是本行的 dp[i][j-1]；
    • 取较小值再加当前格子值，正好是 dp[i][j]。

代码

class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        f = [0] * cols
        f[0] = grid[0][0]

        # 初始化第一行
        for j in range(1, cols):
            f[j] = f[j - 1] + grid[0][j]

        for i in range(1, rows):
            f[0] += grid[i][0]        # 第一列只能从上往下
            for j in range(1, cols):
                f[j] = min(f[j], f[j - 1]) + grid[i][j]

        return f[cols - 1]

复杂度分析

• 时间复杂度：$O(mn)$。
• 空间复杂度：$O(n)$，只需一行滚动数组。