BM68　矩阵的最小路径和¶

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

牛客原题　源码

讲解章节：线性 DP

一句话

逐行滚动的 dp[j] = a[i][j] + min(上, 左)。

解题思路¶

这题考什么¶

坐标 DP 的模板题，以及滚动数组省掉的是哪一维这个必答问题。

状态定义：dp[i][j] = 从左上角走到 (i, j) 的最小路径和。只能向右或向下，进入 (i, j) 的上一步必然在正上方或正左方：

dp[i][j] = a[i][j] + min(dp[i-1][j], dp[i][j-1])
dp[0][j] = 第 0 行的前缀和        首行没有上方，只能一路向右
dp[i][0] = 第 0 列的前缀和        首列没有左方，只能一路向下

答案是 dp[n-1][m-1]。转移只用到上一行的同列与本行的左邻，所以行这一维可以滚掉，只留长度 m 的一维数组：从左往右扫到第 j 列时，dp[j] 还没被本行覆盖，装的正是上一行的值（上），而 dp[j-1] 已经在本轮更新过，装的是本行的值（左）。 这就是为什么必须从左往右扫：倒着扫会让 dp[j-1] 仍是上一行的值，转移就变成「上方加左上方」，求的是另一个问题。滚动数组的一般讨论见 DP 入门。

实现上把这条带依赖的扫描下沉到 C 层：itertools.accumulate 的累加函数 f(acc, (a, up)) = a + min(acc, up)，其中 acc 恰好就是刚算出的「左」。 accumulate 会把序列的第一个元素原样吐出，所以把本行第 0 列的值 row[0] + dp[0] 先拼在序列最前面当种子。首行则直接 accumulate 求前缀和。

数据规模与复杂度¶

题面正文写 1 <= n, m <= 500，备注写 1 <= n, m <= 2000——两处不一致，按更大的 2000 准备：最坏 4e6 格，时限 2 秒（其他语言）。 4e6 次 Python 级迭代在判题机上（比本机慢数倍）风险不小，改用 accumulate 后每一行的整条扫描都在 C 层完成，只剩 2000 次外层循环。时间 O(n*m)、空间 O(m)，优于题面只要求的 O(nm) 时间。格子值 a[i][j] <= 100，路径和上界 4000 * 100 = 4e5，不涉及大整数。

坑在哪¶

首行与首列必须单独处理。它们各缺一个方向的前驱，套用通用转移会读到不存在的格子；代码用「首行 accumulate 前缀和」与「每行拼一个 row[0] + dp[0] 的种子」把这两条边界一次性解决。
一维滚动必须正序遍历列。倒序会让「左」变成上一行的值，算出的是另一种转移下的答案。
accumulate 的第一个元素是原样透传的，不经过累加函数，所以种子必须预先加好 dp[0]，写成 row[0] 会漏掉上一行首列的累计值。
空矩阵与空行要挡在前面，否则 matrix[0] 会抛 IndexError。
求的是路径和的最小值，不是格子数最小；每格的值都要计入，包括起点与终点。

样例复核¶

[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]：首行 dp = [1,4,9,18]；第二行种子 8+1=9，依次 9、min(9,4)+1=5、min(5,9)+3=8、min(8,18)+4=12；继续两行后 dp[-1] = 12，与期望输出一致。

参考实现¶

solutions/nowcoder/BM68/sol.py
from itertools import accumulate, chain
from typing import List, Optional


def _step(acc: int, t) -> int:
    """acc = 本行左邻 dp[j-1]，t = (a[i][j], 上一行的 dp[j])。"""
    up = t[1]
    # 手写比较代替 min()：这个函数会被调用 n*m 次，省下的函数调用是主要常数
    return t[0] + (acc if acc < up else up)


class Solution:
    def minPathSum(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0                                # 空矩阵挡在前面，避免下面取 matrix[0] 越界
        # dp 只留一行，省掉的是**行**这一维；下标 j 对应列
        dp = list(accumulate(matrix[0]))            # 第 0 行没有上方，只能一路向右求前缀和
        for row in matrix[1:]:
            # 第 0 列没有左邻，只能从上方来。accumulate 把序列首项原样吐出，
            # 所以这里必须把 dp[0] 预先加进种子，否则首列的累计值会丢
            # 其余各列 zip 成 (本行格子值, 上一行同列 dp)，正序扫描保证 acc 是「左」
            dp = list(accumulate(chain((row[0] + dp[0],), zip(row[1:], dp[1:])), _step))
        return dp[-1]                               # 右下角即答案

BM68 矩阵的最小路径和¶