[leetcode]174. Dungeon Game

siberiawolf 發(fā)布于2019-08-14 16:52 / 1555人閱讀

摘要：為了保證騎士可以最終到達，我們可以從終點逆向走到起點。為正數(shù)表示是藥水，騎士可以相應(yīng)降低初始血量。為負數(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.

本題為最小路徑。在搜索的時候，保持最小值至少為1。
為了保證騎士可以最終到達，我們可以從終點逆向走到起點。每到一個地方有兩種選擇，向上或者向左。
選擇需要初始血量最小的走法。matrix為正數(shù)表示是藥水，騎士可以相應(yīng)降低初始血量。為負數(shù)表明要增加血量來保證存活。
用二維空間來表示當前位置所需的最小血量，不斷向左上方走直到起點。因為一個點只有兩種走法，血量只與右邊和下邊有關(guān)。
我們可以減少空間到O(2n)。用來表示當前層與下一層。但是我們是逆向走，在dp[j+1]是已經(jīng)是當前層，而dp[j]還停留在下一層未更新。所以我們只需一個O(n)空間就行了。

time: O(n^2), space: O(n)

public class Solution {
    public int calculateMinimumHP(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[] dp = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[n-1] = 1;
        for(int i=m-1;i>=0;i--) {
            for(int j=n-1;j>=0;j--){
                dp[j] = Math.max(1 , Math.min(dp[j],dp[j+1]) - matrix[i][j]);
            }   // dp[j] means go down,  dp[j+1] means go right
        }
        return dp[0];
    }
}

time: O(n^2), space: O(n^2)

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
     
        //init dp table
        int[][] h = new int[m][n];
     
        h[m - 1][n - 1] = Math.max(1 - dungeon[m - 1][n - 1], 1);
     
        //init last col
        for (int i = m - 2; i >= 0; i--) {
                h[i][n - 1] = Math.max(h[i + 1][n - 1] - dungeon[i][n - 1], 1);
        }
     
        //init last row
        for (int j = n - 2; j >= 0; j--) {
                h[m - 1][j] = Math.max(h[m - 1][j + 1] - dungeon[m - 1][j], 1);
        }
     
        //calculate dp table
        for (int i = m - 2; i >= 0; i--) {
                for (int j = n - 2; j >= 0; j--) {
                        int down = Math.max(h[i + 1][j] - dungeon[i][j], 1);
                        int right = Math.max(h[i][j + 1] - dungeon[i][j], 1);
                        h[i][j] = Math.min(right, down);
                }
        }
     
        return h[0][0];
    }