174. Dungeon Game

二刷
dp[][]定义为步入当前位置所需要的血量
如果得出步入当前位置所需血量是负数，证明格子里面补充的health足够用，所以步入当前格子不需要血。但需要时刻保持>=1 所以当遇到负数或0时，置为1
Space O(1)
Time O(mn)
90.55 %
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length == 0 || dungeon[0] == null || dungeon[0].length == 0) {
            return 0;
        }
        int rows = dungeon.length;
        int cols = dungeon[0].length;
        for (int x = rows - 1; x >= 0; x--) {
            for (int y = cols - 1; y >= 0; y--) {
                if (x == rows - 1 && y == cols - 1) {
                    dungeon[x][y] = 1 - dungeon[x][y];
                } else if (x == rows - 1) {
                    dungeon[x][y] = dungeon[x][y + 1] - dungeon[x][y];
                } else if (y == cols - 1) {
                    dungeon[x][y] = dungeon[x + 1][y] - dungeon[x][y];
                } else {
                    dungeon[x][y] = Math.min(dungeon[x][y + 1], dungeon[x + 1][y]) - dungeon[x][y];
                }
                dungeon[x][y] = Math.max(1, dungeon[x][y]);
                // System.out.println(x + ", " + y + " -> " + dungeon[x][y]);
            }
        }
        return dungeon[0][0];
    }
}


一刷
如果血量为0就死了所以任意时刻血量必须>=1，所以dp作为需要的血量，需要>=1
这道题因为没有dp的initial state 所以从终点反向求

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length == 0 || dungeon[0] == null || dungeon[0].length == 0) throw new IllegalArgumentException();
        int rows = dungeon.length;
        int cols = dungeon[0].length;
        for (int x = rows - 1; x >= 0; x--) {
            for (int y = cols - 1; y >= 0; y--) {
                if (x == rows - 1 && y == cols - 1) dungeon[x][y] = Math.max(0, -dungeon[x][y]) + 1;
                else if (x == rows - 1) {
                    dungeon[x][y] = Math.max(1, dungeon[x][y + 1] - dungeon[x][y]);
                } else if (y == cols - 1) {
                    dungeon[x][y] = Math.max(1, dungeon[x + 1][y] - dungeon[x][y]);
                } else {
                    dungeon[x][y] = Math.max(1, Math.min(dungeon[x + 1][y], dungeon[x][y + 1]) - dungeon[x][y]);
                }
            }
        }
        return dungeon[0][0];
    }
}