LC62　不同路径¶

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

讲解章节：DP 入门

一句话

到某格的路径数等于上方与左方之和，一维数组滚着推完整张网格。

解题思路¶

这题考什么¶

机器人只能向下或向右，所以走到某一格的最后一步只有两种可能：从正上方下来，或从正左方过来。两类路径互不重叠（最后一步的方向不同），也没有遗漏（题目只允许这两种移动），把两边的路径数相加就是答案。这是网格上最基础的计数 DP，见 DP 入门。

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

f[i][j] = f[i-1][j] + f[i][j-1]

边界：第一行只能一路向右，第一列只能一路向下，各只有一条路径，全为 1。答案是 f[m-1][n-1]。

滚动数组省掉的是「行」这一维。 f[i][j] 只依赖上一行的同列与本行的左邻，两者都在长度为 n 的一维数组里就地取到：扫到第 j 列时， dp[j] 尚未被覆盖，存的正是上一行的 f[i-1][j]（「上」）； dp[j-1] 已在本行被覆盖过，存的是 f[i][j-1]（「左」）。于是一句 dp[j] += dp[j-1] 就完成了一次转移，且必须正序遍历列—— 倒序时 dp[j-1] 还是上一行的值，加出来的是另一道题的答案。

这题也有纯数学解：全程要走 m-1 步下、n-1 步右，路径数就是从 m+n-2 步里挑出 m-1 步向下的组合数 C(m+n-2, m-1)。DP 版更容易推广到有障碍的变体，所以这里写 DP。

数据规模与复杂度¶

1 <= m, n <= 100，题面另外保证答案不超过 2e9。时间 O(m * n) = 100 * 100 = 1e4 次加法，空间 O(n) = 100 个整数，都极小。朴素递归 paths(i, j) = paths(i-1, j) + paths(i, j-1) 不记忆化时，调用次数就等于路径数本身，可达 2e9 量级，必然超时； DP 把每个格子只算一次。

答案上界 2e9 已经超出 32 位有符号整数的 2.1e9 边缘不远，在 C++ 里要留意用 long long；Python 整数任意精度，不必处理。

坑在哪¶

dp 的初值整行取 1，代表的是第一行：只能一路向右，每格都只有一种走法。取 0 会让整张表恒为 0，取别的值则从第一行起就错。
外层只需再推 m-1 行。第一行已经由初值给出，写成 range(m) 会多推一行，算出的是 m+1 行网格的答案。
内层列必须从 1 开始，跳过第 0 列。第一列只能一路向下，路径数恒为 1， dp[0] 因此全程不动；若把 j = 0 也放进循环，dp[-1] 会静默取到 dp[n-1] （Python 负下标合法），把上一行末尾的值加进第一列，结果全错。
内层必须正序。倒序时 dp[j-1] 尚未在本行更新，取到的是上一行的值，转移就变成了 f[i-1][j] + f[i-1][j-1]，那是杨辉三角不是路径计数。
m 与 n 的角色可以互换（网格转置不改变路径数），所以不必纠结哪个是行哪个是列。题面样例 1 的 m=3、n=7 与样例 3 的 m=7、n=3 答案都是 28，正是这条对称性的体现。

样例复核¶

m = 3、n = 2。dp 初值 [1, 1]（第一行）。

第 1 轮（第二行）：dp[1] += dp[0] -> dp = [1, 2]
第 2 轮（第三行）：dp[1] += dp[0] -> dp = [1, 3]

返回 dp[1] = 3，与题面列出的三条路径一致。

参考实现¶

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


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 滚动数组省掉的是**行**这一维，只留长度 n 的一行。
        # 整行初值 1 就是第一行的答案：只能一路向右，每格都只有一种走法
        dp = [1] * n
        # 第一行已由初值给出，只需再推 m-1 行；写成 range(m) 会多推一行
        for _ in range(m - 1):
            # 从第 1 列开始：第 0 列只能一路向下，恒为 1 条路径，dp[0] 全程不动。
            # 把 j = 0 放进来会取到 dp[-1]，Python 的负下标不报错却会取到本行末尾
            for j in range(1, n):
                # 必须正序：此刻 dp[j] 尚未覆盖，是上一行的同列（「上」）；
                # dp[j-1] 已在本行覆盖过，是左邻（「左」）。
                # 倒序时 dp[j-1] 还是上一行的值，推出来的是杨辉三角而非路径计数
                dp[j] += dp[j - 1]
        return dp[n - 1]

LC62 不同路径¶