LeetCode题解：62. 不同路径，动态规划，JavaScript，详细注释

[chencl1986]

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

解题思路：

1. 在网格中的任意一点，都有向右和向下两种走法。同时它也是从上方和左方两个位置走过来的。
2. 那么，任意一点的走法数量，等于从起点走到上方和左方点的数量之和。
3. 第一行和第一列都只有一种走法，就是从起点一直走到底。
4. 我们可以用一个二维数组，画出网格中每个点的走法数量，一直递推到终点，终点存储的就是所有的走法数量。
5. 因此动态规划的状态转移方程为：dp[i][j]=dp[i-1][j]+dp[i][j-1]。

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  // 按行数创建一个数组，用来存储整个网格，每个格子都存储到达当前位置所需的路径数
  let dp = new Array(m);

  // 遍历网格的行
  for (let i = 0; i < dp.length; i++) {
    // 只有网格超过一行，才需要计算
    if (i > 0) {
      // 网格第一列，就只有一种走法，因此存入1
      dp[i] = [1];

      // 从1开始遍历网格的列
      for (let j = 1; j < n; j++) {
        // 每个位置都是上方和左方两个点走过来的
        // 那么当前走法数量，就是上方和左方个位置的走法之和
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    } else {
      // 网格的第一行只有一种走法，因此全部为1
      dp[i] = new Array(n).fill(1);
    }
  }

  // 网格的最后一个位置，存储的就是最终结果
  return dp[m - 1][n - 1];
};

6. 实际上我们计算某个点的步数时，只需要左边和上边的值即可。
7. 我们可以只用一个数组，而且我们每次都是从左向右生成步数，因此就有以下特点：
   • 因此对于第m行来说，它存储的就是m-1行的步数。
   • 对于第n列来说，它的n-1位置存储了n-1位置的步数。

代码优化如下：

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  // 创建第一行，且第一行只有一种走法
  let dp = new Array(n).fill(1);

  // 第一行的走法都是1，因此从第二行开始计算
  for (let i = 1; i < m; i++) {
    // 第一列的走法都为1，因此从第二列开始计算
    for (let j = 1; j < n; j++) {
      // 每个位置都是上方和左方两个点走过来的
      // 那么当前走法数量，就是上方和左方个位置的走法之和
      // 当前位置原本存储的是上一行的结果，存储新结果之后，它就变成了下一位置的左边结果
      dp[j] = dp[j] + dp[j - 1];
    }
  }

  // 数组的最后一位存储的就是最终结果
  return dp[n - 1];
};