力扣 63 不同路徑②【動規五步法】【dp數組初始化】

力扣 63 不同路徑二② 【動規五步法】

文章目錄

• 力扣 63 不同路徑二② 【動規五步法】
• • 全部刷題與學習記錄
  • 原題目
  • 考查知識點
  • 自己的第一遍解法
  • 好的解法

全部刷題與學習記錄

【C++刷題學習筆記目錄】

【C++百萬并發網絡通信-筆記目錄】

原題目

題目位址：63. 不同路徑 II

考查知識點

dp數組究竟代表什麼意思、dp數組的初始化

自己的第一遍解法

剛開始按照五步法來，結果體會到了弄清楚dp數組意義的重要性，題目要求：

那麼從左上角到右下角将會有多少條不同的路徑？

我在這裡把

dp[i] [j]

定義成了從

（i，j）

到右下角有多少路徑，這跟正确的dp數組意義截然相反。一個沒有障礙的地圖，随着

i，j

的增加，前往右下角的路徑隻會越來越多，但是在我這種定義方式下，

dp[i] [j]

隻會越來越少。正确的dp數組意義應該是：

dp[i] [j]

代表從

(0, 0)

到

(i, j)

有多少路徑。

在改正dp數組的意義後，下面的代碼中因為初始化沒做好（因為存在障礙），導緻代碼魯棒性不高，需要單獨用if語句處理很多情況（比如地圖是

1×1

，

n×1

，

1×n

并且以上情況均需要考慮是否有障礙存在），這樣是十分不好的

好的解法

【代碼随想錄】大佬給出了正确的思路，首先就是正确的dp數組意義；其次，是dp數組的初始化思路。不同于力扣 62 不同路徑【動态規劃五步法】中直接對兩條邊不加區分的賦1，現在出現的問題是如果邊上一旦出現障礙，障礙目前的位置以及之後的位置在dp數組的對應處都應該是0

那麼在兩層for循環，從上到下，從左到右的周遊中，如果目前位置出現障礙，在dp數組的目前位置也要保持0

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        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] == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};
           

參考：

https://mp.weixin.qq.com/s/lhqF0O4le9-wvalptOVOww