[Leetcode] Dungeon Game 地牢游戲

taoszu 發布于2019-08-14 12:45 / 2202人閱讀

摘要：動態規劃復雜度時間空間遞歸棧思路騎士向右或者向下走，如果血量小于就死掉了，這會使得計算變得很復雜。假設表示點和的血量，表示走到和要扣除的血量。最右下角那個節點沒有待逆推的節點，所以我們假設其逆推節點的血量為。

Dungeon Game

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.

動態規劃 復雜度

時間 O(N) 空間 O(N) 遞歸棧

思路

騎士向右或者向下走，如果血量小于0就死掉了，這會使得計算變得很復雜。如果我們從后往前看，從最后一個格子逆推回去，就會簡單很多。每個格子可以是它下方或者右方的格子逆推回來，那么要讓其實的血量最少，我們則要保證逆推的每一步都處于活著的狀態，且選擇活著的狀態中，血量較小的那一種。假設health[i][j]表示點i和j的血量，dungeon[i][j]表示走到i和j要扣除的血量。如果從下方逆推回上面，則血量為health[i][j] = health[i + 1][j] - dungeon[i][j]，但要考慮，如果該格子如果扣血扣太多的，則這樣相減血量會成為負數，說明騎士就已經死了，這樣的話我們要保證扣完血后騎士還活著，則該點的血量就應該為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)。最后，我們在這兩個逆推的值中，取較小的那個就行了。

注意

由于最下面一行和最右面一列比較特殊，只有一種逆推方法，所以我們要先多帶帶處理一下。

最右下角那個節點沒有待逆推的節點，所以我們假設其逆推節點的血量為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);
        }
        // 對于每個節點，從其下方和右方逆推回來
        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];
    }
}

云服務器 GPU云服務器 Dungeon 地牢 LeetCode LeetCode_String

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64684.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
174. Dungeon Game

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

wanglu1209 2019-08-14 14:06 評論0 收藏0
[Leetcode] Nim Game 尼姆游戲

摘要：腦筋急轉彎復雜度時間空間思路這題往小說可以追溯到小學奧數或者腦筋急轉彎的書中，往大說可以深究到博弈論。代碼如果一開始就是的倍數，你就輸了，因為對方可以用同樣的策略 Nim Game You are playing the following Nim Game with your friend: There is a heap of stones on the table, each ...

cartoon 2019-08-14 12:45 評論0 收藏0
[Leetcode] Jump Game 跳躍游戲

摘要：代碼記錄下當前區域的上界，以便待會更新下一個區域的上界更新下一個區域的上界更新下一個區域的下界后續如果要求返回最短跳躍路徑，如何實現可以使用，并根據一個全局最短步數維護一個全局最短路徑，當搜索完所有可能后返回這個全局最短路徑。 Jump Game I 最新解法請見：https://yanjia.me/zh/2019/01/... Given an array of non-negat...

venmos 2019-08-14 12:24 評論0 收藏0
[Leetcode] Game of Life 生命游戲

摘要：思路普通解法，遍歷每一個細胞求值，用一個的矩陣存放結果。求值過程，稍微分析一下可知，其實就是按照以下的矩陣進行結果是可數的。 According to the Wikipedias article: The Game of Life, also knownsimply as Life, is a cellular automaton devised by the Britishmath...

android_c 2019-08-15 13:59 評論0 收藏0