Java Solution using DP


  • 1

    Given the health of knight cannot be allowed to be less than 1, and we want to calculate the min-health at the start, so we should iterate the dp array in reverse order.
    For each cell, if the dungeon[i][j] is positive, dp[i][j] subtracts it until 1; if the dungeon[i][j] is negative, dp[i][j] plus it. Because the knight can only move right or down, so the value of each cell in dp comes from the min value of its right and bottom cell.

    public class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            int[][] dp = new int[dungeon.length][dungeon[0].length];
    
            for(int i=dp.length-1; i>=0; i--) {
                for(int j=dp[0].length-1; j>=0; j--) {
                    if(i == dp.length-1 && j == dp[0].length-1) {
                        dp[i][j] = 1 - dungeon[i][j] < 1 ? 1 : 1 - dungeon[i][j];
                    } else {
                        int right = j == dp[0].length-1 ? Integer.MAX_VALUE :
                                (dp[i][j+1] - dungeon[i][j] < 1 ? 1 : dp[i][j+1] - dungeon[i][j]);
                        int bottom = i == dp.length-1 ? Integer.MAX_VALUE :
                                dp[i+1][j] - dungeon[i][j] < 1 ? 1 : dp[i+1][j] - dungeon[i][j];
                        dp[i][j] = Math.min(right, bottom);
                    }
                }
            }
            return dp[0][0];
        }
    }
    

Log in to reply
 

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