My AC Java Version, Suggestions are welcome


  • 48
    V
    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) return 0;
        
        int m = dungeon.length;
        int n = dungeon[0].length;
        
        int[][] health = new int[m][n];
    
        health[m - 1][n - 1] = Math.max(1 - dungeon[m - 1][n - 1], 1);
    
        for (int i = m - 2; i >= 0; i--) {            
            health[i][n - 1] = Math.max(health[i + 1][n - 1] - dungeon[i][n - 1], 1);
        }
    
        for (int j = n - 2; j >= 0; j--) {
            health[m - 1][j] = Math.max(health[m - 1][j + 1] - dungeon[m - 1][j], 1);
        }
    
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int down = Math.max(health[i + 1][j] - dungeon[i][j], 1);
                int right = Math.max(health[i][j + 1] - dungeon[i][j], 1);
                health[i][j] = Math.min(right, down);
            }
        }
    
        return health[0][0];
    }

  • 3
    P

    Although it's straightforward, but it would still be better to add some explanation and comment on the code IMHO.


  • 3
    P

    Thanks for the good solution.

    As an improvement, it can also be solved without extra space.

    Find below my accepted code. :

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

  • 3
    Y

    Before modifying the original matrix, it might be a good idea to ask the interviewer whether it is ok in my opinion.


  • 2

    For DP problem, I always come up with recursion + memoization approach.
    Someone may feel DP is straight-forward, someone may think the other.
    Anyway, here is a top down recursive solution:

    public class Solution {
        
        int[][] mem;
        
        private int helper(int[][] dungeon, int i, int j) {
            if(i>=dungeon.length || j>=dungeon[0].length)
                return Integer.MAX_VALUE;
            if(mem[i][j]>0)
                return mem[i][j];
            int health = Integer.MAX_VALUE;
            health = Math.min(health, helper(dungeon, i+1, j));
            health = Math.min(health, helper(dungeon, i, j+1));
            health = health==Integer.MAX_VALUE ? 1 : health; // this only happens with i, j is P already
            int ret = health>dungeon[i][j] ? (health-dungeon[i][j]) : 1;
            mem[i][j] = ret;
            return ret;
        }
        
        public int calculateMinimumHP(int[][] dungeon) {
            if(dungeon.length==0)
                return 0;
            mem = new int[dungeon.length][dungeon[0].length];
            return helper(dungeon, 0, 0);
        }
    }

Log in to reply
 

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