C++ day39 动态规划不同路径不同路径Ⅱ

题目1：62 不同路径

题目链接：不同路径

对题目的理解

机器人位于m*n的网格中的左上角start,求解走到网格右下角finish的移动路径

动规五部曲

1）dp数组的含义以及下标i的含义

dp[i][j]：从start（0，0）位置到位置（i，j）有多少不同的路径

2)递推公式

因为题目要求只能向右和向下走，所以dp[i][j]只能从紧邻它的正方的格走到，或是紧邻它的正左方的格得到

所以dp[i][j]与dp[i][j-1]有关，只要dp[i][j-1]再向右走一步就可以到达(i,j)的位置

同理，dp[i][j]与dp[i-1][j]有关，只要dp[i-1][j]再向下走一步就可以到达(i,j)的位置

dp[i][j] = dp[i-1][j] + dp[i][j-1]

3）初始化dp数组

第一行：dp[0][j]，(j从0~n变化)，代表从起始位置（0，0）一直向右走，到（0，j），只有1种走法

第一列：dp[i][0]，（i从0~m变化）代表从起始位置(0，0)一直向下走，到（i，0），只有一种走法

for(int i=0;i<m;i++) dp[i][0] = 1

for(int j=0;j<n;j++) dp[0][j] = 1

4）遍历顺序

从左往右遍历，从上往下遍历，因为dp[i][j]与 dp[i-1][j](上)和dp[i][j-1](左)有关

5）打印dp数组

代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        //定义dp数组
        vector<vector<int>> dp(m, vector<int>(n,0));
        //初始化dp数组
        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++){//从第2行开始
            for(int j=1;j<n;j++){//从第2列开始
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

时间复杂度：O(m × n)
空间复杂度：O(m × n)

压缩代码（优化空间复杂度）

这个有点难理解

class Solution {
public:
    int uniquePaths(int m, int n) {
        //定义dp数组
        vector<int> dp(n);
        //初始化dp数组
        for(int i=0;i<n;i++) dp[i]=1;
        for(int j=1;j<m;j++){
            for(int i=1;i<n;i++){
                dp[i] += dp[i-1];
            }
        }
        return dp[n-1];
    }
};

时间复杂度：O(m × n)
空间复杂度：O( n)

题目2：63 不同路径Ⅱ

题目链接：不同路径Ⅱ

对题目的理解

机器人位于m*n的网格中的左上角start,求解走到网格右下角finish的移动路径，但是本题与上题的区别是，网格中有障碍物（障碍物和空位置分别用0和1表示）

动规五部曲

1）dp数组的含义以及下标i的含义

dp[i][j]：从start（0，0）位置到位置（i，j）有多少不同的路径

2)递推公式

因为题目要求只能向右和向下走，所以dp[i][j]只能从紧邻它的正方的格走到，或是紧邻它的正左方的格得到

所以dp[i][j]与dp[i][j-1]有关，只要dp[i][j-1]再向右走一步就可以到达(i,j)的位置

同理，dp[i][j]与dp[i-1][j]有关，只要dp[i-1][j]再向下走一步就可以到达(i,j)的位置

但是本题有障碍物，所以加上判断条件，在没有障碍物的地点，此进行递推，

if(obs[i][j]==0) dp[i][j] = dp[i-1][j] + dp[i][j-1]

3）初始化dp数组

第一行：dp[0][j]，(j从0~n变化)，代表从起始位置（0，0）一直向右走，到（0，j），只有1种走法，遇到障碍物，后面就不进行初始化了，因为走不到后面的位置了

第一列：dp[i][0]，（i从0~m变化）代表从起始位置(0，0)一直向下走，到（i，0），只有一种走法，遇到障碍物，后面就不进行初始化了，因为走不到后面的位置了

for(int i=0;i<m&&obs[i][0]==0;i++) dp[i][0]=1

for(int j=0;j<n&&obs[0][j]==0;j++) dp[0][j] = 1

4）遍历顺序

从左往右遍历，从上往下遍历，因为dp[i][j]与 dp[i-1][j](上)和dp[i][j-1](左)有关

5）打印dp数组

注意：起始位置有障碍，终止位置有障碍，直接return 0

代码

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        if(obstacleGrid[0][0]==1) return 0;
        if(obstacleGrid[m-1][n-1]==1) return 0;
        //定义dp数组
        vector<vector<int>> dp(m,vector<int>(n,0));
        //初始化数组
        for(int i=0;i<m && obstacleGrid[i][0]==0;i++) dp[i][0]=1;
        for(int j=0;j<n && obstacleGrid[0][j]==0;j++) dp[0][j]=1;
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(obstacleGrid[i][j]==0){
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};