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)

一刷
題解：
.就是一個騎士要救公主冯袍，從迷宮坐上到右下滞项，一共需要多少體力。 這里比較明顯的想到了用DP浪册，條件就是，當(i + 1, j) 和(i, j + 1)的值都小于0時扬虚，我們才更新(i叠蝇，j)，否則我們不需要更多的體力涡尘。這樣自右下角dp到左上角就可以了。 其實應該也可以用BFS或者其他的weighted shortest path方法响迂。 也應該可以用滾動數(shù)組來進行dp考抄，留給二刷吧。

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        if(dungeon == null || dungeon.length == 0) return 1;
        
        int m = dungeon.length, n = dungeon[0].length;
        
        for(int i=m-2; i>=0; i--){
            dungeon[i][n-1] += Math.min(dungeon[i+1][n-1], 0); //last col
        }
        
        for(int j=n-2; j>=0; j--){ //last row
            dungeon[m-1][j] += Math.min(dungeon[m-1][j+1], 0);
        }
        
        for(int i=m-2; i>=0; i--){
            for(int j=n-2; j>=0; j--){
                if(Math.max(dungeon[i+1][j], dungeon[i][j+1]) < 0){
                    dungeon[i][j] += Math.max(dungeon[i+1][j], dungeon[i][j+1]);
                }
            }
        }
        
        return dungeon[0][0] >= 0? 1: -dungeon[0][0] + 1;
        
    }
}

二刷
只能從底到上蔗彤。因為是問起點需要多少能量川梅。

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        if(m == 0) return 1;
        int n = dungeon[0].length;
        int[][] dp = new int[m][n];
        dp[m-1][n-1] = Math.min(dungeon[m-1][n-1], 0);
        
        for(int i=m-2;i>=0; i--){
            dp[i][n-1] = Math.min(dp[i+1][n-1], 0) + dungeon[i][n-1];
        }
        
        for(int j = n-2; j>=0; j--){
            dp[m-1][j] = Math.min(dp[m-1][j+1], 0) + dungeon[m-1][j];
        }
        
        for(int i=m-2; i>=0; i--){
            for(int j = n-2; j>=0; j--){
                if(Math.max(dp[i+1][j], dp[i][j+1])<0){
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j+1]) + dungeon[i][j];
                }
                else dp[i][j] = dungeon[i][j];
            }
        }
        
        return dp[0][0]>=0? 1:1-dp[0][0];        
    }
}

方法二，滾動數(shù)組

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        if(m == 0) return 1;
        int n = dungeon[0].length;
        int[] dp = new int[n];
        dp[n-1] = Math.min(dungeon[m-1][n-1], 0);
               
        for(int j = n-2; j>=0; j--){//last row
            dp[j] = Math.min(dp[j+1], 0) + dungeon[m-1][j];
        }
        
        for(int i=m-2; i>=0; i--){
            for(int j = n-1; j>=0; j--){
                if(j==n-1) dp[j] = Math.min(dp[j], 0) + dungeon[i][j];
                else{
                    if(Math.max(dp[j], dp[j+1])<0){
                        dp[j] = Math.max(dp[j], dp[j+1]) + dungeon[i][j];
                    }
                    else dp[j] = dungeon[i][j];
                }
            }
        }
        
        return dp[0]>=0? 1:1-dp[0];        
    }
}

三刷
用dp[i][j]然遏， 如果為負數(shù)贫途， 絕對值表示到達i,j需要的能量

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