力扣174. 地下城游戲

文章目錄

• 力扣174. 地下城游戲
• • 一、題目描述
  • 二、分析
  • 三、完整代碼

一、題目描述

二、分析

• 這個題一看就可以用動態規劃，就需要確定動態規劃的狀態和選擇以及狀態轉移方程

• 如果按照從左上往右下的順序進行動態規劃，對于每一條路徑，我們需要同時記錄兩個狀態。第一個是「從出發點到當前點的路徑和」，第二個是「從出發點到當前點所需的最小初始值」。而這兩個狀態的重要程度相同

• 例如：
  

• 從 (0,0)到 (1,2) 有多條路徑（即動態規劃的選擇），我們取其中最有代表性的兩條：
  

• 綠色路徑「從出發點到當前點的路徑和」為 1，「從出發點到當前點所需的最小初始值」為 3。

• 藍色路徑「從出發點到當前點的路徑和」為 -1，「從出發點到當前點所需的最小初始值」為 2

我們希望「從出發點到當前點的路徑和」盡可能大，而「從出發點到當前點所需的最小初始值」盡可能小。這兩條路徑各有優劣。

• 在上圖中，我們知道應該選取綠色路徑，因為藍色路徑的路徑和太小，使得藍色路徑需要增大初始值到 4 才能走到終點，而綠色路徑只要 3 點初始值就可以直接走到終點。

• 但是如果把終點的 -2 換為 0，藍色路徑只需要初始值 2，綠色路徑仍然需要初始值 3，最優決策就變成藍色路徑了。

• 因此，如果按照從左上往右下的順序進行動態規劃，我們無法直接確定到達 (1,2) 的方案，因為動態規劃的兩個狀態無論怎么選擇都在相互影響。也就是說，這樣的動態規劃是不滿足其自身的特性「無后效性」的。

• 所以此時我們需要從后往前思考：我：公主，你自殺吧，我走不過去。公主：傻屌，起點等著，我去找你！

• 定義dp函數：

int dp(vector<vector<int>>& dungeon, int i, int j);

• dp函數的定義：

• 從dungeon[i][j]到達終點（右下角）所需的最少生命值是dp(dungeon, i, j)。

• 那么可以這樣寫代碼

int calculateMinimumHP(vector<vector<int>>& dungeon) {// 我們想計算左上角到右下角所需的最小生命值return dp(dungeon, 0, 0); }int dp(vector<vector<int>>& dungeon, int i, int j) {int m = dungeon.size();int n = dungeon[0].size();// base caseif (i == m - 1 && j == n - 1) {return dungeon[i][j] >= 0 ? 1 : 1 - dungeon[i][j];}... }

• 根據新的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，意味著走到dungeon[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) ) - dungeon[i][j];dp(i, j) = ret <= 0 ? 1 : ret;

三、完整代碼

• dp函數

class Solution { public:int dp(vector<vector<int>>& dungeon, int i, int j, vector<vector<int>>& dict) {//代表走到終點，當前只需判斷終點坐標值的大小。如果為正，騎士走到這里至少需要//1滴血（小于1滴血騎士就掛了），如果為負，那么騎士走到這里至少需要(abs(負) + 1)//滴血，abs(負)是為了補回來， + 1是為了讓騎士不死//if (i == dungeon.size() - 1 && j == dungeon[0].size() - 1) {return dungeon[i][j] > 0 ? 1 : 1 - dungeon[i][j];}//代表越界情況：因為每次求的是下方和右方的最小值，所以返回max，避免影響if (i == dungeon.size() || j == dungeon[0].size()) {return INT_MAX;}//備忘錄if (dict[i][j] != -1) {return dict[i][j];}//知道dp(dungeon, i + 1, j, dict)和dp(dungeon, i, j + 1, dict)，那么//肯定選著需要血最少的int ret = min(dp(dungeon, i + 1, j, dict), dp(dungeon, i, j + 1, dict)) - dungeon[i][j];//判斷結果，原理見博客dict[i][j] = (ret <= 0 ? 1 : ret);return dict[i][j];}int calculateMinimumHP(vector<vector<int>>& dungeon) {if(dungeon.empty() || dungeon[0].empty()) {return 0;} vector<vector<int>> dict(dungeon.size(), vector<int>(dungeon[0].size(), -1));return dp(dungeon, 0, 0, dict);} };

• dp數組

class Solution { public:int calculateMinimumHP(vector<vector<int>>& dungeon) {if(dungeon.empty() || dungeon[0].empty()) {return 0;} int n = dungeon.size(), m = dungeon[0].size();vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));dp[n][m - 1] = dp[n - 1][m] = 1;for(int i = n - 1; i >= 0; --i) {for(int j = m - 1; j >= 0; --j) {int ret = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];dp[i][j] = ret > 0 ? ret : 1;}}return dp[0][0];} };

總結

以上是生活随笔為你收集整理的力扣174. 地下城游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。