My bottom-up O(n^2) Java Solution with detailed explanation


  • 1

    I use another 2-D array to store intermediate result. If you don't care modification of original array, you can replace all "result" as "dungeon". So O(1) space can be achieved.

    Then use bottom-up strategy to compute the minimum initial health for each cell from bottom-right direction.

    I use the current cell minus previous path's health requirement to compute reversed health requirement for each cell.

    I use this line to update required health for each cell:

            result[i][j] = result[i][j] > 0 ? 0 : -result[i][j];
    

    The whole code:

    public class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            int[][] result = new int[dungeon.length][dungeon[0].length];
    
            for (int i = dungeon.length - 1; i >= 0; i--) {
                int[] row = dungeon[i];
                for (int j = row.length - 1; j >= 0; j--) {
                    boolean rowEnd = i == dungeon.length - 1;
                    boolean columnEnd = j == row.length - 1;
                    if (rowEnd && columnEnd) {
                        result[i][j] = dungeon[i][j];
                    } else if (!rowEnd && !columnEnd) {
                        result[i][j] = dungeon[i][j] - Math.min(result[i + 1][j], result[i][j + 1]);
                    } else {
                        result[i][j] = dungeon[i][j] - result[i + (rowEnd ? 0 : 1)][j + (columnEnd ? 0 : 1)];
                    }
                    result[i][j] = result[i][j] > 0 ? 0 : -result[i][j];
                }
            }
            return result[0][0] + 1;
        }
    }

  • 0
    C

    I have the same similar solution with you. Furthermore, you can just use one dimensional array result[colNumber] to update the result.


  • 0

    Yes, I use 2-D array just make the logic looks clear. I have another post to share O(1) space solution by change original values.


  • 0
    R

    can you write it also top-down, for me always top down is much easier. I wrote the top down DP, but it does not pass the limit for me


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.