Java DP solution with explain


  • 0
    X

    My idea is I create array dp[][] to store the min health needed if K start from that room dp[i][j], and I calculate from the last room which is dp[m-1][n-1]. The [m-1][n-1] should equal 0 if the dungeon[m-1][n-1] larger than 0, or it equals dungeon[m-1][n-1], if dungeon[m-1][n-1] <0.

    The base case is m-1 row and n-1 column. For m-1 row, it should equal 0 if its value + the right room's val >0, or it equals its value + the right room's val. It is same for the n-1 column.

    For the other room, I calculate the max val between the right room and down room + itself. If the result larger than 0 I put 0 here, or the result.

    Sorry for my poor English.

    public class Solution {
            public int calculateMinimumHP(int[][] dungeon) {
                int m=dungeon.length;
                int n=dungeon[0].length;
                if(m==0||n==0){
                    return 0;
                }
                int[][] dp=new int[m][n];
                dp[m-1][n-1]=dungeon[m-1][n-1]>0?0:dungeon[m-1][n-1];
                for(int i=n-2;i>=0;i--){
                    int val=dp[m-1][i+1]+dungeon[m-1][i];
                    if(val>=0){
                        dp[m-1][i]=0;
                    }else{
                        dp[m-1][i]=val;
                    }
                }
                for(int i=m-2;i>=0;i--){
                    int val=dp[i+1][n-1]+dungeon[i][n-1];
                    if(val>=0){
                        dp[i][n-1]=0;
                    }else{
                        dp[i][n-1]=val;
                    }
                }
                for(int i=m-2;i>=0;i--){
                    for(int j=n-2;j>=0;j--){
                        int val=Math.max(dp[i+1][j],dp[i][j+1])+dungeon[i][j];
                        if(val>=0){
                            dp[i][j]=0;
                        }else{
                            dp[i][j]=val;
                        }
                    }
                }
                return -dp[0][0]+1;
                
            }
        }

  • 0
    A

    My simple and short solution:

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

        if(dungeon==null || dungeon.length==0)
            return 0;
        int x=dungeon.length-1;
        int y=dungeon[0].length-1;
        dungeon[x][y]=Math.max(1-dungeon[x][y], 1);
        
        for(int i=y-1;i>=0;i--)
            dungeon[x][i]=Math.max(dungeon[x][i+1]-dungeon[x][i], 1);
        
        for(int i=x-1;i>=0;i--)
            dungeon[i][y]=Math.max(dungeon[i+1][y]-dungeon[i][y], 1);
        
        for(int i=x-1;i>=0;i--){
            for(int j=y-1;j>=0;j--){
                int right=Math.max(dungeon[i][j+1]-dungeon[i][j], 1);
                int left=Math.max(dungeon[i+1][j]-dungeon[i][j], 1);
                dungeon[i][j]=Math.min(left, right);
            }
        }
        return dungeon[0][0];
    }
    

    }


Log in to reply
 

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