BM67　不同路径的数目(一)¶

简单通过率 44.19%python3核心代码模式样例通过牛客 AC动态规划

牛客原题　源码

讲解章节：线性 DP

一句话

递推恰是杨辉三角，直接用组合数 C(m+n-2, m-1) 一步到位。

解题思路¶

这题考什么¶

先按坐标 DP 建模，再认出这张表就是杨辉三角，从而把整张表换成一个组合数。

状态定义：dp[i][j] = 从左上角走到第 i 行第 j 列的路径数（行列均从 0 起算）。每步只能向下或向右，所以到达 (i, j) 的上一步只可能在正上方或正左方，两类不重叠：

dp[i][j] = dp[i-1][j] + dp[i][j-1]
dp[0][j] = dp[i][0] = 1        贴着上边或左边走，只有一条路

「每格等于上方加左方」正是杨辉三角的递推，于是 dp[m-1][n-1] = C(m+n-2, m-1)。组合意义更直观：从起点到终点一共要走 (m-1) 步向下与 (n-1) 步向右，共 m+n-2 步，一条路径就是这串步子的一个排列，路径数即「在 m+n-2 步里挑哪 m-1 步向下」的方案数。于是不必开表，一个组合数就是答案，正好满足题面进阶要求的 O(1) 空间。

组合数按 C(t, k) = C(t, k-1) * (t-k+1) / k 递推着乘，循环取较小的 k = min(m, n) - 1（C(t, k) = C(t, t-k)，挑少的那边循环次数更少）。

数据规模与复杂度¶

0 < m, n <= 100，时限 2 秒（其他语言），题面保证结果在 32 位整型范围内。时间 O(min(m, n))，最多 99 次乘除；空间 O(1)。即便老老实实开 100 * 100 的表也只有 1e4 格，两种写法都远在时限内，这里选组合数是为了兑现进阶要求的 O(1) 空间。

坑在哪¶

乘除必须按「先乘后整除」的顺序做。前 i 步的乘积 C(t, i) 一定是整数，所以每一步的 // 都能整除；先除后乘会丢掉余数，把答案算小。
循环变量 i 与分子 (total - k + i) 的配对不能错位：第 i 步乘的是从 total-k+1 开始的第 i 个因子，除的是 i。写成 total - i 会把因子列表整体挪一位。
m 或 n 等于 1 时 k = 0，循环体一次都不进，返回初值 1——一条直线路径，正确。
用 Python 的浮点除法或先算阶乘再相除都不必要： m + n - 2 最大 198，阶乘虽然算得出，但中间量巨大且毫无好处。

参考实现¶

solutions/nowcoder/BM67/sol.py
from typing import List, Optional


class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        total = m + n - 2                # 总步数：(m-1) 步向下 + (n-1) 步向右
        k = min(m, n) - 1                # C(t,k) = C(t,t-k)，挑小的那边循环次数更少
        res = 1                          # C(t, 0) = 1，k = 0 时直接就是答案
        for i in range(1, k + 1):
            # 由 C(t,i-1) 递推到 C(t,i)：乘上新因子 (total-k+i) 再除以 i。
            # 每一步的乘积都是一个真正的组合数，所以 // 必然整除，不会丢精度
            res = res * (total - k + i) // i
        return res

BM67 不同路径的数目(一)¶