最小路径和

🟡 Medium · 🏷️ 数组、动态规划 · LeetCode#64

📖 题目

m×n 网格每格有个非负数字，找一条从左上到右下（只能向下或向右）的路径，使路径上数字总和最小。

💡 思路

不同路径问"有几条路"（计数，用加法），这题问"最短的路"（求最优，用 min），转移方程从相加变成取较小值再加上当前格子的代价：

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

初始化也不一样：不同路径的边界全是 1，这题的边界是累加——第一行/第一列只有一条路能到（一路直走），所以每格是"前一格 + 自己"的前缀和。

💻 代码

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [row[:] for row in grid]   # 逐行拷贝，不改动原网格

        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[-1][-1]

时间复杂度 O(m × n)，空间复杂度 O(m × n)。[row[:] for row in grid] 是逐行拷贝——直接 grid.copy() 只会复制外层列表，内层的每一行仍然是同一个引用，改 dp 会连带改到原始 grid。