好的，我们这次来详细讲解 LeetCode 第 64 题「最小路径和」。

1. 题目描述

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

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

示例：

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

2. 题目理解

• 起点：grid[0][0]
• 终点：grid[m-1][n-1]
• 只能向右或向下走。
• 路径上经过的格子中的数字要累加。
• 要求找到最小的累加和。

这其实是一个二维动态规划的经典问题，因为每个位置的最小路径和依赖于它的左边和上边位置的最小路径和。

3. 思路推导

3.1 暴力搜索（思路启发）

我们可以想象从 (0,0) 出发，每一步有两种选择（向右或向下），递归尝试所有路径，计算路径和，取最小值。
但这样时间复杂度是 \(O(2^{m+n})\)，会超时，因为有大量重复计算。

3.2 动态规划定义状态

定义 dp[i][j] 表示从 (0,0) 走到 (i,j) 的最小路径和。

3.3 状态转移方程

• 要走到 (i,j)，只能从 (i-1,j) 向下走，或者从 (i,j-1) 向右走。
• 所以 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

3.4 边界情况

• 当 i=0, j=0：dp[0][0] = grid[0][0]
• 当 i=0（第一行）：只能从左边来，dp[0][j] = dp[0][j-1] + grid[0][j]
• 当 j=0（第一列）：只能从上边来，dp[i][0] = dp[i-1][0] + grid[i][0]

4. 逐步计算示例

以示例网格：

1 3 1
1 5 1
4 2 1

4.1 初始化 dp 表（与 grid 同大小）

第一步：dp[0][0] = grid[0][0] = 1

第二行第一列（i=0）：

• dp[0][1] = dp[0][0] + grid[0][1] = 1 + 3 = 4
• dp[0][2] = dp[0][1] + grid[0][2] = 4 + 1 = 5

第一行第一列（j=0）：

• dp[1][0] = dp[0][0] + grid[1][0] = 1 + 1 = 2
• dp[2][0] = dp[1][0] + grid[2][0] = 2 + 4 = 6

此时 dp 表为：

1 4 5
2 ? ?
6 ? ?

计算 dp[1][1]：

• 从上 dp[0][1]=4，从左 dp[1][0]=2，取 min=2
• dp[1][1] = 2 + grid[1][1] = 2 + 5 = 7

计算 dp[1][2]：

• 从上 dp[0][2]=5，从左 dp[1][1]=7，取 min=5
• dp[1][2] = 5 + grid[1][2] = 5 + 1 = 6

计算 dp[2][1]：

• 从上 dp[1][1]=7，从左 dp[2][0]=6，取 min=6
• dp[2][1] = 6 + grid[2][1] = 6 + 2 = 8

计算 dp[2][2]：

• 从上 dp[1][2]=6，从左 dp[2][1]=8，取 min=6
• dp[2][2] = 6 + grid[2][2] = 6 + 1 = 7

最终 dp 表：

1 4 5
2 7 6
6 8 7

最小路径和 = dp[2][2] = 7，与示例一致。

5. 代码实现（Python）

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    
    dp[0][0] = grid[0][0]
    
    # 初始化第一行
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    
    # 初始化第一列
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    
    # 填充其余部分
    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]

6. 复杂度分析

• 时间复杂度：\(O(m \times n)\)，需要遍历整个网格一次。
• 空间复杂度：\(O(m \times n)\)，dp 表的大小。

7. 空间优化

我们可以用一维数组来优化空间复杂度到 \(O(n)\)：

因为计算 dp[i][j] 时只需要当前行的左边 dp[i][j-1] 和上一行的同列 dp[i-1][j]，所以可以用 dp[j] 表示当前行第 j 列的最小路径和，在计算过程中覆盖更新。

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    
    dp[0] = grid[0][0]
    for j in range(1, n):
        dp[j] = dp[j-1] + grid[0][j]
    
    for i in range(1, m):
        dp[0] += grid[i][0]  # 第一列只能从上方来
        for j in range(1, n):
            dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
    
    return dp[n-1]

这样空间复杂度降为 \(O(n)\)。

8. 总结

• 核心思路：动态规划，每个位置的最小路径和由左边和上边的最小值决定。
• 关键点：处理好边界条件（第一行和第一列）。
• 优化：空间可优化到 \(O(\min(m, n))\)。

这样循序渐进地理解，你应该能掌握这个题目的解法了。