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

62.不同路径：

文档讲解：代码随想录|62.不同路径

视频讲解：https://www.bilibili.com/video/BV1ve4y1x7Eu

状态：已做出

一、题目要求：

一个二维数组里，将(0，0)位置下标作为起点，计算到达最右下角位置的方式一共有多少种。

二、常见错误：

容易把dp数组的初始化设置错误，如果设置的二维数组dp只是初始化一个位置就会出现错误，仔细观察题目就可以得知只能向下向右移动，所以初始化需要对第一行和第一列的所有元素都进行初始化才正确。

三、解题思路：

根据五个步骤来分析，第一个步骤是确定dp数组的含义，dp数组是从(0，0)到(i，j)位置的方法有dp[i][j]种。第二步是确定推导公式，根据题目要求，每次移动只能向右或者向下移动，所以一个位置的到达方式收到上面或者左边的格子影响，那么推导公式就是dp[i][j]=dp[i-1][j]+dp[i][j-1]。第三步则是初始化dp数组，既然格子只能向右或者向下移动，那么第一行和第一列的所有格子到达的方式都只有一种，所以需要初始化第一行和第一列所有元素为1。第四步则是确定循环顺序，根据推导公式，顺序可以一行一行的遍历，循环的i和j都从1开始遍历到结束。最后一步举例出dp正确的元素和代码得出的进行对比既可。

四、代码实现：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>>dp(m, vector<int>(n,1));  //创建二维数组dp，并把所有元素都初始化为1
        
        for(int i=1;i<m;++i) {
            for(int j=1;j<n;++j) {
                dp[i][j]=dp[i][j-1]+dp[i-1][j];   //当前位置的到达方式种类靠左边和上面位置dp值确定
            }
        }
        
        return dp[m-1][n-1];
    }
};

五、代码复杂度：

代码的整体时间复杂度是O(m*n)，因为要遍历二维数组的所有元素。
代码的空间复杂度是O(m*n)，因为需要创建一个m*n大小的二维数组。

六、收获：

之前做的一维数组的动归和这次二维数组在很多地方都有所不同，更加复杂。前面题目一维数组在推导公式上只要考虑前两个元素，这道题目二维数组需要考虑上和左的元素，并且初始化也有很大的区别，一维数组只要对第一个元素初始化，而二维数组去要对第一行和第一列都进行初始化，从一维数组进阶到二维数组的动规，能更加熟练的设置dp数组。

63.不同路径：

文档讲解：代码随想录|63.不用路径ll

视频讲解：https://www.bilibili.com/video/BV1Ld4y1k7c6

状态：已做出

一、题目要求：

要求从下标(0，0)开始，到最右下角的方法有多少种，其中格子有可能会有阻碍。

二、常见错误：

这道题目最容易犯的错误就是初始化第一行和第一列的时候没有把出现障碍后的所有元素都初始化为零，因为第一行或者第一列中途出现了障碍，后面的格子就不可能到达，所以直接初始化为0。

三、解题思路：

五个步骤和上一道题目基本相同，就是第三步初始化有区别，需要对障碍物进行正确处理，将障碍物后面的所有元素都初始化为零就正确了。循环遍历如果出现障碍物，此处的dp就赋值为零。

四、代码实现：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();   //变量m用来记录行数
        int n=obstacleGrid[0].size();  //变量n用来记录列数
        vector<vector<int>>dp(m,vector<int>(n,0));   //创建二维数组dp，先对所有的元素初始化为零
               
        //下面这个循环对第零行进行初始化，遇到障碍物后面的所有dp元素都不改变，为零
        for(int i=0;i<m;++i) {
            if(obstacleGrid[i][0]) break;
            else dp[i][0]=1;
        }
        
        //这里是对第零列的所有元素进行初始化，规则和行的初始化一样
        for(int i=0;i<n;++i) {
            if(obstacleGrid[0][i]) break;
            else dp[0][i]=1;
        }
        
        for(int i=1;i<m;++i) {
            for(int j=1;j<n;++j) {
                if(obstacleGrid[i][j]) continue;   //当遇到障碍物，直接跳过这个位置
                dp[i][j]=dp[i][j-1]+dp[i-1][j];   //不是障碍物就进行赋值
            }
        }
        
        return dp[m-1][n-1];
    }
};

五、代码复杂度：

时间复杂度为O(m*n)，空间复杂度为O(m*n)，m为行数，n为列数。

六、收获：

这道题目是上一道题目的加强版，加入了障碍物，更考验对初始化操作的熟练度，通过两道题目的练习，对二维数组的动规有了更深的认识。