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