資訊專欄INFORMATION COLUMN
摘要：題目解答這一題最重要的是把所剩血量初始化血量走這一步消耗的血量這句話讀懂。那么我們假設(shè)是走完后所剩余的血量肯定是大于等于的。如果想存活下來，最少需要上一步血量，即上一步血量然后分類討論上一步血量的可能性，注意邊界情況的初始化即可。
題目：
The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0"s) or contain magic orbs that increase the knight"s health (positive integers).
In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Write a function to determine the knight"s minimum initial health so that he is able to rescue the princess.
For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.
-2 (K) -3 3
-5 -10 1
10 30 -5 (P)
Notes:
The knight"s health has no upper bound.
Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
解答：
這一題最重要的是把 ： 所剩血量 ＝ 初始化血量＋走這一步消耗的血量 >= 1 這句話讀懂。那么我們假設(shè)f(i, j)是走完(i, j)后所剩余的血量（f(i, j)肯定是大于等于1的）。如果想存活下來，最少需要f(i, j) ＝ f(上一步血量）＋ dungeon(i, j) >= 1，即：f(i, j) = Math.max(1, f(上一步血量）- dungeon(i, j)). 然后分類討論上一步血量的可能性，注意邊界情況的初始化即可。
程序如下：
public class Solution {
//State: f[i][j] is from (0, 0) to (i, j) the least health the knight should have
//Function: f[i][j] + dungeon[i][j] >= 1 --> f[i][j] = Math.max(1 - dungeon[i][j], 1);
//Intialize: f[i][n - 1] = Math.max(1 - f[i + 1][n - 1], 1), f[m - 1][i] = math.max(i - f[m - 1][i + 1], 1);
//Result: f[0][0];
public int calculateMinimumHP(int[][] dungeon) {
if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) {
return 0;
}
int m = dungeon.length, n = dungeon[0].length;
int[][] f = new int[m][n];
//初始化最后一步的血量要求
f[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]);
//最后一列格子的初始血量
for (int i = m - 2; i >= 0; i--) {
f[i][n - 1] = Math.max(1, f[i + 1][n - 1] - dungeon[i][n - 1]);
}
//最后一排格子的初始血量
for (int j = n - 2; j >= 0; j--) {
f[m - 1][j] = Math.max(1, f[m - 1][j + 1] - dungeon[m - 1][j]);
}
//可以從右邊或者下邊得到當(dāng)前格子的最小初始血量
for (int i = m - 2; i >= 0; i--) {
for (int j = n - 2; j >= 0; j--) {
int right = Math.max(1, f[i][j + 1] - dungeon[i][j]);
int down = Math.max(1, f[i + 1][j] - dungeon[i][j]);
f[i][j] = Math.min(right, down);
}
}
return f[0][0];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64812.html
摘要：為了保證騎士可以最終到達(dá)，我們可以從終點(diǎn)逆向走到起點(diǎn)。為正數(shù)表示是藥水，騎士可以相應(yīng)降低初始血量。為負(fù)數(shù)表明要增加血量來保證存活。用二維空間來表示當(dāng)前位置所需的最小血量，不斷向左上方走直到起點(diǎn)。用來表示當(dāng)前層與下一層。 The demons had captured the princess (P) and imprisoned her in the bottom-right cor...
摘要：動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間遞歸棧思路騎士向右或者向下走，如果血量小于就死掉了，這會(huì)使得計(jì)算變得很復(fù)雜。假設(shè)表示點(diǎn)和的血量，表示走到和要扣除的血量。最右下角那個(gè)節(jié)點(diǎn)沒有待逆推的節(jié)點(diǎn)，所以我們假設(shè)其逆推節(jié)點(diǎn)的血量為。 Dungeon Game The demons had captured the princess (P) and imprisoned her in the bottom-r...
摘要：美國亞特蘭大機(jī)房速度怎么樣商家也有提供亞特蘭大機(jī)房。亞特蘭大是美國佐治亞州首府和最大的工商業(yè)城市位于美國東部。這篇文章，我們一起看看亞特蘭大機(jī)房吧。Vultr 美國亞特蘭大機(jī)房速度怎么樣？Vultr 商家也有提供亞特蘭大Atlanta機(jī)房。Atlanta亞特蘭大是美國佐治亞州首府和最大的工商業(yè)城市、位于美國東部。從PING速度看，速度上相對(duì)是不如洛杉磯或者西雅圖等稍微偏西岸機(jī)房的，但是對(duì)于我...
摘要：商家歐洲機(jī)房目前包含英國倫敦荷蘭德國法國四個(gè)機(jī)房。第四英國倫敦機(jī)房配置和讀寫測試第五英國倫敦機(jī)房網(wǎng)絡(luò)媒體支持測試第六英國倫敦機(jī)房路由回程測試總結(jié)，以上是歐洲機(jī)房倫敦機(jī)房的基本性能測試。Vultr 商家歐洲機(jī)房目前包含英國倫敦、荷蘭、德國、法國四個(gè)機(jī)房。一般歐洲機(jī)房適合有需要?dú)W洲IP節(jié)點(diǎn)業(yè)務(wù)需要的，包括我們有需要?dú)W洲外貿(mào)業(yè)務(wù)需要用到歐洲本土的機(jī)房。比如老蔣遇到有不少遠(yuǎn)程操作歐洲亞馬遜業(yè)務(wù)的會(huì)開...
閱讀 1210·2021-11-10 11:35
閱讀 2952·2021-09-24 10:35
閱讀 2976·2021-09-22 15:38
閱讀 2815·2019-08-30 15:43
閱讀 1349·2019-08-29 18:39
閱讀 2592·2019-08-29 15:22
閱讀 2802·2019-08-28 18:17
閱讀 619·2019-08-26 13:37
