代码随想录算法训练营Day39|62.不同路径、63.不同路径II

一、62 不同路径

1. 题目链接：力扣

2. 思路：求的是路径数，那么最左侧一列和最上面一行都只能朝一个方向走，因此只有一个路径，初始化的时候需要初始这些。而其他的数据应该是将这个格子上方与左侧的两个格子相加得出。需要注意的是js的二维数组定义方式，得记住。

3. 代码：

var uniquePaths = function(m, n) {
    // 这里要记住这个二维数组的定义方法
    var dp = Array(m).fill().map(item => Array(n));
    for (let i=0; i<m; i++) dp[i][0] = 1;
    for (let j=0; j<n; j++) dp[0][j] = 1;
    for (let i=1; i<m; i++) {
        for (let j=1; j<n; j++) {
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
        }
    }
    console.log(dp);
    return dp[m - 1][n - 1];
};

二、63 不同路径II

1. 题目链接：力扣

2. 思路：主要是需要判断障碍物部分，如果有的话需要把dp数组的这一个格子设为0，另外还需要注意初始化方面的问题，具体见代码。

3. 代码：

var uniquePathsWithObstacles = function(obstacleGrid) {
    var m = obstacleGrid.length;
    var n = obstacleGrid[0].length;
    var dp = Array(m).fill().map(item => Array(n));
    for (let i=0; i<m; i++) {
        for (let j=0; j<n; j++) {
            if (obstacleGrid[i][j] === 1) {
                dp[i][j] = 0;
            }
            // 需要规定dp[0][0]是1，不然的话都会变成0
            else if (i === 0 && j === 0) {
                dp[i][j] = 1;
            }
            // 不能再直接填充第一行和第一列为1了，因为有可能有障碍物挡着导致后面的都为0
            // 因此我们直接将超出外面的设为0，然后相加，也是一样的
            else {
                var top = i - 1 >= 0 ? dp[i - 1][j] : 0;
                var left = j - 1 >= 0 ? dp[i][j - 1] : 0;
                dp[i][j] = top + left;
            }
        }
    }
    return dp[m - 1][n - 1];
};

今日学习时长：1.5h左右

总结：今天的障碍物卡了一下下，主要是初始化方面的东西，另外需要注意js当中二维数组的定义。