LC64　最小路径和¶

中等通过率 72.5%python3核心代码模式多维动态规划样例通过牛客 AC数组动态规划矩阵

牛客原题　源码

讲解章节：DP 入门

一句话

每格的最优代价等于本格数值加上「上方与左方较小的那个」，一行滚到底。

解题思路¶

这题考什么¶

与 LC62 不同路径同构，只是把「路径计数」换成「代价最小化」：加法原理换成取最小值。走到某一格的最后一步只能来自正上方或正左方，两条来路各自的最优代价都已经算好，取较小的接上本格数值即可。见 DP 入门。

状态定义：f[i][j] 表示从左上角走到第 i 行第 j 列（下标从 0 起）的最小路径和。转移方程：

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

边界：第一行只能一路向右，第一列只能一路向下，各自是该方向上的前缀和。答案是 f[m-1][n-1]。

无后效性成立的理由值得说清：题面保证 grid[i][j] 非负，但这不是取最小值能成立的前提——真正的前提是「只能向下或向右」使得路径不可能绕回去，到达某格的方式被上一格的最优解完全概括。即便有负数，只要移动方向仍受限，这条转移照样成立。

滚动数组省掉的是「行」这一维。 扫到第 j 列时，dp[j] 尚未被覆盖，存的正是上一行的 f[i-1][j]（「上」）；dp[j-1] 已在本行覆盖过，存的是 f[i][j-1]（「左」）。列必须正序遍历，倒序时 dp[j-1] 还是上一行的值，取到的「左」是错的。

数据规模与复杂度¶

1 <= m, n <= 200，0 <= grid[i][j] <= 200。时间 O(m * n) = 200 * 200 = 4e4 次比较加法，空间 O(n) = 200 个整数。答案上界是走满 m+n-1 = 399 格、每格 200，即 79800，任何整数类型都装得下。暴力枚举全部路径是组合数 C(m+n-2, m-1) 条，m = n = 200 时是天文数字， DP 把它压到每格只算一次。

坑在哪¶

第一行不能用 0 起手。dp 必须先填成第一行的前缀和，因为第一行没有「上方」可选，只能一路向右累加。直接把 dp 初始化成全 0 再进主循环，会让第一行的代价被整个丢掉。
每行的第 0 列要单独处理：它没有左邻，只能从正上方来，所以是 dp[0] += grid[i][0] 而不是取最小值。若把 j = 0 也放进内层循环，dp[-1] 会静默取到本行末尾（Python 负下标合法），很可能得到一个更小的值，答案凭空变小且无从察觉。
内层必须正序。倒序时 dp[j-1] 尚未在本行更新，取到的是上一行的左邻，转移变成 min(f[i-1][j], f[i-1][j-1])，那是另一个模型。
m = 1 或 n = 1 的退化网格要能跑通。m = 1 时主循环一次都不进，直接返回第一行前缀和的末项；n = 1 时内层循环为空，每轮只做 dp[0] += grid[i][0]，累出整列的和。两种情形都不需要特判。
手写 if 比较而不是调用 min()，是为了省掉 4e4 次函数调用；这在 Python 里是可观的常数，且不改变语义。

样例复核¶

grid = [[1,3,1],[1,5,1],[4,2,1]]。

第一行前缀和：dp = [1, 4, 5]
第二行：dp[0] = 1 + 1 = 2
        dp[1] = 5 + min(4, 2) = 7
        dp[2] = 1 + min(5, 7) = 6
第三行：dp[0] = 2 + 4 = 6
        dp[1] = 2 + min(7, 6) = 8
        dp[2] = 1 + min(6, 8) = 7

返回 7，对应路径 1 -> 3 -> 1 -> 1 -> 1，与期望输出一致。

参考实现¶

solutions/leetcode/LC64/sol.py
from typing import List, Optional


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid[0])
        # 滚动数组省掉的是**行**这一维，只留长度 n 的一行。
        # 先把它填成第一行的前缀和：第一行没有「上方」可选，只能一路向右累加。
        # 起手全 0 再进主循环会把第一行的代价整个丢掉
        dp = [0] * n
        acc = 0
        for j in range(n):
            acc += grid[0][j]
            dp[j] = acc
        for i in range(1, len(grid)):
            row = grid[i]                   # 提出本行，省掉内层对 grid[i] 的重复寻址
            # 第 0 列没有左邻，只能从正上方来，是累加而不是取最小值。
            # 把它放进内层循环会取到 dp[-1]（Python 负下标合法，静默取到本行末尾），
            # 很可能得到更小的值，答案凭空变小且无从察觉
            dp[0] += row[0]
            for j in range(1, n):
                # 必须正序：此刻 dp[j] 尚未覆盖，是上一行同列的「上」；
                # dp[j-1] 已在本行覆盖过，是「左」。倒序会取到上一行的左邻，模型就错了。
                # 手写比较而非 min()，省掉 4e4 次函数调用，语义不变
                dp[j] = row[j] + (dp[j] if dp[j] < dp[j - 1] else dp[j - 1])
        return dp[n - 1]

LC64 最小路径和¶