代码随想录算法训练营第三十九 | ● 62.不同路径 ● 63. 不同路径 II

62.不同路径

https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html
视频讲解：https://www.bilibili.com/video/BV1ve4y1x7Eu

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n,0));
        for(int i=0;i<m;i++)
            dp[i][0] = 1;
        for(int j=0;j<n;j++)
            dp[0][j] = 1;
        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

63. 不同路径 II

https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html
视频讲解：https://www.bilibili.com/video/BV1Ld4y1k7c6

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        //记录行列数
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        //如果第一个就是障碍，直接返回0
        if(obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1)
            return 0;
        //定义dp二维数组，初始为0
        vector<vector<int>> dp(m, vector<int>(n,0));
        //给第一列元素挨个赋值为1，若遇到了障碍后面的元素就不更新了
        for(int i=0;i<m && obstacleGrid[i][0]==0;i++)
            dp[i][0] = 1;
        //给第一行所有元素挨个赋值为1，同理遇到障碍后面就不用管了
        for(int j=0;j<n && obstacleGrid[0][j]==0; j++)
            dp[0][j] = 1;
        //更新dp数组
        for(int i=1;i<m;i++) {
            for(int j=1; j<n; j++) {
                //遇到障碍不做处理，直接下一步操作。
                if(obstacleGrid[i][j]==1)
                    continue;
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        //返回目标下标的dp数组值
        return dp[m-1][n-1];
    }
};