leetcode 174. Dungeon Game (地牢游戏）

题意大致如下：
有个地牢，公主（P）被关在右下角格子里，骑士（K）会从左上角格子进入营救公主，骑士初始有一个血量。每个格子中可能有怪兽，会减掉骑士的血量（负数），也可能有药水，会增加骑士的血量（正数）。骑士的血量一旦减到0或者0以下，就会挂掉。问骑士能顺利营救公主所需要的初始血量。骑士每次只会向右边或者下面移动

需要注意的是在左上角的格子和右下角的格子，也就是骑士刚进入的格子和公主所在的格子也可能会减少血量。

思路：
从公主所在的格子倒推回初始的格子，
因为骑士每次只会向右边或者下边移动，所以只需要取右边和下边的较小值即可。
右边界的情况只需要看下边的格子，下边界只需要看右边的格子。

但是需要注意几点：

1. 骑士的血量一旦到达0或者0以下会挂掉，所以要保证每个格子的血量至少是1.
2. 营救到公主的最后一刻，即到达右下角的时候也要保证活着见到公主，所以初始化最后一格血量的时候要保证至少是1
3. 需要的血量也就是至少是1的血量 减去 地牢中的数字

    public int calculateMinimumHP(int[][] dungeon) {
        if(dungeon == null || dungeon.length == 0) {
            return 0;
        }
        
        int m = dungeon.length;
        int n = dungeon[0].length;
        
        int[][] dp = new int[m][n];
        //营救到公主的最后一刻也要保证血量至少是1
        dp[m-1][n-1] = Math.max(-dungeon[m-1][n-1] + 1, 1);
        
        //初始化右边界
        for(int i = m-2; i >= 0; i--) {
            dp[i][n-1] = Math.max(dp[i+1][n-1] - dungeon[i][n-1], 1);
        }
        //初始化下边界
        for(int j = n-2; j >= 0; j--) {
            dp[m-1][j] = Math.max(dp[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--) {
                //思路是取右边和下边的较小值，同时保证至少是1
                //但是为了减少计算量，取了简化版本
                //int right = Math.max(dp[i][j+1] - dungeon[i][j], 1);
                //int down = Math.max(dp[i+1][j] - dungeon[i][j], 1);
                //dp[i][j] = Math.min(right, down);
                dp[i][j] = Math.min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j];
                dp[i][j] = Math.max(dp[i][j], 1);
            }
        }
        
        return dp[0][0];
    }