leetcode-go/hard/174.dungeon-game.java

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m, n;
        if ((m = dungeon.length) == 0 || (n = dungeon[0].length) == 0) return 1;
        int[][] dp = new int[m + 1][n + 1];
        // dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
        for (int i = 0; i < m - 1; i++) dp[i][n] = Integer.MAX_VALUE;
        for (int i = 0; i < n - 1; i++) dp[m][i] = Integer.MAX_VALUE;
        dp[m][n - 1] = 1;
        dp[m - 1][n] = 1;
        for (int i = m - 1; 0 <= i; i--)
            for (int j = n - 1; 0 <= j; j--)
                dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
        // Arrays.stream(dp).forEach((int[] row) -> System.out.println(Arrays.stream(row).boxed().collect(Collectors.toList())));
        return dp[0][0];
    }
}