動(dòng)態(tài)規(guī)劃算法幫我通關(guān)了魔塔！
來(lái)自公眾號(hào)：labuladong
讀完本文，可以去力扣解決如下題目：
174.地下城游戲（Hard）
「魔塔」是一款經(jīng)典的地牢類游戲，碰怪物要掉血，吃血瓶能加血，你要收集鑰匙，一層一層上樓，最后救出美麗的公主。
現(xiàn)在手機(jī)上仍然可以玩這個(gè)游戲：
嗯，相信這款游戲承包了不少人的童年回憶，記得小時(shí)候，一個(gè)人拿著游戲機(jī)玩，兩三個(gè)人圍在左右指手畫(huà)腳，這導(dǎo)致玩游戲的人體驗(yàn)極差，而左右的人異?？鞓?lè) ??
力扣第 174 題是一道類似的題目，我簡(jiǎn)單描述一下：
輸入一個(gè)存儲(chǔ)著整數(shù)的二維數(shù)組grid，如果grid[i][j] > 0，說(shuō)明這個(gè)格子裝著血瓶，經(jīng)過(guò)它可以增加對(duì)應(yīng)的生命值；如果grid[i][j] == 0，則這是一個(gè)空格子，經(jīng)過(guò)它不會(huì)發(fā)生任何事情；如果grid[i][j] < 0，說(shuō)明這個(gè)格子有怪物，經(jīng)過(guò)它會(huì)損失對(duì)應(yīng)的生命值。
現(xiàn)在你是一名騎士，將會(huì)出現(xiàn)在最上角，公主被困在最右下角，你只能向右和向下移動(dòng)，請(qǐng)問(wèn)騎士的初始生命值至少為多少，才能成功救出公主？
換句話說(shuō)，就是問(wèn)你至少需要多少初始生命值，能夠讓騎士從最左上角移動(dòng)到最右下角，且任何時(shí)候生命值都要大于 0。
函數(shù)簽名如下：
int?calculateMinimumHP(int[][]?grid);
比如題目給我們舉的例子，輸入如下一個(gè)二維數(shù)組grid，用K表示騎士，用P表示公主：
算法應(yīng)該返回 7，也就是說(shuō)騎士的初始生命值至少為 7 時(shí)才能成功救出公主，行進(jìn)路線如圖中的箭頭所示。
上篇文章 最小路徑和 寫(xiě)過(guò)類似的問(wèn)題，問(wèn)你從左上角到右下角的最小路徑和是多少。
我們做算法題一定要嘗試舉一反三，感覺(jué)今天這道題和最小路徑和有點(diǎn)關(guān)系對(duì)吧？
想要最小化騎士的初始生命值，是不是意味著要最大化騎士行進(jìn)路線上的血瓶？是不是相當(dāng)于求「最大路徑和」？是不是可以直接套用計(jì)算「最小路徑和」的思路？
但是稍加思考，發(fā)現(xiàn)這個(gè)推論并不成立，吃到最多的血瓶，并不一定就能獲得最小的初始生命值。
比如如下這種情況，如果想要吃到最多的血瓶獲得「最大路徑和」，應(yīng)該按照下圖箭頭所示的路徑，初始生命值需要 11：
但也很容易看到，正確的答案應(yīng)該是下圖箭頭所示的路徑，初始生命值只需要 1：
所以，關(guān)鍵不在于吃最多的血瓶，而是在于如何損失最少的生命值。
這類求最值的問(wèn)題，肯定要借助動(dòng)態(tài)規(guī)劃技巧，要合理設(shè)計(jì)dp數(shù)組/函數(shù)的定義。類比前文 最小路徑和問(wèn)題，dp函數(shù)簽名肯定長(zhǎng)這樣：
int?dp(int[][]?grid,?int?i,?int?j);
但是這道題對(duì)dp函數(shù)的定義比較有意思，按照常理，這個(gè)dp函數(shù)的定義應(yīng)該是：
從左上角（grid[0][0]）走到grid[i][j]至少需要dp(grid, i, j)的生命值。
這樣定義的話，base case 就是i, j都等于 0 的時(shí)候，我們可以這樣寫(xiě)代碼：
int?calculateMinimumHP(int[][]?grid)?{
????int?m?=?grid.length;
????int?n?=?grid[0].length;
????//?我們想計(jì)算左上角到右下角所需的最小生命值
????return?dp(grid,?m?-?1,?n?-?1);
}
int?dp(int[][]?grid,?int?i,?int?j)?{
????//?base?case
????if?(i?==?0?&&?j?==?0)?{
????????//?保證騎士落地不死就行了
????????return?gird[i][j]?>?0???1?:?-grid[i][j]?+?1;
????}
????...
}
PS：為了簡(jiǎn)潔，之后dp(grid, i, j)就簡(jiǎn)寫(xiě)為dp(i, j)，大家理解就好。
接下來(lái)我們需要找狀態(tài)轉(zhuǎn)移了，還記得如何找狀態(tài)轉(zhuǎn)移方程嗎？我們這樣定義dp函數(shù)能否正確進(jìn)行狀態(tài)轉(zhuǎn)移呢？
我們希望dp(i, j)能夠通過(guò)dp(i-1, j)和dp(i, j-1)推導(dǎo)出來(lái)，這樣就能不斷逼近 base case，也就能夠正確進(jìn)行狀態(tài)轉(zhuǎn)移。
具體來(lái)說(shuō)，「到達(dá)A的最小生命值」應(yīng)該能夠由「到達(dá)B的最小生命值」和「到達(dá)C的最小生命值」推導(dǎo)出來(lái)：
但問(wèn)題是，能推出來(lái)么？實(shí)際上是不能的。
因?yàn)榘凑?code style="font-size: inherit;line-height: inherit;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;color: rgb(233, 105, 0);background: rgb(248, 248, 248);">dp函數(shù)的定義，你只知道「能夠從左上角到達(dá)B的最小生命值」，但并不知道「到達(dá)B時(shí)的生命值」。
「到達(dá)B時(shí)的生命值」是進(jìn)行狀態(tài)轉(zhuǎn)移的必要參考，我給你舉個(gè)例子你就明白了，假設(shè)下圖這種情況：
你說(shuō)這種情況下，騎士救公主的最優(yōu)路線是什么？
顯然是按照?qǐng)D中藍(lán)色的線走到B，最后走到A對(duì)吧，這樣初始血量只需要 1 就可以；如果走黃色箭頭這條路，先走到C然后走到A，初始血量至少需要 6。
為什么會(huì)這樣呢？騎士走到B和C的最少初始血量都是 1，為什么最后是從B走到A，而不是從C走到A呢？
因?yàn)轵T士走到B的時(shí)候生命值為 11，而走到C的時(shí)候生命值依然是 1。
如果騎士執(zhí)意要通過(guò)C走到A，那么初始血量必須加到 6 點(diǎn)才行；而如果通過(guò)B走到A，初始血量為 1 就夠了，因?yàn)槁飞铣缘窖苛?，生命值足夠?code style="font-size: inherit;line-height: inherit;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;color: rgb(233, 105, 0);background: rgb(248, 248, 248);">A上面怪物的傷害。
這下應(yīng)該說(shuō)的很清楚了，再回顧我們對(duì)dp函數(shù)的定義，上圖的情況，算法只知道dp(1, 2) = dp(2, 1) = 1，都是一樣的，怎么做出正確的決策，計(jì)算出dp(2, 2)呢？
所以說(shuō)，我們之前對(duì)dp數(shù)組的定義是錯(cuò)誤的，信息量不足，算法無(wú)法做出正確的狀態(tài)轉(zhuǎn)移。
正確的做法需要反向思考，依然是如下的dp函數(shù)：
int?dp(int[][]?grid,?int?i,?int?j);
但是我們要修改dp函數(shù)的定義：
從grid[i][j]到達(dá)終點(diǎn)（右下角）所需的最少生命值是dp(grid, i, j)。
那么可以這樣寫(xiě)代碼：
int?calculateMinimumHP(int[][]?grid)?{
????//?我們想計(jì)算左上角到右下角所需的最小生命值
????return?dp(grid,?0,?0);
}
int?dp(int[][]?grid,?int?i,?int?j)?{
????int?m?=?grid.length;
????int?n?=?grid[0].length;
????//?base?case
????if?(i?==?m?-?1?&&?j?==?n?-?1)?{
????????return?grid[i][j]?>=?0???1?:?-grid[i][j]?+?1;
????}
????...
}
根據(jù)新的dp函數(shù)定義和 base case，我們想求dp(0, 0)，那就應(yīng)該試圖通過(guò)dp(i, j+1)和dp(i+1, j)推導(dǎo)出dp(i, j)，這樣才能不斷逼近 base case，正確進(jìn)行狀態(tài)轉(zhuǎn)移。
具體來(lái)說(shuō)，「從A到達(dá)右下角的最少生命值」應(yīng)該由「從B到達(dá)右下角的最少生命值」和「從C到達(dá)右下角的最少生命值」推導(dǎo)出來(lái)：
能不能推導(dǎo)出來(lái)呢？這次是可以的，假設(shè)dp(0, 1) = 5, dp(1, 0) = 4，那么可以肯定要從A走向C，因?yàn)?4 小于 5 嘛。
那么怎么推出dp(0, 0)是多少呢？
假設(shè)A的值為 1，既然知道下一步要往C走，且dp(1, 0) = 4意味著走到grid[1][0]的時(shí)候至少要有 4 點(diǎn)生命值，那么就可以確定騎士出現(xiàn)在A點(diǎn)時(shí)需要 4 - 1 = 3 點(diǎn)初始生命值，對(duì)吧。
那如果A的值為 10，落地就能撿到一個(gè)大血瓶，超出了后續(xù)需求，4 - 10 = -6 意味著騎士的初始生命值為負(fù)數(shù)，這顯然不可以，騎士的生命值小于 1 就掛了，所以這種情況下騎士的初始生命值應(yīng)該是 1。
綜上，狀態(tài)轉(zhuǎn)移方程已經(jīng)推出來(lái)了：
int?res?=?min(
????dp(i?+?1,?j),
????dp(i,?j?+?1)
)?-?grid[i][j];
dp(i,?j)?=?res?<=?0???1?:?res;
根據(jù)這個(gè)核心邏輯，加一個(gè)備忘錄消除重疊子問(wèn)題，就可以直接寫(xiě)出最終的代碼了：
/*?主函數(shù)?*/
int?calculateMinimumHP(int[][]?grid)?{
????int?m?=?grid.length;
????int?n?=?grid[0].length;
????//?備忘錄中都初始化為?-1
????memo?=?new?int[m][n];
????for?(int[]?row?:?memo)?{
????????Arrays.fill(row,?-1);
????}
????return?dp(grid,?0,?0);
}
//?備忘錄，消除重疊子問(wèn)題
int[][]?memo;
/*?定義：從?(i, j)?到達(dá)右下角，需要的初始血量至少是多少?*/
int?dp(int[][]?grid,?int?i,?int?j)?{
????int?m?=?grid.length;
????int?n?=?grid[0].length;
????//?base?case
????if?(i?==?m?-?1?&&?j?==?n?-?1)?{
????????return?grid[i][j]?>=?0???1?:?-grid[i][j]?+?1;
????}
????if?(i?==?m?||?j?==?n)?{
????????return?Integer.MAX_VALUE;
????}
????//?避免重復(fù)計(jì)算
????if?(memo[i][j]?!=?-1)?{
????????return?memo[i][j];
????}
????//?狀態(tài)轉(zhuǎn)移邏輯
????int?res?=?Math.min(
????????????dp(grid,?i,?j?+?1),
????????????dp(grid,?i?+?1,?j)
????????)?-?grid[i][j];
????//?騎士的生命值至少為?1
????memo[i][j]?=?res?<=?0???1?:?res;
????return?memo[i][j];
}
這就是自頂向下帶備忘錄的動(dòng)態(tài)規(guī)劃解法，參考前文 動(dòng)態(tài)規(guī)劃套路詳解 很容易就可以改寫(xiě)成dp數(shù)組的迭代解法，這里就不寫(xiě)了，讀者可以嘗試自己寫(xiě)一寫(xiě)。
這道題的核心是定義dp函數(shù)，找到正確的狀態(tài)轉(zhuǎn)移方程，從而計(jì)算出正確的答案。
推薦閱讀：
完全整理 | 365篇高質(zhì)技術(shù)文章目錄整理
專注服務(wù)器后臺(tái)技術(shù)棧知識(shí)總結(jié)分享
歡迎關(guān)注交流共同進(jìn)步