一、題目解析

?

與62.不同路徑不同的一點是現在網格中有了障礙物，其他的并沒有什么不同?

二、算法解析

1.狀態表示

dp[i][j]表示：到[i,j]位置時，不同的路徑數

2.狀態轉移方程

由于多了障礙物，所以我們要判斷是否遇到障礙物

3.初始化

我們要保證初始化后(1)保證后面填表是正確的(2)下標的映射關系

?

觀察左邊帶圓圈的位置，可以發現在初始化的時候會有越界訪問的問題，所以就有了右圖的解決方法，多加一行一列，并初始化dp[1][0] = 1,為什么只初始化這一個值呢？根據這個圖我們能知道到達dp[1][1]位置時，機器人只有一種方法，同理其他圓圈格子同理，所以只需要初始化dp[1][0]其他位置的值可以計算得出。

這里的映射關系為dp[i][j] == obstacleGrid[i-1][j-1]，即橫縱坐標都-1.

4.填表順序

為了保證填表時所需值存在，從左往右，從上往下，完成填表

5.返回值

由題需要返回到達右下角的方法數，所以返回dp[m][n]

雖然62沒有很大區別，但還是建議自己去上手寫一遍，鏈接：63. 不同路徑 II - 力扣（LeetCode）?

三、代碼示例

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

?

看到最后，如果對您有所幫助還請點贊、收藏，我們下期再見！?

?