🥈62. 不同路径

🥈Medium

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

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

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

示例一：

//

输入：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 * 109

题解

组合公式法

这个是最快也是最简单的方法，要使机器人在m x n方格中从左上到右下，则需要向下n-1步，向右m-1步，即总共走m+n-2步，其中选出n-1步往下走即可，组合公式为：

因此我们直接计算出这个组合数即可。计算的方法有很多种：

如果使用的语言有组合数计算的 API，我们可以调用 API 计算；

如果没有相应的 API，我们可以使用 进行计算。

Python

Python有组合计算的api，直接调用即可

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

JavaScript

var uniquePaths = function(m, n) {
    let ans = 1;
    for (let x = n, y = 1; y < m; ++x, ++y) {
        ans = Math.floor(ans * x / y);
    }
    return ans;
};

复杂度分析

• 时间复杂度：。由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 m 和 n 使得 ，这样空间复杂度降低至 。

• 空间复杂度：。

  动态规划

  用表示从左上角走到的路径数量，其中和的范围分别为和.
  因为走的方式只有向右或者向下。所以要想到，要么是从过来的，要么是从过来的。因此动态规划的状态转移方程为：

要注意，如果，那么并不是一个满足要求的状态，同理，也不满足，此处需要忽略。

初始条件为，即左上角到左上角只有一种方法。最终结果即。为了方便起见，可以将所有的 以及 都设置为边界条件，它们的值均为 1。

Python

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

JavaScript

var uniquePaths = function(m, n) {
    const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
    for (let i = 0; i < m; i++) {
        f[i][0] = 1;
    }
    for (let j = 0; j < n; j++) {
        f[0][j] = 1;
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    return f[m - 1][n - 1];
};

复杂度分析

• 时间复杂度：

• 空间复杂度：，即为存储所有状态需要的空间。注意到 仅与第 i 行和第 i-1行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 。此外，由于我们交换行列的值并不会对答案产生影响，因此我们总可以通过交换 m 和 n 使得 ，这样空间复杂度降低至