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

由于我最近临近期末考试所以后面两题就先暂时跳过，但是并不是代表我不写，等我暑假会全部补起来，那么来看今天的第一题

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                dp[i][0]=1;
                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：代码随想录

这道题目和上道题目是一样的，只不过是加了一些障碍物，这就意味着我们需要考虑一些特殊情况，首先就是初始化因为我们知道，如果说起点和终点就有障碍物的话，那肯定是直接返回0了，如果说在第一排或者是第一列出现障碍物，那是不是代表后面的点我都无法到达了，因为这些点只能由起点到达，所以只要我发现了障碍物，我就将后面所有的点都放上障碍物，也就是说后面的点都无法到达了，也就是将相应的数组的值赋值成1，然后就是递推公式的改变，首先如果我们当前遍历的点是障碍物的话，是不是直接continue就可以了，如果不是，我们还要在上面一题的基础上分情况讨论，有障碍物的就不能到达这点，所以我们可以写出如下代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& nums) {
        int m=nums.size();int n=nums[0].size();
        if(nums[0][0]==1) return 0;
        if(nums[m-1][n-1]==1) return 0;
        int dp[m][n];
        for(int i=0;i<m;i++){
            if(nums[i][0]==1){
                for(int j=i;j<m;j++) nums[j][0]=1;
                break;
            }
            dp[i][0]=1;
        }
        for(int i=0;i<n;i++){
            if(nums[0][i]==1){
                for(int j=i;j<n;j++) nums[0][j]=1;
                break;
            }
            dp[0][i]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(nums[i][j]==1) continue;
                if(nums[i-1][j]==1 && nums[i][j-1]==1) dp[i][j]=0;
                else if(nums[i-1][j]==1 && nums[i][j-1]!=1) dp[i][j]=dp[i][j-1];
                else if(nums[i-1][j]!=1 && nums[i][j-1]==1) dp[i][j]=dp[i-1][j];
                else dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

只需要在对应的情况分类讨论即可，这就是今天的内容了，比较少，因为后面两道难题我没时间做，我后面有时间做一定会补上！