我来给你讲解 LeetCode 第 64 题：最小路径和（Minimum Path Sum）。

题目描述

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

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

示例：

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

解题思路

第一步：理解问题本质

这是一个典型的网格动态规划问题。我们需要从左上角 (0,0) 走到右下角 (m-1, n-1)，每次只能向右或向下移动，目标是找到路径和的最小值。

关键观察：要到达某个格子 (i,j)，只能从它的上方 (i-1,j) 或左方 (i,j-1) 过来。因此，到达 (i,j) 的最小路径和取决于这两个相邻格子的最小路径和。

第二步：定义状态

定义 dp[i][j] 表示从起点 (0,0) 到达格子 (i,j) 的最小路径和。

第三步：状态转移方程

根据前面的分析，我们可以写出状态转移方程：

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

意思是：到达 (i,j) 的最小路径和 = 从上方或左方过来的较小值 + 当前格子的值。

第四步：边界情况处理

对于边界格子需要特殊处理：

• 左上角 (0,0)：dp[0][0] = grid[0][0]
• 第一行 (0,j)：只能从左边过来，dp[0][j] = dp[0][j-1] + grid[0][j]
• 第一列 (i,0)：只能从上边过来，dp[i][0] = dp[i-1][0] + grid[i][0]

第五步：算法实现步骤

1. 获取网格的行数 m 和列数 n
2. 创建 dp 数组，大小与 grid 相同
3. 初始化 dp[0][0] = grid[0][0]
4. 初始化第一行：dp[0][j] = dp[0][j-1] + grid[0][j]
5. 初始化第一列：dp[i][0] = dp[i-1][0] + grid[i][0]
6. 遍历剩余格子：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
7. 返回 dp[m-1][n-1]

第六步：示例演示

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

初始化：

dp[0][0] = 1

初始化第一行：

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

初始化第一列：

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

填充剩余格子：

dp[1][1] = min(dp[0][1]=4, dp[1][0]=2) + 5 = 2 + 5 = 7
dp[1][2] = min(dp[0][2]=5, dp[1][1]=7) + 1 = 5 + 1 = 6
dp[2][1] = min(dp[1][1]=7, dp[2][0]=6) + 2 = 6 + 2 = 8
dp[2][2] = min(dp[1][2]=6, dp[2][1]=8) + 1 = 6 + 1 = 7

最终结果为 dp[2][2] = 7。

第七步：优化空间复杂度

我们可以直接在原数组上修改，或者只使用一维数组来优化空间复杂度：

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(m × n)，需要遍历整个网格
• 空间复杂度：O(n)，使用了一维数组进行优化

这个问题的核心思想是动态规划，通过将大问题分解为小问题，并利用最优子结构性质，逐步构建出最终的解。