0062. 不同路径.md

62. 不同路径

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

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

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/unique-paths

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

m，n 最大 100，回溯会爆。

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
  var total = 0
  var backTrack = (left, right) => {
    if (left === 0 && right === 0) {
      total ++
    } else {
      if (left > 0) {
        backTrack(left - 1, right)
      }
      if (right > 0) {
        backTrack(left, right - 1)
      }
    }
  }
  backTrack(m - 1, n - 1)
  return total
};

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
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];
};

纯数学方法

result = C ^{m - 1} _{m + n - 2} = C ^{n - 1} _{m + n - 2}