Dungeon Game

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

• Time: O(n)
• Space: O(n)

public int calculateMinimumHP(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
    int m = grid.length;
    int n = grid[0].length;
    grid[m - 1][n - 1] = Math.max(1 - grid[m - 1][n - 1], 1);
    for (int i = m - 2; i >= 0; i--) {
        grid[i][n - 1] = Math.max(grid[i + 1][n - 1] - grid[i][n - 1], 1);
    }
    for (int j = n - 2; j >= 0; j--) {
        grid[m - 1][j] = Math.max(grid[m - 1][j + 1] - grid[m - 1][j], 1);
    }

    for (int i = m - 2; i >= 0; i--) {
        for (int j = n - 2; j >= 0; j--) {
            int min = Math.min(grid[i + 1][j], grid[i][j + 1]);
            grid[i][j] = min > grid[i][j] ? min - grid[i][j] : 1;
        }
    }
    return grid[0][0];
}