1 ms Java recursive solution


  • 0
    S
    public class Solution {
        //for memoizing solution
        private int[][] dp = null;
        
        public int calculateMinimumHP(int[][] dungeon) {
            this.dp = new int [dungeon.length][dungeon[0].length];
            
            return Math.max(1,calculateMinimumHP(dungeon, 0, 0));
            // return 0;
        }
        
        private int calculateMinimumHP(int[][] dungeon, int i, int j){
            
            if (i > dungeon.length -1 || j > dungeon[0].length - 1){
                // System.out.println(""+ i +" "+ j + " " + Integer.MAX_VALUE );
                return Integer.MAX_VALUE;
            }
            
            if (this.dp[i][j] != 0){
                return this.dp[i][j];
            }
            
            if (i == dungeon.length -1 && j == dungeon[0].length - 1){
                int res = Math.max(1, 1 - dungeon[i][j]);
                // System.out.println(""+ i +" "+ j + " " + res );
                return res;
            }
            
            int right = calculateMinimumHP(dungeon, i + 1, j) - 1;
            int down = calculateMinimumHP(dungeon, i, j+1) - 1;
            
            int min = Math.min(right, down) + (1 - dungeon[i][j]);
            
            this.dp[i][j] = Math.max(1, min);
            
            // System.out.println(""+ i +" "+ j + " " + Math.max(1, min) );
            return Math.max(1, min) ;
        }
    }
    

Log in to reply
 

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