174. Dungeon Game

https://leetcode.com/problems/dungeon-game/description/

• 乍一看，这个问题和"Maximum/Minimum Path Sum"问题很相似。然而，具有全局最大HP（生命值）收益的路径并不一定可以保证最小的初始HP，因为题目中具有限制条件：HP不能≤0。例如，考虑下面的两条路径：0 -> -300 -> 310 -> 0 和 0 -> -1 -> 2 -> 0。这两条路径的净HP收益分别是-300 + 310 = 10 与 -1 + 2 = 1。第一条路径的净收益更高，但是它所需的初始HP至少是301，才能抵消第二个房间的-300HP损失，而第二条路径只需要初始HP为2就可以了。
• 幸运的是，这个问题可以通过“table-filling”（表格填充）动态规划算法解决，与其他"grid walking"（格子行走）问题类似：

思路

骑士向右或者向下走，如果血量小于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];
    }
}