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，并把所有元素都初始化為1for(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為列數。

六、收獲：

這道題目是上一道題目的加強版，加入了障礙物，更考驗對初始化操作的熟練度，通過兩道題目的練習，對二維數組的動規有了更深的認識。