My short and fast DP Java solution


  • 0
    X

    The idea is that start from the Princess position, we calculate the min health required while entering this position.
    The DP state transition would be:

    DP[i][j] = dungeon[i][j] >= Math.min(DP[i+1][j], DP[i][j+1]) ? 1 : Math.min(DP[i+1][j], DP[i][j+1]) - dungeon[i][j];
    

    Here are the code:

    public int calculateMinimumHP(int[][] dungeon) {
        if(dungeon == null || dungeon.length == 0) return 0;
        int row = dungeon.length, col = dungeon[0].length;
        int[][] dp = new int[row][col];
        for(int i = row-1; i>= 0; i--){
            for(int j = col-1; j >= 0; j--){
                if(i == row-1 && j == col-1) dp[i][j] = dungeon[i][j] >= 0 ? 1 : 1-dungeon[i][j];
                else{
                    int minToNext = (i == row-1) ? dp[i][j+1] : ((j==col-1) ? dp[i+1][j] : Math.min(dp[i+1][j], dp[i][j+1]));
                    dp[i][j] = dungeon[i][j] >= minToNext ? 1 : minToNext - dungeon[i][j];
                }
            }
        }
        return dp[0][0];
    }

Log in to reply
 

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