An easy java solution


  • 0
    S
    public class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            
            int m = dungeon.length, i, j;
            if(m == 0)
                return 0;
            int n = dungeon[0].length;
            
            int[][] requirement = new int[m][n];
            
            requirement[m-1][n-1] = Math.max(1 , 1-dungeon[m-1][n-1]);
         
            for(i=m-2;i>=0;i--) {
                requirement[i][n-1] = Math.max(1 , requirement[i+1][n-1] - dungeon[i][n-1]);
            }   
            
            for(i=n-2;i>=0;i--) {
                requirement[m-1][i] = Math.max(1 , requirement[m-1][i+1] - dungeon[m-1][i]);
            }   
            
            for(i=m-2;i>=0;i--) {
                for(j=n-2;j>=0;j--) {
                    requirement[i][j] = Math.max(1 , Math.min(requirement[i+1][j] , requirement[i][j+1]) - dungeon[i][j]);
                }
            }
            
            return requirement[0][0];
        }
    }

Log in to reply
 

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