[62] 不同路径

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

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

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

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2

输出: 3

解释:

从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下

2. 向右 -> 向下 -> 向右

3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3

输出: 28

最简易的动态规划，每一格只能从上方往下走和左方往右走两种情况，因此将这两格的情况相加即可。

function uniquePaths(m: number, n: number): number {
  // dp[i][j] 表示到达该处不同的路径条数
  // 状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
  const dp = Array(m)
    .fill(0)
    .map(x => Array(n).fill(0));
  for (let i = 0; i < m; i++) {
    dp[i][0] = 1;
  }
  for (let i = 0; i < n; i++) {
    dp[0][i] = 1;
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
}

由于每一格的取值只与上方与左方有关，因此我们可以化简为一维数组节省空间。一维数组存储对每一行遍历时上一行的数据，另外建一个变量pre存储遍历行时左边一格的数据，更新时指针右移，此时将pre于一维数组对应值更新即可。

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

受到女朋友的启发，抛开算法思维，只从基础数学角度思考的话，这题实际上用简单的排列组合就搞定了，小人向下走有n-1种选择，向左走有m-1种选择，那么总数不就是C(n-1)(m-1+n-1)（数学公式不好植入，n-1为上标，m-1+n-1为下标）吗？因此答案为(m-1+n-1)!/(m-1)!*(n-1)!。

var uniquePaths = function(m, n) {
  const smaller = (m < n ? m : n) - 1;
  const bigger = (m > n ? m : n) - 1;

  let dividend = 1;
  let divisor = 1;
  for (let i = 1; i <= smaller; i++) {
    dividend *= bigger + i;
    divisor *= i;
  }
  return dividend / divisor;
};

console.log(uniquePaths(3, 5));