https://leetcode.com/problems/dungeon-game/description/
- 乍一看铝侵，這個問題和"Maximum/Minimum Path Sum"問題很相似堕澄。然而侠讯，具有全局最大HP（生命值）收益的路徑并不一定可以保證最小的初始HP王浴，因為題目中具有限制條件：HP不能≤0榆综。例如您觉，考慮下面的兩條路徑：0 -> -300 -> 310 -> 0 和 0 -> -1 -> 2 -> 0。這兩條路徑的凈HP收益分別是-300 + 310 = 10 與 -1 + 2 = 1拖吼。第一條路徑的凈收益更高，但是它所需的初始HP至少是301这吻，才能抵消第二個房間的-300HP損失吊档，而第二條路徑只需要初始HP為2就可以了。
- 幸運的是唾糯，這個問題可以通過“table-filling”（表格填充）動態(tài)規(guī)劃算法解決怠硼，與其他"grid walking"（格子行走）問題類似：
思路
騎士向右或者向下走鬼贱，如果血量小于0就死掉了，這會使得計算變得很復(fù)雜香璃。如果我們從后往前看这难，從最后一個格子逆推回去，就會簡單很多葡秒。每個格子可以是它下方或者右方的格子逆推回來姻乓，那么要讓其實的血量最少，我們則要保證逆推的每一步都處于活著的狀態(tài)眯牧，且選擇活著的狀態(tài)中蹋岩，血量較小的那一種。假設(shè)health[i][j]表示點i和j的血量学少，dungeon[i][j]表示走到i和j要扣除的血量剪个。如果從下方逆推回上面，則血量為
health[i][j] = health[i + 1][j] - dungeon[i][j]版确，但要考慮扣囊，如果該格子如果扣血扣太多的，則這樣相減血量會成為負(fù)數(shù)绒疗，說明騎士就已經(jīng)死了侵歇，這樣的話我們要保證扣完血后騎士還活著，則該點的血量就應(yīng)該為1忌堂。所以其實是health[i][j] = Math.max(health[i + 1][j] - dungeon[i][j], 1)盒至。同理，如果從右邊逆推回來士修，則health[i][j] = Math.max(health[i][j] - dungeon[i][j + 1], 1)枷遂。最后，我們在這兩個逆推的值中棋嘲，取較小的那個就行了酒唉。
注意
- 由于最下面一行和最右面一列比較特殊，只有一種逆推方法沸移，所以我們要先單獨處理一下痪伦。
- 最右下角那個節(jié)點沒有待逆推的節(jié)點，所以我們假設(shè)其逆推節(jié)點的血量為1雹锣。
public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
if(dungeon == null || dungeon.length == 0) return 1;
int m = dungeon.length;
int n = dungeon[0].length;
int[][] health = new int[m][n];
health[m - 1][n - 1] = Math.max(1 - dungeon[m - 1][n - 1], 1);
// 逆推最后一列的血量
for(int i = m - 2; i >= 0; i--){
health[i][n - 1] = Math.max(health[i + 1][n - 1] - dungeon[i][n - 1], 1);
}
// 逆推最后一行的血量
for(int j = n - 2; j >= 0; j--){
health[m - 1][j] = Math.max(health[m - 1][j + 1] - dungeon[m - 1][j], 1);
}
// 對于每個節(jié)點网沾，從其下方和右方逆推回來
for(int i = m - 2; i >= 0; i--){
for(int j = n - 2; j >= 0; j--){
int down = Math.max(health[i + 1][j] - dungeon[i][j], 1);
int right = Math.max(health[i][j + 1] - dungeon[i][j], 1);
health[i][j] = Math.min(down, right);
}
}
return health[0][0];
}
}
