天天看點

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

力扣 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