Easy java solution using DP


  • 0
    D

    public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {

        //Base case: if number of rows or columns is 0, return 0
        if(dungeon.length==0 || dungeon[0].length==0 || dungeon==null)
            return 0;
            
        //matrix to store minimum paths from each position to the end(using DP)
        int[][] solutionMatrix=new int[dungeon.length][dungeon[0].length];
        
        //for loops to form solution matrix by backtracking
        for(int i=dungeon.length-1;i>=0;i--)
        {
            for(int j=dungeon[0].length-1;j>=0;j--)
            {
                //Case 1: if present in middle of matrix,find the minimum solution of either side, and add it to current position
                if(i!=dungeon.length-1 && j!=dungeon[0].length-1)
                    solutionMatrix[i][j]=Math.max(1,Math.min(solutionMatrix[i+1][j],solutionMatrix[i][j+1])-dungeon[i][j]);
                //Case 2: if present at column bound
                else if(i!=dungeon.length-1)
                    solutionMatrix[i][j]=Math.max(1,solutionMatrix[i+1][j]-dungeon[i][j]);
                //Case 3: if present at row bound
                else if(j!=dungeon[0].length-1)
                    solutionMatrix[i][j]=Math.max(1,solutionMatrix[i][j+1]-dungeon[i][j]);
                //Case 4: if at the destination
                else
                    solutionMatrix[i][j]=Math.max(1,0-dungeon[i][j]+1);
            }
        }
        
        return solutionMatrix[0][0];
        
    }
    

    }


Log in to reply
 

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