一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

示例1：
不同路径 - 图1

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

示例2：

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

  1. 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向下

示例3：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

动态规划

二维数组

  1. function uniquePaths(m: number, n: number): number {
  2.     // 校验：m、n中有小于1的情况
  3.     if (m < 1 || n < 1) {
  4.         return 0;
  5.     } else if (m === 1 || n ===1) { // 边界：只有一行或者一列
  6.         return 1;
  7.     }
  8.     const dp: Array<Array<number>> = new Array(m).fill(0).map(() => new Array(n).fill(0));
  9.     for (let i = 0; i < m; i++) {
  10.         for(let j = 0; j < n; j++) {
  11.             if (i === 0 || j === 0) {
  12.                 dp[i][j] = 1;
  13.             } else {
  14.                 dp[i][j] = dp[i][j -1] + dp[i-1][j];
  15.             }
  16.         }
  17.     }
  18.     return dp[m - 1][n - 1];
  19. };

时间复杂度：O(mn)
空间复杂度：O(mn)

一维数组

  1. function uniquePaths(m: number, n: number): number {
  2.     // 校验：m、n中有小于1的情况
  3.     if (m < 1 || n < 1) {
  4.         return 0;
  5.     } else if (m === 1 || n ===1) { // 边界：只有一行或者一列
  6.         return 1;
  7.     }
  8.     const dp: Array<number> = new Array(n).fill(0);
  9.     for (let i = 0; i < m; i++) {
  10.         for(let j = 0; j < n; j++) {
  11.             if (i === 0 || j === 0) {
  12.                 dp[j] = 1;
  13.             } else {
  14.                 dp[j] = dp[j - 1] + dp[j];
  15.             }
  16.         }
  17.     }
  18.     return dp[n - 1];
  19. };

时间复杂度：O(mn)
空间复杂度：O(n)

组合数学

对，这是一个数学问题，为什么不用数学来解决呢？时间和空间快速优化！

数学知识

组合数概念：从 n 个不同元素中每次取出 m 个不同元素（0 ≤ m ≤ n），不管其顺序合成一组，称为从 n 个元素中不重复地选取 m 个元素的一个组合。所有这样的组合的种数称为组合数。
计算公式：在线性写法中被写昨C(n, m)，公式为：
不同路径 - 图2
n 元集合 A 中不重复地抽取 m 个元素作成的一个组合实质上是 A 的一个 m 元子集合。如果给集 A 编序不同路径 - 图3成为一个序集，那么 A 中抽取 m 个元素的一个组合对应于数段不同路径 - 图4到序集 A 的一个确定的严格保序映射。组合数不同路径 - 图5的常用符号还有
不同路径 - 图6
其中 n! 为 n的阶乘：n! = 1 × 2 × 3 × ⋯ × (n-1) n

数学解题思路

从左上角到右小角的过程中，我们需要移动 m + n - 2 次，其中 m - 1次向下移动，n - 1次向右移动。因此路径的总数，等于从 m + n - 2 次移动中 选择 m - 1 次向下移动的方案数，即组合数：
不同路径 - 图7
直接计算出这个组合数即可，计算的方法有很多种：

  • 如果使用的语言有组合数计算的API，可以直接调用API计算，像 Python中的 comb函数、Golang中的Binomial函数…
  • 如果没有响应的API，可以使用公式不同路径 - 图8进行计算，注意for循环中 x，y的起始值。

    代码

    1. function uniquePaths(m: number, n: number): number {
    2.   if (m > n) return uniquePaths(n, m);
    3.   let ans = 1;
    4.   for (let x = n, y = 1; y < m; x++, y++) {
    5.       ans = ans * x / y;  
    6.   }
    7.   return ans;
    8. };
    时间复杂度：O(min(m,n)
    空间复杂度：O(1)