📝 题目描述

题目链接：不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

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

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
示例 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 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 10^9

💡 解题思路

方法一：动态规划

我们用 f(i,j) 表示从左上角走到 (i,j) 的路径数量，其中 i 和 j 的范围分别是 [0,m) 和 [0,n)。

由于我们每一步只能从向下或者向右移动一步，因此要想走到 (i,j)，如果向下走一步，那么会从 (i−1,j) 走过来；如果向右走一步，那么会从 (i,j−1) 走过来。因此我们可以写出动态规划转移方程：

f(i,j)=f(i−1,j)+f(i,j−1)f(i,j)=f(i−1,j)+f(i,j−1)

需要注意的是，如果 i=0，那么 f(i−1,j) 并不是一个满足要求的状态，我们需要忽略这一项；同理，如果 j=0，那么 f(i,j−1) 并不是一个满足要求的状态，我们需要忽略这一项。

初始条件为 f(0,0)=1，即从左上角走到左上角有一种方法。

最终的答案即为 f(m−1,n−1)。

由于当前格子的路径数只依赖于正上方和左侧的格子，我们在遍历时，其实只需要保留“当前行”和“上一行”的数据。进一步压缩，我们只需要一个长度为 n 的一维数组就能完成状态滚动更新。

方法二：组合数学

机器人总共需要移动的步数是固定的：向下走 m−1m-1 步，向右走 n−1n-1 步，总共需要走 m+n−2m+n-2 步。
问题就转化为了：在总共 m+n−2m+n-2 步中，选出 m−1m-1 步向下的方案数是多少？

公式即为求组合数 Cm+n−2m−1C_{m+n-2}^{m-1} ：

Cm+n−2m−1=(m+n−2)!(m−1)!(n−1)!C_{m+n-2}^{m-1} = \frac{(m+n-2)!}{(m-1)!(n-1)!}

在代码实现时，唯一的难点是防止连乘时发生整型溢出。我们可以一边乘一边除，并使用 long long 来存储中间变量。

这里不必担心发生无法整除的现象，任意 ii 个连续自然数的乘积，一定能被 i!i!（ii 的阶乘）整除。

🔧 代码实现

1、动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 1);
        // 从第二行开始往下遍历，因为第一行时 i = 0， i - 1 不是有效状态
        for (int i = 1; i < m; i++) {
            // 同理，也从第二列开始遍历
            for (int j = 1; j < n; j++) {
                dp[j] = dp[j] + dp[j - 1];
            }
        }

        return dp[n - 1];
    }
};

2、组合数学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int uniquePaths(int m, int n) {
        long long ans = 1;
        // 取 m-1 和 n-1 中的较小值来降低时间复杂度
        int k = m < n ? m - 1 : n - 1; 
        int total = m + n - 2;
        
        // 计算组合数 C(total, k)
        for (int i = 1; i <= k; i++) {
            ans = ans * (total - i + 1) / i;
        }
        return ans; // 题目保证结果在这个范围内
    }
};

📊 复杂度分析

1、动态规划

  • 时间复杂度：O(m×n)O(m \times n)，需要遍历整个网格。
  • 空间复杂度：O(n)O(n)，只用到了一个长度为 nn 的一维数组。

2、组合数学

  • 时间复杂度：O(min⁡(m,n))O(\min(m, n))，只需要一个简单的循环，循环次数为 mm 和 nn 中较小的那一个。
  • 空间复杂度：O(1)O(1)，只需要常数级变量。

🎯 总结

  • 核心思想：记住动态规划的方法，以及优化成一维数组的思路。