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

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

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

    1. /**
    2.  * 动态规划
    3.  * 时间复杂度：O(mn)
    4.  * 空间复杂度：O(mn)
    5.  */
    6. var uniquePaths = function (m, n) {
    7.   const dp = new Array(m).fill(0).map(() => new Array(n).fill(0))
    8.   for (let i = 0; i < m; i++) {
    9.     dp[i][0] = 1
    10.   }
    11.   for (let j = 0; j < n; j++) {
    12.     dp[0][j] = 1
    13.   }
    14.   for (let i = 1; i < m; i++) {
    15.     for (let j = 1; j < n; j++) {
    16.       dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    17.     }
    18.   }
    19.   return dp[m - 1][n - 1]
    20. }
    1. /**
    2.  * 动态规划
    3.  * 时间复杂度：O(mn)
    4.  * 空间复杂度：O(n)
    5.  */
    6. var uniquePaths = function (m, n) {
    7.   const dp = new Array(n).fill(1)
    8.   for (let i = 1; i < m; i++) {
    9.     for (let j = 1; j < n; j++) {
    10.       dp[j] += dp[j - 1]
    11.     }
    12.   }
    13.   return dp[n - 1]
    14. }