算法訓練之動態規劃（三）

???~~~~~~歡迎光臨知星小度博客空間~~~~~~???

???零星地變得優秀~也能拼湊出星河~???

???我們一起努力成為更好的自己~???

???如果這一篇博客對你有幫助~別忘了點贊分享哦~???

???如果有什么問題可以評論區留言或者私信我哦~???
?????? 個人主頁??????

??????? 接下來這篇博客我們將繼續在題目中使用巧妙的動態規劃思想~準備好了嗎~我們發車去探索奧秘啦~🚗🚗🚗🚗🚗🚗

下降路徑的最小和

這個題目看起來有點嚇人，別怕，接下來我們一步步按照動態規劃的思想來解決這道問題~

分析：

1、狀態表示

??????? 結合這里的題目要求+經驗：我們這里的狀態表示——dp[i][j]為到達該位置的最小路徑和

2、狀態轉移方程

?????? 我們以離【i】【j】位置最近的狀態分析狀態轉移方程（題目要求最多相隔一列）所以有下面的三種情況：

1、到達該位置，可能是從第【i-1】【j】位置向下一步到達的

2、到達該位置，可能是從第【i-1】【j-1】位置向下再向右一步到達的

3、到達該位置，可能是從第【i-1】【j+1】位置向下再向左一步到達的

?????? 所以到達該位置最小路徑和也就是三種情況的最小值再加上當前位置的數據（注意下標映射關系），所以狀態轉移方程也就是：

??????????????? dp[i][j]=min(min(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1]) + nums[i-1][j-1]

3、初始化

??????? 我們可以看到，狀態轉移方程里面有i-1,j-1，j+1當i=0或者j=0或者j=n的時候顯然會出現越界的情況，所以我們需要進行初始化

??????? 結合前面如果不想初始化太麻煩，我們可以多申請一些空間，這里與前面不一樣的是這里是我們這里還有一個j+1，那么我們這里也就可以多申請一行兩列~那么怎么初始化這一行兩列呢？

??????? 我們結合例子來看看：

??????? 我們首先來看看結合我們的邏輯dp[i][j]里面的值在具體的例子中是多少？

????? 我們可以看到第一行就是它本身的值，而第一行是受到我們增加的那一行影響的，所以我們增加的那一行應該全部初始化為0，才不會出錯~接下來看后面的兩行，都是在取上一行三個位置的最小值加上當前位置值得到的，那么旁邊的兩列如果也初始化為0的話，那么邊界找到的最小值就是0了，這并不是數組里面的有效數據~所以為了避免影響，我們也就可以把兩列位置設置成INT_MAX,題目給出數據大小范圍，顯然dp[i][j]是不會超過INT_MAX的，那么我們就可以這樣進行初始化~

??????????????? 第一行初始化為0,剩下的位置初始化為INT_MAX

???????

?

??????? 這種初始化方式還需要注意的是下標的映射關系~

4、填表順序

??????? 我們這里的邏輯是從上面依次推出下面的，所以填表順序是從上向下

5、返回結果

????? 這里返回結果也與我們前面的不一樣，因為它不是一個具體的位置，最小路徑和存在于最后一行，所以我們可以找到dp表最后一行最小值進行返回~

代碼實現：

class Solution 
{
public:int minFallingPathSum(vector<vector<int>>& matrix) {//1、創建dp表int m=matrix.size();int n=matrix[0].size();//多創建一行兩列vector<vector<int>> dp(m+1,vector<int>(n+2,INT_MAX));//最開始就把所有位置初始化為INT_MAX//2、初始化//最開始就把所有位置初始化為INT_MAX了//初始化第一行為0for(int j=0;j<=n+1;j++){dp[0][j]=0;}//3、填表for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1])+matrix[i-1][j-1];//注意下標映射關系}}//4、返回結果//找到最后一行最小值進行返回int ret=dp[m][1];for(int i=2;i<=n;i++){ret=min(ret,dp[m][i]);}return ret;}
};

順利通過~分析之后也就十分清楚了，我們來看看下一道題目~

最小路徑和

我們同樣可以一步步來分析：

1、狀態表示

??????? 結合這里的題目要求+經驗：我們這里的狀態表示——dp[i][j]為到達該位置的最小總和

2、狀態轉移方程

?????? 我們以離【i】【j】位置最近的狀態分析狀態轉移方程（題目要求只能向下或者向右移動）所以有下面的兩種情況：

1、到達該位置，可能是從第【i-1】【j】位置向下一步到達的

2、到達該位置，可能是從第【i】【j-1】位置向右一步到達的

?????? 所以到達該位置最小總和也就是兩種情況的最小值再加上當前位置的數據（注意下標映射關系），所以狀態轉移方程也就是：

??????????????? dp[i][j]=min(dp[i-1][j],dp[i][j-1]) + nums[i-1][j-1]

3、初始化

??????? 我們可以看到，狀態轉移方程里面有i-1,j-1當i=0或者j=0的時候顯然會出現越界的情況，所以我們需要進行初始化

??????? 結合前面如果不想初始化太麻煩，我們可以多申請一些空間，那么我們這里結合經驗也就可以多申請一行一列~那么怎么初始化這一行一列呢？

??????? 我們結合例子來看看：

??????? 我們首先來看看結合我們的邏輯dp[i][j]里面的值在具體的例子中是多少？

????? 我們可以看到除了左上角的數就是它本身的值，其他的值都發生了變化，而左上角的數是受到它上面的位置和左邊的位置影響的，結合狀態轉移方程? dp[i][j]=min(dp[i-1][j],dp[i][j-1]) + nums[i-1][j-1]，所以它上面的位置和左邊的位置應該初始化為0，才不會出錯~接下來看剩下的位置，每一個位置都是在取當前位置上面的位置和左邊的位置的最小值加上當前位置值得到的，那么如果也初始化為0的話，那么邊界找到的最小值就是0了，這并不是數組里面的有效數據~所以為了避免影響，我們也就可以把剩下的設置成INT_MAX,題目給出數據大小范圍，顯然dp[i][j]是不會超過INT_MAX的，那么我們就可以這樣進行初始化~

?????? dp[1][0]=dp[0][1]=0,剩下的位置初始化為INT_MAX

?

??????? 這種初始化方式還需要注意的是下標的映射關系~

4、填表順序

??????? 我們這里的邏輯是從上面依次推出下面的，所以填表順序是從上向下

5、返回結果

???? 右下角的位置就是我們想要的結果，直接返回dp[m][n]就可以了

有了前面題目的鋪墊，相信這道題目就手到擒來了~

代碼實現：

class Solution 
{
public:int minPathSum(vector<vector<int>>& grid) {//1、創建dp表int m=grid.size();int n=grid[0].size();//dp表最開始全部初始化為INT_MAXvector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));//2、初始化dp[0][1]=dp[1][0]=0;//3、填表for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];//注意下標映射關系}}//4、返回結果return dp[m][n];}
};

順利通過~

地下城游戲

一看這題目就有點嚇人，我們同樣按照我們之前的步驟來進行分析：

1、狀態表示

??????? 結合這里的題目要求+經驗：狀態表示一般有兩種方式：

1、以某一個位置為結尾分析：

??????? 我們這里來看看如果我們以【i】【j】位置為結尾來分析的話，認為dp【i】【j】表示的是到該位置的最低健康點數，那么我們可以發現dp【i】【j】不僅僅受到前面位置的影響，還會受到后面位置的影響，這樣就會十分麻煩，所以我們換一種方式~

2、以某一個位置為起點分析：

??????? 我們這里來看看如果我們以【i】【j】位置為起點來分析的話，認為dp【i】【j】表示的是從該位置開始到達指定位置的最低健康點數，那么dp【i】【j】只受到后面位置的影響，這樣就更加方便~

2、狀態轉移方程

?????? 我們以離【i】【j】位置最近的狀態分析狀態轉移方程（題目要求只能向下或者向右移動）所以有下面的兩種情況：

1、以該位置為起點，可能是向下一步到達第【i+1】【j】位置

2、以該位置為起點，可能是向右一步到達第【i】【j+1】位置

?????? 所以dp【i】【j】也就是以該位置為起點，兩種情況的最小值再減去當前位置的數據（這里增加不需要注意下標映射關系），所以狀態轉移方程也就是：

??????????????? dp[i][j]=min(dp[i+1][j],dp[i][j+1]) - nums[i][j]

????????這樣處理之后，還有一種情況就是dp[i][j]是負數了，也就是nums[i][j]很大，那么該位置的最小健康點數只需要是1經過加上nums[i][j]就可以了，所以還需要處理為負數的情況~

??????? dp[i][j]=max(1,dp[i][j])

3、初始化

??????? 我們可以看到，狀態轉移方程里面有i+1,j+1當i=m-1或者j=n-1的時候顯然會出現越界的情況，所以我們需要進行初始化

??????? 結合前面如果不想初始化太麻煩，我們可以多申請一些空間，那么我們這里結合經驗也就可以多申請一行一列~與前面不同的是這里是以【i】【j】位置為起點來分析，所以加的那一行一列在后面，那么怎么初始化這一行一列呢？

??????? 我們結合例子來看看：

??????? 我們首先來看看結合我們的邏輯dp[i][j]里面的值在具體的例子中是多少？

????? 我們可以看到除了右下角的數到達右邊或者下邊那一個位置至少還應該剩下1的健康點數，不能剛好到了就死亡了，所以dp【m-1】【n】=dp【m】【n-1】=1，接下來看剩下的位置，每一個位置都是在取當前位置下面的位置和右邊的位置的最小值加上當前位置值得到的，那么如果也初始化為1的話，那么邊界找到的最小值就是錯誤的~所以為了避免影響，我們也就可以把剩下的設置成INT_MAX,題目給出數據大小范圍，顯然dp[i][j]是不會超過INT_MAX的，那么我們就可以這樣進行初始化~

?????? dp[m-1][n]=dp[m][n-1]=1,剩下的位置初始化為INT_MAX

?

??????? 這種初始化方式還不需要注意下標的映射關系了~因為位置與數組一一對應的~

4、填表順序

??????? 我們這里的邏輯是從下面/右邊依次推出上面/左邊的，所以填表順序是從下向上，從右向左

5、返回結果

???? 左上角的位置就是我們想要的結果，直接返回dp[0][0]就可以了

代碼實現：

class Solution 
{
public:int calculateMinimumHP(vector<vector<int>>& d) {//1、創建dp表int m=d.size();int n=d[0].size();//最開始全部初始化為INT_MAXvector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));//2、初始化dp[m-1][n]=dp[m][n-1]=1;//3、填表//注意填表順序for(int i=m-1;i>=0;i--){for(int j=n-1;j>=0;j--){dp[i][j]=min(dp[i+1][j],dp[i][j+1])-d[i][j];//處理為負的情況dp[i][j]=max(1,dp[i][j]);}}//4、返回結果return dp[0][0];}
};