前置知識(shí)
參考前文
參考文章：
LeetCode刷題筆記【29】：動(dòng)態(tài)規(guī)劃專(zhuān)題-1（斐波那契數(shù)、爬樓梯、使用最小花費(fèi)爬樓梯）
62.不同路徑
題目描述
LeetCode鏈接：https://leetcode.cn/problems/unique-paths/description/
解題思路
動(dòng)態(tài)規(guī)劃: 創(chuàng)建m×n的數(shù)組, 對(duì)應(yīng)這個(gè)地圖, 數(shù)組val表示有幾種方法可以走到這一格
最開(kāi)始, 第一行和第一列val都是1, 然后依次遍歷更新val
每一格的val是其上和左格子的和
代碼
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> map(m, vector<int>(n));
for(int i=0; i<n; i++){
map[0][i] = 1;
}
for(int i=0; i<m; i++){
map[i][0] = 1;
}
for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
map[i][j] = map[i-1][j] + map[i][j-1];
}
}
return map[m-1][n-1];
}
};
63. 不同路徑 II
題目描述
LeetCode鏈接：https://leetcode.cn/problems/unique-paths-ii/description/
障礙信息傳遞法(比較復(fù)雜)
參考<62. 不同路徑>
動(dòng)態(tài)規(guī)劃, 先把石頭初始化為INT_MAX(并且初始化過(guò)程中前面一個(gè)是INT_MAX, 那他自己也是INT_MAX)
遞推遍歷的過(guò)程中加一個(gè)判斷
① 如果左和上都是INT_MAX, 那么本位置也是INT_MAX
② 如果上/左有一個(gè)是INT_MAX, 那么val是另一個(gè)非INT_MAX的
③ 正常遞推
class Solution {
private:
int maxNum = INT_MAX;
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
for(int i=0; i<obstacleGrid.size(); ++i){
for(int j=0; j<obstacleGrid[0].size(); ++j){
if(obstacleGrid[i][j]==1)
obstacleGrid[i][j] = maxNum;
}
}
if(obstacleGrid[0][0] != maxNum)
obstacleGrid[0][0] = 1;
for(int i=1; i<obstacleGrid[0].size(); ++i){
if(obstacleGrid[0][i-1]==maxNum)
obstacleGrid[0][i] = maxNum;
if(obstacleGrid[0][i] != maxNum)
obstacleGrid[0][i] = 1;
}
for(int i=1; i<obstacleGrid.size(); ++i){
if(obstacleGrid[i-1][0]==maxNum)
obstacleGrid[i][0] = maxNum;
if(obstacleGrid[i][0] != maxNum)
obstacleGrid[i][0] = 1;
}
for(int i=1; i<obstacleGrid.size(); ++i){
for(int j=1; j<obstacleGrid[0].size(); ++j){
if(obstacleGrid[i][j]==maxNum)
continue;
int left = obstacleGrid[i-1][j];
int over = obstacleGrid[i][j-1];
if(left==maxNum && over==maxNum){
obstacleGrid[i][j] = maxNum;
}else if(left==maxNum || over==maxNum){
obstacleGrid[i][j] = min(left, over);
}else{
obstacleGrid[i][j] = left + over;
}
}
}
if(obstacleGrid.back().back()==maxNum)
return 0;
else
return obstacleGrid.back().back();
}
};
這樣做相當(dāng)于是如果在過(guò)程中遇到了障礙物, 就把這個(gè)障礙物的信息繼續(xù)往后傳遞, 一直到遍歷結(jié)束.
這樣當(dāng)然可以解決問(wèn)題, 并且整個(gè)遍歷的過(guò)程也非常符合手工推導(dǎo)的直覺(jué).
但是落實(shí)到代碼層面的話, 不管是初始化的過(guò)程, 推導(dǎo)的過(guò)程, 還是最后得出結(jié)果的步驟, 都會(huì)變得更加繁瑣, 不夠簡(jiǎn)潔.
被障礙物阻擋后直接清空計(jì)數(shù)法(更簡(jiǎn)潔)
另一種思路: 將obstacleGrid試做參考, 自己新建一個(gè)map;
在遍歷過(guò)程中如果當(dāng)前位置有障礙物, 那么就直接給當(dāng)前位置賦值0(清空前面的累計(jì)計(jì)數(shù));
其含義也可以理解為: 有0種方法可以走到當(dāng)前位置.
在初始化時(shí), 遇到障礙物, 直接停止初始化.
class Solution {
private:
int maxNum = INT_MAX;
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m=obstacleGrid.size();
int n=obstacleGrid[0].size();
if(obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1)//一些trick, 起點(diǎn)終點(diǎn)處有障礙物就沒(méi)法走了
return 0;
vector<vector<int>> map(m, vector<int>(n));
for(int i=0; i<n; i++){
if(obstacleGrid[0][i]==1)
break;
map[0][i] = 1;
}
for(int i=0; i<m; i++){
if(obstacleGrid[i][0]==1)
break;
map[i][0] = 1;
}
for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
if(obstacleGrid[i][j]==1)
continue;
map[i][j] = map[i-1][j] + map[i][j-1];
}
}
return map[m-1][n-1];
}
};
總結(jié)
動(dòng)態(tài)規(guī)劃做起來(lái)真的比貪心舒服很多很多, 有邏輯的通暢感覺(jué).
今天第二道題是第一道題的延伸拓展, 我雖然也做出來(lái)了, 但是用程序強(qiáng)行實(shí)現(xiàn)的手工推導(dǎo)思路, 并沒(méi)有貼合dp數(shù)組的定義與實(shí)質(zhì).
導(dǎo)致算法不夠簡(jiǎn)潔有力.
或許以后隨著練習(xí), 可以逐漸加強(qiáng).文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-707098.html
本文參考：
不同路徑
不同路徑 II文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-707098.html
到了這里，關(guān)于LeetCode刷題筆記【30】：動(dòng)態(tài)規(guī)劃專(zhuān)題-2（不同路徑、不同路徑 II）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
