LeetCode 174: Dungeon Game

Explanation:

To solve this problem, we can use dynamic programming. We start from the bottom-right corner (princess room) and move towards the top-left corner (knight's starting point). At each cell, we calculate the minimum health needed to reach the princess. We iterate in reverse order to consider the minimum health required to reach the princess from either the cell below or the cell to the right.

We maintain a 2D DP array where dp[i][j] represents the minimum health needed at cell (i, j) to reach the princess. We initialize the last cell (princess room) as max(1, 1-dungeon[m-1][n-1]) since the knight needs at least 1 health point to survive.

Then, we iterate from m-1 to 0 and from n-1 to 0, updating the dp values based on the minimum health required from the cell below or the cell to the right.

Finally, we return the dp[0][0] which represents the minimum initial health needed at the knight's starting point.

• Time complexity: O(m*n) where m and n are the dimensions of the dungeon.
• Space complexity: O(m*n) for the DP array.

:

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