62.不同路径

链接：62.不同路径
难度：Medium
标签：数学、动态规划、组合数学
简介：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？。

题解 1 - typescript

• 编辑时间：2020-12-09
• 执行用时：88ms
• 内存消耗：40.7MB
• 编程语言：typescript
• 解法介绍：动态规划。

function uniquePaths(m: number, n: number): number {
  const arr = new Array(n).fill(0).map(_ => new Array(m).fill(0));
  for (let i = n - 1; i >= 0; i--) {
    for (let j = m - 1; j >= 0; j--) {
      if (i === n - 1 || j === m - 1) {
        arr[i][j] = 1;
      } else {
        arr[i][j] = arr[i + 1][j] + arr[i][j + 1];
      }
    }
  }
  return arr[0][0];
}