174. Dungeon Game

wanglu1209 發布于2019-08-14 14:06 / 2232人閱讀

摘要：題目解答這一題最重要的是把所剩血量初始化血量走這一步消耗的血量這句話讀懂。那么我們假設是走完后所剩余的血量肯定是大于等于的。如果想存活下來，最少需要上一步血量，即上一步血量然后分類討論上一步血量的可能性，注意邊界情況的初始化即可。

題目：

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 這句話讀懂。那么我們假設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]);
        }
        //可以從右邊或者下邊得到當前格子的最小初始血量
        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];
    }
}

GPU云服務器云服務器 Dungeon game webrtc game game 域名備案

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64812.html

[leetcode]174. Dungeon Game

摘要：為了保證騎士可以最終到達，我們可以從終點逆向走到起點。為正數表示是藥水，騎士可以相應降低初始血量。為負數表明要增加血量來保證存活。用二維空間來表示當前位置所需的最小血量，不斷向左上方走直到起點。用來表示當前層與下一層。 The demons had captured the princess (P) and imprisoned her in the bottom-right cor...

siberiawolf 2019-08-14 16:52 評論0 收藏0
[Leetcode] Dungeon Game 地牢游戲

摘要：動態規劃復雜度時間空間遞歸棧思路騎士向右或者向下走，如果血量小于就死掉了，這會使得計算變得很復雜。假設表示點和的血量，表示走到和要扣除的血量。最右下角那個節點沒有待逆推的節點，所以我們假設其逆推節點的血量為。 Dungeon Game The demons had captured the princess (P) and imprisoned her in the bottom-r...

taoszu 2019-08-14 12:45 評論0 收藏0
Vultr機房測評 - Vultr美國亞特蘭大Atlanta機房綜合速度和線路去程回程測

摘要：美國亞特蘭大機房速度怎么樣商家也有提供亞特蘭大機房。亞特蘭大是美國佐治亞州首府和最大的工商業城市位于美國東部。這篇文章，我們一起看看亞特蘭大機房吧。Vultr 美國亞特蘭大機房速度怎么樣？Vultr 商家也有提供亞特蘭大Atlanta機房。Atlanta亞特蘭大是美國佐治亞州首府和最大的工商業城市、位于美國東部。從PING速度看，速度上相對是不如洛杉磯或者西雅圖等稍微偏西岸機房的，但是對于我...

fox_soyoung 2021-08-30 09:47 評論0 收藏0
Vultr機房測評 - Vultr英國倫敦London機房綜合速度和線路去程回程測試

摘要：商家歐洲機房目前包含英國倫敦荷蘭德國法國四個機房。第四英國倫敦機房配置和讀寫測試第五英國倫敦機房網絡媒體支持測試第六英國倫敦機房路由回程測試總結，以上是歐洲機房倫敦機房的基本性能測試。Vultr 商家歐洲機房目前包含英國倫敦、荷蘭、德國、法國四個機房。一般歐洲機房適合有需要歐洲IP節點業務需要的，包括我們有需要歐洲外貿業務需要用到歐洲本土的機房。比如老蔣遇到有不少遠程操作歐洲亞馬遜業務的會開...

lavor 2021-08-23 09:45 評論0 收藏0