62. 不同路徑

62. 不同路徑 - 力扣（LeetCode）

動(dòng)態(tài)規(guī)劃思想第一步：描述狀態(tài)~

dp[i][j]：表示走到i，j位置時(shí)，一共有多少種方法~

動(dòng)態(tài)規(guī)劃思想第二步：狀態(tài)轉(zhuǎn)移方程~

動(dòng)態(tài)規(guī)劃思想第三步：初始化（考慮邊界情況）~

我們通過擴(kuò)充數(shù)組大小可以節(jié)省初始化步驟，不過需要注意下標(biāo)映射關(guān)系~

動(dòng)態(tài)規(guī)劃思想第四步：返回值~

return dp[m][n]

代碼

//62 不同路徑
class Solution
{
public:int uniquePaths(int m, int n){//創(chuàng)建dp表（注意擴(kuò)充）vector<vector<int>> dp(m + 1, vector<int>(n + 1));//細(xì)節(jié)處理dp[0][1] = 1;//從起點(diǎn)開始填表for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){//狀態(tài)轉(zhuǎn)移方程dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}//返回值return dp[m][n];}
};

其實(shí)動(dòng)態(tài)規(guī)劃核心就在于初始化和狀態(tài)轉(zhuǎn)移方程，之所以初始化主要考慮的就是填表邊界情況，把特殊情況考慮了才方便讓dp表一次到位。而狀態(tài)轉(zhuǎn)移方程尤其需要注意最近一步，一定得分析是如何到這一步的~

63. 不同路徑 II

63. 不同路徑 II - 力扣（LeetCode）

其實(shí)本道題跟上一道一樣，唯一要注意的就是判定有無障礙物擋路~

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();vector<vector<int>> dp(m+1,vector<int> (n+1));dp[0][1] = 1;for(int i = 1;i<=m;i++){for(int j = 1;j<=n;j++){//小細(xì)節(jié)：dp表與原數(shù)組是對(duì)應(yīng)不上的 if(obstacleGrid[i-1][j-1]==0){dp[i][j] = dp[i-1][j]+dp[i][j-1];}}}return dp[m][n];}
};

代碼就是在上一道題的基礎(chǔ)上多了一步判斷，由于我們的dp表與原數(shù)組不是同等大小了，所以要記得對(duì)應(yīng)位置的映射。

LCR 166. 珠寶的最高價(jià)值

LCR 166. 珠寶的最高價(jià)值 - 力扣（LeetCode）

也練習(xí)挺多道的了，這道題甚至感覺不用畫圖，就照著前面的套路添加一個(gè)判斷大小即可~?

class Solution {
public:int jewelleryValue(vector<vector<int>>& nums) {//小case,直接秒殺int m = nums.size();int n = nums[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i = 1;i<=m;i++){for(int j = 1;j<=n;j++){dp[i][j] = nums[i-1][j-1]+max(dp[i-1][j],dp[i][j-1]);}}return dp[m][n];}
};

?931. 下降路徑最小和

931. 下降路徑最小和 - 力扣（LeetCode）

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int m = matrix.size();vector<vector<int>> dp(m+1,vector<int>(m+2,INT_MAX));for(int i = 0;i<=m+1;i++){dp[0][i] = 0;}for(int i = 1;i<=m;i++){for(int j = 1;j<=m;j++){dp[i][j] = min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j+1]))+matrix[i-1][j-1];}}int ret = INT_MAX;for(int i = 1;i<=m;i++){ret = min(ret,dp[m][i]);}return ret;}
};

64. 最小路徑和

64. 最小路徑和 - 力扣（LeetCode）

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {//秒殺，分析越來越快了~int m = grid.size();int n = grid[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));dp[0][1] = 0;for(int i = 1;i<=m;i++){for(int j = 1;j<=n;j++){dp[i][j] = min(dp[i][j-1],dp[i-1][j])+grid[i-1][j-1];}}return dp[m][n];}
};

174. 地下城游戲

174. 地下城游戲 - 力扣（LeetCode）

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

感覺講得還不夠好，不夠詳細(xì)，后面再作改善~