95% Java yet a little bit long :(


  • 0
    public class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            
            /* Dynamic programming
            res[i][j] := from point (i,j) to the dest, the minimum HP you gonna carry.
            res[i][j] = max{1, min{right(if exists), down(if exists)} - dungeon[i][j]}
            */
            int m = dungeon.length;
            int n = dungeon[0].length;
            
            int[][] result = new int[m][n];
            assign(result, dungeon, m-1, n-1);
            return result[0][0];
        }
        
        public void assignColumn(int[][] result, int[][] dungeon, int i, int j){
            while(i>0){
                    if(j == result[0].length - 1)
                        result[i-1][j] = Math.max(1, result[i][j] - dungeon[i-1][j]);
                    else
                        result[i-1][j] = Math.max(1, Math.min(result[i][j],result[i-1][j+1]) - dungeon[i-1][j]);
                    i--;
            }
            return;
        }
        
        public void assignRow(int[][] result, int[][] dungeon, int i, int j){
            while(j>0){
                    if(i == result.length - 1)
                        result[i][j-1] = Math.max(1, result[i][j] - dungeon[i][j-1]);
                    else
                        result[i][j-1] = Math.max(1, Math.min(result[i][j],result[i+1][j-1]) - dungeon[i][j-1]);
                    j--;
            }
            return;
        }
        
        public void assignValue(int[][] result, int[][] dungeon, int i, int j){
            if(i==result.length-1 && j==result[0].length-1)
                result[i][j] = Math.max(1, 1-dungeon[i][j]);
            else
                result[i][j] = Math.max(1, Math.min(result[i+1][j], result[i][j+1]) - dungeon[i][j]);
        }
        
        public void assign(int[][] res, int[][] dungeon, int i, int j){
            while(i>=0 && j>=0){
                assignValue(res, dungeon, i, j);
                assignRow(res, dungeon, i, j);
                assignColumn(res, dungeon, i,j);
                i--;
                j--;
            }
        }
    }
    

Log in to reply
 

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