Description
The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight’s health (represented by positive integers).
To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Return the knight’s minimum initial health so that he can rescue the princess.
Note that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
Examples:
Example 1:
Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.
Example 2:
Input: dungeon = [[0]]
Output: 1Solution in Python
Steps to Solve the Problem:
- Initialize a DP Table:
- We’ll create a 2D DP table (
dp) wheredp[i][j]represents the minimum health required to reach the princess when starting from room(i, j).
- We’ll create a 2D DP table (
- Base Case:
- The base case is the bottom-right room where the princess is located. The knight must have at least
1health point after exiting this room, sodp[m-1][n-1]should bemax(1, 1 - dungeon[m-1][n-1]).
- The base case is the bottom-right room where the princess is located. The knight must have at least
- Filling the DP Table:
- We fill the DP table starting from the bottom-right corner and moving left and upwards.
- For each room
(i, j), the knight needs enough health to move to either the room on the right(i, j+1)or the room below(i+1, j). We choose the path that requires the least health. - The knight’s health at
(i, j)should be enough to cover the cost of the current room plus the minimum health required for the next step: dp[i][j]=max(1,min(dp[i+1][j],dp[i][j+1])−dungeon[i][j]) - Here,
\min(dp[i+1][j], dp[i][j+1])gives us the minimum health needed for the next step, and subtractingdungeon[i][j]adjusts for the health effect of the current room.
- Return the Result:
- Finally,
dp[0][0]will contain the minimum health required to start at the top-left corner and reach the bottom-right corner alive.
- Finally,
Python
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
m, n = len(dungeon), len(dungeon[0])
# Initialize a DP table with dimensions m x n
dp = [[float('inf')] * n for _ in range(m)]
# Base case for the bottom-right room
dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
# Fill the DP table starting from the bottom-right corner
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
if i < m-1: # If there's a room below
dp[i][j] = min(dp[i][j], max(1, dp[i+1][j] - dungeon[i][j]))
if j < n-1: # If there's a room to the right
dp[i][j] = min(dp[i][j], max(1, dp[i][j+1] - dungeon[i][j]))
# The result is the minimum initial health required at the top-left corner
return dp[0][0]Explanation:
- Initialization: The
dptable is initialized withinf(infinity) since we want to minimize the health required. - Base Case: The minimum health required at the princess’s location is calculated first.
- Filling the DP Table: We move from bottom-right to top-left, ensuring at each step that the knight has enough health to survive.
- Result: The top-left cell
dp[0][0]gives us the minimum health required to start the journey.
This approach efficiently computes the minimum initial health required for the knight to rescue the princess.
Solution in Javascript
JavaScript
/**
* @param {number[][]} dungeon
* @return {number}
*/
var calculateMinimumHP = function(dungeon) {
const m = dungeon.length; // Number of rows in the dungeon
const n = dungeon[0].length; // Number of columns in the dungeon
// Create a DP table with dimensions m x n, initialized with Infinity
const dp = Array.from({ length: m }, () => Array(n).fill(Infinity));
// Base case: Bottom-right room (where the princess is)
dp[m-1][n-1] = Math.max(1, 1 - dungeon[m-1][n-1]);
// Fill the DP table starting from the bottom-right corner
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; j >= 0; j--) {
// If there's a room below, calculate the minimum health required from below
if (i < m - 1) {
dp[i][j] = Math.min(dp[i][j], Math.max(1, dp[i+1][j] - dungeon[i][j]));
}
// If there's a room to the right, calculate the minimum health required from the right
if (j < n - 1) {
dp[i][j] = Math.min(dp[i][j], Math.max(1, dp[i][j+1] - dungeon[i][j]));
}
}
}
// The top-left cell dp[0][0] contains the minimum initial health required
return dp[0][0];
};Solution in Java
Java
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length; // Number of rows in the dungeon
int n = dungeon[0].length; // Number of columns in the dungeon
// Create a DP table with dimensions m x n
int[][] dp = new int[m][n];
// Base case: Minimum health needed to rescue the princess
dp[m-1][n-1] = Math.max(1, 1 - dungeon[m-1][n-1]);
// Fill the last row (bottom row) from right to left
for (int j = n - 2; j >= 0; j--) {
dp[m-1][j] = Math.max(1, dp[m-1][j+1] - dungeon[m-1][j]);
}
// Fill the last column (rightmost column) from bottom to top
for (int i = m - 2; i >= 0; i--) {
dp[i][n-1] = Math.max(1, dp[i+1][n-1] - dungeon[i][n-1]);
}
// Fill the rest of the DP table
for (int i = m - 2; i >= 0; i--) {
for (int j = n - 2; j >= 0; j--) {
int minHealthOnExit = Math.min(dp[i+1][j], dp[i][j+1]);
dp[i][j] = Math.max(1, minHealthOnExit - dungeon[i][j]);
}
}
// The top-left cell dp[0][0] contains the minimum initial health required
return dp[0][0];
}
}Solution in C#
C#
public class Solution {
public int CalculateMinimumHP(int[][] dungeon) {
int m = dungeon.Length; // Number of rows in the dungeon
int n = dungeon[0].Length; // Number of columns in the dungeon
// Create a DP table with dimensions m x n
int[,] dp = new int[m, n];
// Base case: Minimum health needed to rescue the princess in the bottom-right corner
dp[m-1, n-1] = Math.Max(1, 1 - dungeon[m-1][n-1]);
// Fill the last row (bottom row) from right to left
for (int j = n - 2; j >= 0; j--) {
dp[m-1, j] = Math.Max(1, dp[m-1, j+1] - dungeon[m-1][j]);
}
// Fill the last column (rightmost column) from bottom to top
for (int i = m - 2; i >= 0; i--) {
dp[i, n-1] = Math.Max(1, dp[i+1, n-1] - dungeon[i][n-1]);
}
// Fill the rest of the DP table
for (int i = m - 2; i >= 0; i--) {
for (int j = n - 2; j >= 0; j--) {
int minHealthOnExit = Math.Min(dp[i+1, j], dp[i, j+1]);
dp[i, j] = Math.Max(1, minHealthOnExit - dungeon[i][j]);
}
}
// The top-left cell dp[0,0] contains the minimum initial health required
return dp[0, 0];
}
}