讀完本文,可以去力扣解決如下題目:174.地下城遊戲(Hard)
「魔塔」是一款經典的地牢類遊戲,碰怪物要掉血,吃血瓶能加血,你要收集鑰匙,一層一層上樓,最後救出美麗的公主。
現在手機上仍然可以玩這個遊戲:
嗯,相信這款遊戲承包了不少人的童年回憶,記得小時候,一個人拿著遊戲機玩,兩三個人圍在左右指手畫腳,這導致玩遊戲的人體驗極差,而左右的人異常快樂
力扣第 174 題是一道類似的題目,我簡單描述一下:
輸入一個存儲著整數的二維數組grid,如果grid[i][j] > 0,說明這個格子裝著血瓶,經過它可以增加對應的生命值;如果grid[i][j] == 0,則這是一個空格子,經過它不會發生任何事情;如果grid[i][j] < 0,說明這個格子有怪物,經過它會損失對應的生命值。
現在你是一名騎士,將會出現在最上角,公主被困在最右下角,你只能向右和向下移動,請問騎士的初始生命值至少為多少,才能成功救出公主?
換句話說,就是問你至少需要多少初始生命值,能夠讓騎士從最左上角移動到最右下角,且任何時候生命值都要大於 0。
函數籤名如下:
int calculateMinimumHP(int[][] grid);比如題目給我們舉的例子,輸入如下一個二維數組grid,用K表示騎士,用P表示公主:
算法應該返回 7,也就是說騎士的初始生命值至少為 7 時才能成功救出公主,行進路線如圖中的箭頭所示。
上篇文章 最小路徑和 寫過類似的問題,問你從左上角到右下角的最小路徑和是多少。
我們做算法題一定要嘗試舉一反三,感覺今天這道題和最小路徑和有點關係對吧?
想要最小化騎士的初始生命值,是不是意味著要最大化騎士行進路線上的血瓶?是不是相當於求「最大路徑和」?是不是可以直接套用計算「最小路徑和」的思路?
但是稍加思考,發現這個推論並不成立,吃到最多的血瓶,並不一定就能獲得最小的初始生命值。
比如如下這種情況,如果想要吃到最多的血瓶獲得「最大路徑和」,應該按照下圖箭頭所示的路徑,初始生命值需要 11:
但也很容易看到,正確的答案應該是下圖箭頭所示的路徑,初始生命值只需要 1:
所以,關鍵不在於吃最多的血瓶,而是在於如何損失最少的生命值。
這類求最值的問題,肯定要藉助動態規劃技巧,要合理設計dp數組/函數的定義。類比前文 最小路徑和問題,dp函數籤名肯定長這樣:
int dp(int[][] grid, int i, int j);但是這道題對dp函數的定義比較有意思,按照常理,這個dp函數的定義應該是:
從左上角(grid[0][0])走到grid[i][j]至少需要dp(grid, i, j)的生命值。
這樣定義的話,base case 就是i, j都等於 0 的時候,我們可以這樣寫代碼:
int calculateMinimumHP(int[][] grid) { int m = grid.length; int n = grid[0].length; // 我們想計算左上角到右下角所需的最小生命值 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:為了簡潔,之後dp(grid, i, j)就簡寫為dp(i, j),大家理解就好。
接下來我們需要找狀態轉移了,還記得如何找狀態轉移方程嗎?我們這樣定義dp函數能否正確進行狀態轉移呢?
我們希望dp(i, j)能夠通過dp(i-1, j)和dp(i, j-1)推導出來,這樣就能不斷逼近 base case,也就能夠正確進行狀態轉移。
具體來說,「到達A的最小生命值」應該能夠由「到達B的最小生命值」和「到達C的最小生命值」推導出來:
但問題是,能推出來麼?實際上是不能的。
因為按照dp函數的定義,你只知道「能夠從左上角到達B的最小生命值」,但並不知道「到達B時的生命值」。
「到達B時的生命值」是進行狀態轉移的必要參考,我給你舉個例子你就明白了,假設下圖這種情況:
你說這種情況下,騎士救公主的最優路線是什麼?
顯然是按照圖中藍色的線走到B,最後走到A對吧,這樣初始血量只需要 1 就可以;如果走黃色箭頭這條路,先走到C然後走到A,初始血量至少需要 6。
為什麼會這樣呢?騎士走到B和C的最少初始血量都是 1,為什麼最後是從B走到A,而不是從C走到A呢?
因為騎士走到B的時候生命值為 11,而走到C的時候生命值依然是 1。
如果騎士執意要通過C走到A,那麼初始血量必須加到 6 點才行;而如果通過B走到A,初始血量為 1 就夠了,因為路上吃到血瓶了,生命值足夠抗A上面怪物的傷害。
這下應該說的很清楚了,再回顧我們對dp函數的定義,上圖的情況,算法只知道dp(1, 2) = dp(2, 1) = 1,都是一樣的,怎麼做出正確的決策,計算出dp(2, 2)呢?
所以說,我們之前對dp數組的定義是錯誤的,信息量不足,算法無法做出正確的狀態轉移。
正確的做法需要反向思考,依然是如下的dp函數:
int dp(int[][] grid, int i, int j);但是我們要修改dp函數的定義:
從grid[i][j]到達終點(右下角)所需的最少生命值是dp(grid, i, j)。
那麼可以這樣寫代碼:
int calculateMinimumHP(int[][] grid) { // 我們想計算左上角到右下角所需的最小生命值 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; } ...}根據新的dp函數定義和 base case,我們想求dp(0, 0),那就應該試圖通過dp(i, j+1)和dp(i+1, j)推導出dp(i, j),這樣才能不斷逼近 base case,正確進行狀態轉移。
具體來說,「從A到達右下角的最少生命值」應該由「從B到達右下角的最少生命值」和「從C到達右下角的最少生命值」推導出來:
能不能推導出來呢?這次是可以的,假設dp(0, 1) = 5, dp(1, 0) = 4,那麼可以肯定要從A走向C,因為 4 小於 5 嘛。
那麼怎麼推出dp(0, 0)是多少呢?
假設A的值為 1,既然知道下一步要往C走,且dp(1, 0) = 4意味著走到grid[1][0]的時候至少要有 4 點生命值,那麼就可以確定騎士出現在A點時需要 4 - 1 = 3 點初始生命值,對吧。
那如果A的值為 10,落地就能撿到一個大血瓶,超出了後續需求,4 - 10 = -6 意味著騎士的初始生命值為負數,這顯然不可以,騎士的生命值小於 1 就掛了,所以這種情況下騎士的初始生命值應該是 1。
綜上,狀態轉移方程已經推出來了:
int res = min( dp(i + 1, j), dp(i, j + 1)) - grid[i][j];dp(i, j) = res <= 0 ? 1 : res;根據這個核心邏輯,加一個備忘錄消除重疊子問題,就可以直接寫出最終的代碼了:
/* 主函數 */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);}// 備忘錄,消除重疊子問題int[][] memo;/* 定義:從 (i, j) 到達右下角,需要的初始血量至少是多少 */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; } // 避免重複計算 if (memo[i][j] != -1) { return memo[i][j]; } // 狀態轉移邏輯 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];}這就是自頂向下帶備忘錄的動態規劃解法,參考前文 動態規劃套路詳解 很容易就可以改寫成dp數組的迭代解法,這裡就不寫了,讀者可以嘗試自己寫一寫。
這道題的核心是定義dp函數,找到正確的狀態轉移方程,從而計算出正確的答案。
來源:https://mp.weixin.qq.com/s/KD5sS_wbwiWH0rObuya7aA