62-UniquePaths.md

不同路径

一个机器人位于一个 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;

思路： 使用动态规划（Dynamic Programming, DP）优化不同路径问题的算法可以通过以下步骤实现：

1. 定义状态：定义 dp[i][j] 表示到达网格中第 i 行第 j 列的路径数量。
2. 初始化状态：由于机器人只能从左上角开始，因此 dp[0][0] = 1，表示有一条路径可以到达起点。
3. 状态转移方程：对于每个状态 dp[i][j]，机器人只能从左边 dp[i][j-1] 或上面 dp[i-1][j] 到达，因此状态转移方程为：dp[i][j]=dp[i−1][j]+dp[i][j−1]
4. 填充 DP 表：按照行优先的方式填充 DP 表。对于第一行和第一列，由于只能从一个方向到达，所以直接复制上一行或左一列的值。对于其他位置，使用状态转移方程计算。
5. 返回结果：DP 表的最后一个元素 dp[m-1][n-1] 就是到达右下角的路径总数。

时间复杂度：O(m×n)，因为需要遍历整个 m x n 的 DP 表。 空间复杂度：O(m×n)，DP 表的大小为 m x n。

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
  // 创建 DP 表
  let dp = new Array(m).fill(0).map(() => new Array(n).fill(1));

  // 从第二行第二列开始填充 DP 表
  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];
};