My Java AC solution with DP and O(1) space


  • 4
    D

    Start from the destination, we can calculate the minimum HP required then store it in the cell since we won't be needing it later. This way we can achieve constant space.

    If we care not allowed to change the matrix, then we need at least a 1-D array.

    public class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            // return 0 if dungeon does not exist
            if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) return 0;
            int m = dungeon.length -1, n = dungeon[0].length -1;
            //make sure alive after rescue
            dungeon[m][n] = setHp(1-dungeon[m][n]);
            
            //fill bottom row and right-most column
            for (int i = m-1; i >= 0; i--)
                dungeon[i][n] = setHp(dungeon[i+1][n] - dungeon[i][n]);
            for (int j = n-1; j >= 0; j--)
                dungeon[m][j] = setHp(dungeon[m][j+1] - dungeon[m][j]);
            
            //fill the rest
            for (int i = m-1; i >= 0; i--)
                for (int j = n-1; j >= 0; j--)
                    //pick minimum hp needed after this cell
                    dungeon[i][j] = setHp(Math.min(dungeon[i+1][j],dungeon[i][j+1])-dungeon[i][j]);
            
            return dungeon[0][0];
        }
        //if needed Hp is negative set hp to 1, otherwise positive
        private int setHp (int hp) {
            return hp <= 0 ? 1: hp;
        }
    }

Log in to reply
 

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