前言
幾乎所有的動(dòng)態(tài)規(guī)劃問題大致可分為以下5個(gè)步驟，后續(xù)所有問題分析都將基于此
-
1.、狀態(tài)表示：通常狀態(tài)表示分為基本分為以下兩種，其中更是以第一種為甚。
-
以i為結(jié)尾，dp[i] 表示什么，通常為代求問題（具體依題目而定） -
以i為開始，dp[i]表示什么，通常為代求問題（具體依題目而定）
-
-
2、狀態(tài)轉(zhuǎn)移方程
*以上述的dp[i]意義為以i位置為分界， 通過最近一步來分析和劃分問題，由此來得到一個(gè)有關(guān)dp[i]的狀態(tài)轉(zhuǎn)移方程。 -
3、dp表創(chuàng)建，初始化
- 動(dòng)態(tài)規(guī)劃問題中，如果直接使用狀態(tài)轉(zhuǎn)移方程通常會(huì)伴隨著
越界訪問等風(fēng)險(xiǎn)，所以一般需要初始化。而初始化最重要的兩個(gè)注意事項(xiàng)便是：保證后續(xù)結(jié)果正確，不受初始值影響；下標(biāo)的映射關(guān)系。 - 而
初始化一般分為以下兩種：直接初始化開頭的幾個(gè)值。-
一維空間大小+1，下標(biāo)從1開始；二維增加一行/一列。
- 動(dòng)態(tài)規(guī)劃問題中，如果直接使用狀態(tài)轉(zhuǎn)移方程通常會(huì)伴隨著
-
4、填dp表、填表順序：根據(jù)狀態(tài)轉(zhuǎn)移方程來確定填表順序。
-
5、確定返回值
一、不同路徑1
【題目鏈接】：LCR 098. 不同路徑
【題目】：
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為 “Start” ）。
機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）。
問總共有多少條不同的路徑？
【分析】：
?這是個(gè)二維數(shù)組問題。我們定義dp[i][j]表示機(jī)器人走到下標(biāo)為[i][j]位置時(shí)的總路徑數(shù)。顯然機(jī)器人要走到[i][j]位置，只能從[i][j-1]向右走、[i-1][j]向下走。所以狀態(tài)轉(zhuǎn)移方程為dp[i][j] = dp[i-1][j] + dp[i][j-1]。 但當(dāng)i = 0或j =0時(shí)，顯然狀態(tài)轉(zhuǎn)移方程不適應(yīng)，需要特殊處理。這里我們采用的辦法時(shí)，橫縱都新增一行。然后我們還需將dp[0][1]或dp[1][0]初始化為1。
?接下我僅需從左往右、從上到下依次填表。最后返回結(jié)果即可??！
【代碼實(shí)現(xiàn)】：
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1));//創(chuàng)建dp表
//初始化
dp[1][0] = 1;
//填表
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
dp[i][j] = dp[i -1][j] + dp[i][j - 1];
return dp[m][n];
}
};
二、珠寶的最高價(jià)值
【題目鏈接】：LCR 166. 珠寶的最高價(jià)值
【題目】：
現(xiàn)有一個(gè)記作二維矩陣 frame 的珠寶架，其中 frame[i][j] 為該位置珠寶的價(jià)值。拿取珠寶的規(guī)則為：
只能從架子的左上角開始拿珠寶每次可以移動(dòng)到右側(cè)或下側(cè)的相鄰位置到達(dá)珠寶架子的右下角時(shí)，停止拿取。
注意：珠寶的價(jià)值都是大于 0 的。除非這個(gè)架子上沒有任何珠寶，比如 frame = [[0]]。
【分析】：
?我們可以定義dp[i][j]表示從開始到[i][j]位置所能拿到的珠寶最大價(jià)值。所以要得到dp[i][j]的值，我們只需將dp[i][j-1]和dp[i-1][j]的較大值假設(shè)當(dāng)前下標(biāo)[i][j]的珠寶價(jià)值即可。即動(dòng)態(tài)轉(zhuǎn)移方程為dp[i][j] = max(dp[i-1][j] + dp[i][j-1]) + frame[i][j]。但顯然當(dāng)i=0或j=0時(shí)，需要特殊處理。這里還是采用橫豎都各加一行。需要注意的是此時(shí)下標(biāo)的映射關(guān)系（具體參考代碼）。
?;接下我僅需從左往右、從上到下依次填表。最后返回結(jié)果！！
【代碼實(shí)現(xiàn)】：
class Solution {
public:
int jewelleryValue(vector<vector<int>>& frame) {
int m = frame.size(), n = frame[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] = max(dp[i][j-1], dp[i-1][j]) + frame[i - 1][j - 1];
return dp[m][n];
}
};
三、下降路徑最小和
【題目鏈接】：931. 下降路徑最小和
【題目】：
給你一個(gè) n x n 的 方形 整數(shù)數(shù)組 matrix ，請(qǐng)你找出并返回通過 matrix 的下降路徑 的 最小和 。
下降路徑 可以從第一行中的任何元素開始，并從每一行中選擇一個(gè)元素。在下一行選擇的元素和當(dāng)前行所選元素最多相隔一列（即位于正下方或者沿對(duì)角線向左或者向右的第一個(gè)元素）。具體來說，位置 (row, col) 的下一個(gè)元素應(yīng)當(dāng)是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
【分析】：
?我們定義dp[i][j]表示下降到[i][j]位置時(shí)，下降路徑的最小和。并且題目中已經(jīng)明確表示下降到[i][j]位置有如下三種方式：
?顯然我們?nèi)菀椎玫綘顟B(tài)轉(zhuǎn)移方程為dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i-1][j+1])) + matrix[i-1][j-1]。但又有一個(gè)問題，當(dāng)i=0、j=0、j=n時(shí)，狀態(tài)轉(zhuǎn)移方程會(huì)越界訪問。所以我們給出的辦法時(shí)加1行、加2列。同時(shí)為了不影響后續(xù)填表結(jié)果，我們將第一行初始為0，第1列和第n+1列初始化為INT_MAX(dp[0][1]、dp[0][n+1]除外)。
?接下來從左往右、從上到下依次填表。dp表填好后，最后一行的每個(gè)數(shù)都有可能是結(jié)果。我們需要依次比較，將最后一行的最小值返回！
【代碼實(shí)現(xiàn)】：文章來源地址http://www.zghlxwxcb.cn/news/detail-854914.html
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dp(m+1, vector<int>(n + 2, INT_MAX));
//初始化
for(int j = 0; j < n + 2; j++)
dp[0][j] = 0;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
{
dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i-1][j+1])) + matrix[i-1][j-1];
}
int ret = INT_MAX;
for(int j = 1; j <= n; j++)
ret = min(ret, dp[m][j]);
return ret;
}
};
四、地下城游戲
【題目鏈接】：174. 地下城游戲
【題目】：
惡魔們抓住了公主并將她關(guān)在了地下城 dungeon 的 右下角 。地下城是由 m x n 個(gè)房間組成的二維網(wǎng)格。我們英勇的騎士最初被安置在 左上角 的房間里，他必須穿過地下城并通過對(duì)抗惡魔來拯救公主。
騎士的初始健康點(diǎn)數(shù)為一個(gè)正整數(shù)。如果他的健康點(diǎn)數(shù)在某一時(shí)刻降至 0 或以下，他會(huì)立即死亡。
有些房間由惡魔守衛(wèi)，因此騎士在進(jìn)入這些房間時(shí)會(huì)失去健康點(diǎn)數(shù)（若房間里的值為負(fù)整數(shù)，則表示騎士將損失健康點(diǎn)數(shù)）；其他房間要么是空的（房間里的值為 0），要么包含增加騎士健康點(diǎn)數(shù)的魔法球（若房間里的值為正整數(shù)，則表示騎士將增加健康點(diǎn)數(shù)）。
為了盡快解救公主，騎士決定每次只 向右 或 向下 移動(dòng)一步。
返回確保騎士能夠拯救到公主所需的最低初始健康點(diǎn)數(shù)。
注意：任何房間都可能對(duì)騎士的健康點(diǎn)數(shù)造成威脅，也可能增加騎士的健康點(diǎn)數(shù)，包括騎士進(jìn)入的左上角房間以及公主被監(jiān)禁的右下角房間。
【實(shí)例】：
輸入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
輸出：7
解釋：如果騎士遵循最佳路徑：右 -> 右 -> 下 -> 下 ，則騎士的初始健康點(diǎn)數(shù)至少為 7
【分析】：
?dp問題中我們一般定義dp[i][j]表示從開始到[i][j]位置的待解結(jié)果，即騎士從[0][0]走到[i][j]所需的最低初始健康點(diǎn)數(shù)。但我們發(fā)現(xiàn)[i][j]位置后面的數(shù)據(jù)對(duì)結(jié)果存在影響。例如：dungeon = [[1， 1],[1， -100]]，假設(shè)我們走到了[0][1]位置，此時(shí)dp[0][1]=1。但此時(shí)走到dungeon[1][1]時(shí)，騎士死亡。后面結(jié)果會(huì)對(duì)當(dāng)前數(shù)據(jù)有影響??！因此該思路錯(cuò)誤。
?我們可以定義dp[i][j]表示從[i][j]位置走到結(jié)尾（假設(shè)結(jié)尾下標(biāo)為[m][n]）騎士所需的最低健康點(diǎn)數(shù)。此時(shí)示意圖如下：（各位懂意思就行，手殘畫不了圖）
?所以我們可以得到狀態(tài)轉(zhuǎn)移方程為dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]。但還有兩個(gè)問題：文章來源：http://www.zghlxwxcb.cn/news/detail-854914.html
- 如果dungeon[i][j]非常大，此時(shí)dp[i][j]可能為負(fù)數(shù)。此時(shí)騎士死亡，不符合要求。所以我們要進(jìn)一步處理，
dp[i][j] = max(1, dp[i][j])（即如果dp[i][j]為負(fù)，此時(shí)表示dungeon[i][j]j較大，我們僅需保證騎士到[i][j]位置時(shí)沒有死亡即可） - 如果[i][j]表示結(jié)尾呢？此時(shí)狀態(tài)轉(zhuǎn)移方程不適應(yīng)。我們給出的辦法是，最后一行、和最后一列各增一行。同時(shí)為了保存新增行列對(duì)后續(xù)填dp表不產(chǎn)生影響，我們其中的元素初始化為INT_MAX。同時(shí)為了保證dp[m][n]在是由狀態(tài)轉(zhuǎn)移方程時(shí)填表正確。我們要保證的時(shí)騎士處于[m][n]位置時(shí)還剩1個(gè)健康點(diǎn)數(shù)即可。所以我們將dp[m+1][n]或dp[m][n+1]初始化為1！
【代碼實(shí)現(xiàn)】：
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size(), n = dungeon[0].size();
//創(chuàng)建dp表
vector<vector<int>> dp(m + 1, vector<int>(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];
}
};
到了這里，關(guān)于算法沉淀 —— 動(dòng)態(tài)規(guī)劃篇（路徑問題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
