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方法。 也应该可以用滚动数组来进行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];        
    }
}

方法二，滚动数组

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]， 如果为负数， 绝对值表示到达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;
    }
}