62. 不同路径

题目链接（中等）

题目描述

一个机器人位于一个 m x n 网格的左上角（起始点标记为 Start）。机器人每次只能向下或者向右移动一步，试图达到网格的右下角（标记为 Finish）。

问总共有多少条不同的路径？

数据范围：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 10^9

示例

示例 1：

输入： m = 3, n = 7
输出： 28

示例 2：

输入： m = 3, n = 2
输出： 3
解释： 从左上角开始，总共有 3 条路径可以到达右下角：

1. 向右 → 向下 → 向下
2. 向下 → 向下 → 向右
3. 向下 → 向右 → 向下

示例 3：

输入： m = 7, n = 3
输出： 28

示例 4：

输入： m = 3, n = 3
输出： 6

方法一：动态规划（二维）

思路及解法

1. 状态定义：设 dp(i, j) 为从左上角走到 (i, j) 的路径数量。

2. 转移方程：由于每一步只能向下或向右，走到 (i, j) 只能从 (i-1, j) 向下或从 (i, j-1) 向右而来，因此转移方程为：

$$dp(i, j) = dp(i-1, j) + dp(i, j-1)$$

1. 初始化：第一行和第一列都是 1（只有一种走法）

最终答案为 dp(m-1, n-1)。

代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

复杂度分析

• 时间复杂度：$O(mn)$，需要填充整个 $m \times n$ 的表格。
• 空间复杂度：$O(mn)$，二维 DP 表。

方法二：动态规划（滚动数组）

思路及解法

观察转移方程 dp(i, j) = dp(i-1, j) + dp(i, j-1)，其中 dp(i, j) 只和上一行同列 dp(i-1, j) 和本行左侧 dp(i, j-1) 有关。

因此可以把二维数组压缩成一维数组 f，长度为 n：

• 初始 f[j] = 1（代表第 0 行）；
• 遍历每一行 i，从左到右更新 f[j] += f[j-1]：
  • f[j] 在更新前是上一行的值 dp(i-1, j)；
  • f[j-1] 在更新后是本行的值 dp(i, j-1)；
  • 相加即为 dp(i, j)。

等价于把二维 DP 一行行压下来。

代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        f = [1] * n
        for i in range(1, m):
            for j in range(1, n):
                f[j] += f[j - 1]
        return f[n - 1]

复杂度分析

• 时间复杂度：$O(mn)$。
• 空间复杂度：$O(n)$。由于交换 m 和 n 不影响答案，可以保证 $m \le n$，从而空间降为 $O(\min(m, n))$。

方法三：组合数学

思路及解法

从左上角到右下角，一共需要移动 m + n - 2 步，其中：

• 向下移动 m - 1 次；
• 向右移动 n - 1 次。

路径总数等于从 m + n - 2 步中选 m - 1 步向下的方案数，即组合数：

$$C_{m+n-2}^{m-1} = \binom{m+n-2}{m-1} = \frac{(m+n-2)!}{(m-1)!\,(n-1)!}$$

Python 中可以直接调用 math.comb 计算。

代码

from math import comb

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m + n - 2, m - 1)

也可以用 comb(m + n - 2, n - 1)，结果相同。为降低时间开销，可以选取较小的那个作为 k。

复杂度分析

• 时间复杂度：$O(\min(m, n))$，计算组合数时只需乘 min(m, n) 次。
• 空间复杂度：$O(1)$。