資訊專欄INFORMATION COLUMN
摘要：動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間遞歸棧思路騎士向右或者向下走，如果血量小于就死掉了，這會(huì)使得計(jì)算變得很復(fù)雜。假設(shè)表示點(diǎn)和的血量，表示走到和要扣除的血量。最右下角那個(gè)節(jié)點(diǎn)沒(méi)有待逆推的節(jié)點(diǎn)，所以我們假設(shè)其逆推節(jié)點(diǎn)的血量為。
Dungeon Game
動(dòng)態(tài)規(guī)劃 復(fù)雜度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.
時(shí)間 O(N) 空間 O(N) 遞歸棧
思路騎士向右或者向下走，如果血量小于0就死掉了，這會(huì)使得計(jì)算變得很復(fù)雜。如果我們從后往前看，從最后一個(gè)格子逆推回去，就會(huì)簡(jiǎn)單很多。每個(gè)格子可以是它下方或者右方的格子逆推回來(lái)，那么要讓其實(shí)的血量最少，我們則要保證逆推的每一步都處于活著的狀態(tài)，且選擇活著的狀態(tài)中，血量較小的那一種。假設(shè)health[i][j]表示點(diǎn)i和j的血量，dungeon[i][j]表示走到i和j要扣除的血量。如果從下方逆推回上面，則血量為health[i][j] = health[i + 1][j] - dungeon[i][j]，但要考慮，如果該格子如果扣血扣太多的，則這樣相減血量會(huì)成為負(fù)數(shù)，說(shuō)明騎士就已經(jīng)死了，這樣的話我們要保證扣完血后騎士還活著，則該點(diǎn)的血量就應(yīng)該為1。所以其實(shí)是health[i][j] = Math.max(health[i + 1][j] - dungeon[i][j], 1)。同理，如果從右邊逆推回來(lái)，則health[i][j] = Math.max(health[i][j] - dungeon[i][j + 1], 1)。最后，我們?cè)谶@兩個(gè)逆推的值中，取較小的那個(gè)就行了。
注意由于最下面一行和最右面一列比較特殊，只有一種逆推方法，所以我們要先多帶帶處理一下。
最右下角那個(gè)節(jié)點(diǎn)沒(méi)有待逆推的節(jié)點(diǎn)，所以我們假設(shè)其逆推節(jié)點(diǎn)的血量為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);
}
// 對(duì)于每個(gè)節(jié)點(diǎn)，從其下方和右方逆推回來(lái)
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];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/64684.html
摘要：為了保證騎士可以最終到達(dá)，我們可以從終點(diǎn)逆向走到起點(diǎn)。為正數(shù)表示是藥水，騎士可以相應(yīng)降低初始血量。為負(fù)數(shù)表明要增加血量來(lái)保證存活。用二維空間來(lái)表示當(dāng)前位置所需的最小血量，不斷向左上方走直到起點(diǎn)。用來(lái)表示當(dāng)前層與下一層。 The demons had captured the princess (P) and imprisoned her in the bottom-right cor...
摘要：題目解答這一題最重要的是把所剩血量初始化血量走這一步消耗的血量這句話讀懂。那么我們假設(shè)是走完后所剩余的血量肯定是大于等于的。如果想存活下來(lái)，最少需要上一步血量，即上一步血量然后分類討論上一步血量的可能性，注意邊界情況的初始化即可。 題目： The demons had captured the princess (P) and imprisoned her in the bottom-...
摘要：腦筋急轉(zhuǎn)彎復(fù)雜度時(shí)間空間思路這題往小說(shuō)可以追溯到小學(xué)奧數(shù)或者腦筋急轉(zhuǎn)彎的書(shū)中，往大說(shuō)可以深究到博弈論。代碼如果一開(kāi)始就是的倍數(shù)，你就輸了，因?yàn)閷?duì)方可以用同樣的策略 Nim Game You are playing the following Nim Game with your friend: There is a heap of stones on the table, each ...
摘要：代碼記錄下當(dāng)前區(qū)域的上界，以便待會(huì)更新下一個(gè)區(qū)域的上界更新下一個(gè)區(qū)域的上界更新下一個(gè)區(qū)域的下界后續(xù)如果要求返回最短跳躍路徑，如何實(shí)現(xiàn)可以使用，并根據(jù)一個(gè)全局最短步數(shù)維護(hù)一個(gè)全局最短路徑，當(dāng)搜索完所有可能后返回這個(gè)全局最短路徑。 Jump Game I 最新解法請(qǐng)見(jiàn)：https://yanjia.me/zh/2019/01/... Given an array of non-negat...
摘要：思路普通解法，遍歷每一個(gè)細(xì)胞求值，用一個(gè)的矩陣存放結(jié)果。求值過(guò)程，稍微分析一下可知，其實(shí)就是按照以下的矩陣進(jìn)行結(jié)果是可數(shù)的。 According to the Wikipedias article: The Game of Life, also knownsimply as Life, is a cellular automaton devised by the Britishmath...
閱讀 1853·2021-11-15 11:37
閱讀 3202·2021-11-04 16:05
閱讀 1990·2021-10-27 14:18
閱讀 2809·2021-08-12 13:30
閱讀 2543·2019-08-29 14:18
閱讀 2155·2019-08-29 13:07
閱讀 2108·2019-08-27 10:54
閱讀 2783·2019-08-26 12:15
