62 不同路径

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

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

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

题解

动态规划的三部曲

确定dp数组的含义和下标的含义
递推公式
递推的初始化条件和递归顺序

1.确定dp数组 dp[i][j]表示到i，j可以的路径数量。 2.递推公式 dp[i][j] 可以从dp[i-1][j] 和dp[i][j-1]相加得到。即 dp[i][j] = dp[i-1][j] + dp[i][j-1] 3.初始条件,递归顺序假设只有一列多行，或者多行一列，他们的dp数组的值肯定都是1，因为只能向下走或者向右走。那么dp[i][0] = 1 以及dp[0][j] = 1

递归顺序从0,0一直到m,n，且和先遍历行和列无关。

所以题解如下

javascript

var uniquePaths3 = function(m, n) {
    var dp = []
    //初始化dp数组
    for(let i=0;i<m;i++) {
        var newRow = []
        dp.push(newRow)
        for(let j=0;j<n;j++) {
            if(i===0 || j=== 0) {
                dp[i][j] = 1
            }
        }
    }

    for(let i=0;i<m;i++) {
        for(let j=0;j<n;j++) {
            if(!dp[i][j]) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
    }

    return dp[m-1][n-1]
}

优化空间复杂度

我们可以利用一维数组来存储。试想如果m，n都是3的情况。二维dp数组是

1   1   1
1   2   3
1   3   6

我们是先求出了1,1,1，然后再求出了1,2,3，最后求出了1,3,6

我们发现可以只保留一行的数据即可，即定义dp[j]表示第j列的路径数量。第一次循环求出dp数组1,1,1

第二次循环，dp[j] = dp[j] + dp[j-1],也就是说dp[j] 是上一行的dp[j] 和这一次的 dp[j-1] 相加。

题解如下：

javascript

var uniquePaths4 = function(m,n) {
    var dp = []
    for(let i=0;i<n;i++) {
        dp[i] = 1
    }

    for(let i=1;i<m;i++) {
        for(let j=1;j<n;j++) {
            dp[j] = dp[j] + dp[j-1]
        }
    }
    //console.log(dp)
    return dp[n - 1]
}

62 不同路径 ​

题解 ​

62 不同路径

题解