174. Dungeon Game
Problem Description
The problem presents a scenario where a knight must rescue a princess trapped in the bottom-right corner of a dungeon represented by a 2D grid. The grid has dimensions m x n
, with each cell of the grid representing a room that may contain demons, magic orbs, or be empty. The knight begins at the top-left room and can only move rightward or downward.
The knight has an initial health value, which must always remain above 0 for him to survive. If the knight passes through a room with demons, his health decreases by the number depicted in that room; if the room contains magic orbs, his health increases accordingly. The objective is to calculate the minimum health the knight needs to start with to ensure he can reach the princess without dying.
Intuition
The key to solving this problem lies in dynamic programming, particularly in understanding that the optimal decision at each room depends on the decisions made in subsequent rooms. Rather than navigating from the start to the end, we work backwards from the princess's room to the knight's starting point. This way, we can always make sure the knight has just enough health to reach the next step.
We initialize a 2D array (dp
) that will store the minimum health required to reach the princess from any given cell. The knight's goal is to reach the cell containing the princess with at least 1 health point.
Starting from the princess's cell, we backtrack and calculate the minimum health needed for each previous room. The minimum health required to enter any room is the maximum of 1 (the knight can't have less than 1 health) and the difference between the health required to enter the subsequent room and the value of the current room (which may be positive, negative, or zero).
This computation proceeds until we reach the starting cell, at which point dp[0][0]
gives us the minimum health that the knight must have to rescue the princess successfully.
Learn more about Dynamic Programming patterns.
Solution Approach
We approach the solution by implementing dynamic programming to solve the problem in a bottom-up manner. Let's go through the implementation using the supplied Python code.
-
Initialization of the DP table: We create a 2D array
dp
of size(m+1)x(n+1)
filled withinf
(infinity). This represents the minimum health needed to reach the princess from any given cell. We fill it withinf
to represent that we haven't calculated the health for any room yet. We usem+1
andn+1
for ease of implementation so that we can handle the boundary without checking for edge cases in each iteration. -
Boundary Conditions: Set
dp[m][n - 1]
anddp[m - 1][n]
to 1 because the knight needs a minimum of 1 health point to survive. These are the cells adjacent to the princess's cell. As the knight can only move rightward or downward, these cells represent the only two ways to reach the bottom-right corner without being in it. -
Main Loop: We iterate over the dungeon grid starting from the cell
(m - 1, n - 1)
which is right above and to the left of the princess's cell, moving backward to the start at(0, 0)
. For each cell(i, j)
, we calculate the minimum health the knight needs to proceed to either of the next cells(i + 1, j)
(downwards) or(i, j + 1)
(rightward).Here's the core logic: we use
max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
, which means:- We first determine the less risky path by finding the minimum of the health needed to move to the next cells (
min(dp[i + 1][j], dp[i][j + 1])
). - We then subtract the current room's value from this health. If the current room has a demon (negative value), this effectively increases the health needed to handle the demon. If the room has an orb (positive value), this decreases the required health.
- However, even if the room's positive value exceeds the health from the next step, the knight cannot have less than 1 health (
max(1, ...)
).
- We first determine the less risky path by finding the minimum of the health needed to move to the next cells (
-
Final Answer: After filling the DP table, the value in the top-left cell
dp[0][0]
is our answer as it represents the minimum health the knight needs to start with in order to rescue the princess.
Using this approach, we avoid recalculating the minimum health requirement for each cell multiple times, leading to an efficient algorithm with a time complexity of O(m*n)
where m
and n
are the dimensions of the dungeon grid.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say the dungeon grid is represented by the following 2D grid, where m = 2
and n = 3
:
[[-2, -3, 3], [-5, -10, 1]]
Here's the step-by-step breakdown of the dynamic programming approach:
- Initialization of DP Table:
We initialize
dp
with size(2+1)x(3+1)
and fill it withinf
except for the boundariesdp[2][2]
anddp[2][3]
ordp[3][2]
, which are set to 1.
dp = [ [inf, inf, inf, inf], [inf, inf, inf, 1 ], [inf, inf, 1, inf]]
- Boundary Conditions:
The bottom-right corner
(m - 1, n - 1)
is the princess's room, hencedp[1][2]
will be the maximum of 1 and the inverse of that room's demon value3
minus1
(minimum health needed to survive). Since3
minus1
is2
, and we need a maximum of1
, it stays as1
:
dp = [ [inf, inf, inf, inf], [inf, inf, 1, 1 ], [inf, inf, 1, inf]]
- Main Loop:
- We first calculate
dp[1][1]
, which is the maximum of1
andmin(dp[1 + 1][1], dp[1][1 + 1]) - dungeon[1][1]
. The minimum ofdp[2][1]
(inf) anddp[1][2]
(1) is1
. The dungeon value at[1][1]
is-10
. Thus1 (-10 + 10 = 0)
becomes the value ofdp[1][1]
. - Then we calculate
dp[1][0]
which is the maximum of1
andmin(dp[1 + 1][0], dp[1][0 + 1]) - dungeon[1][0]
. The minimum ofdp[2][0]
(inf) anddp[1][1]
(1) is1
. With a dungeon value of-5
, we getmax(1, 1 - (-5)) = 6
.
- We first calculate
dp = [ [inf, inf, inf, inf], [6, 1, 1, 1 ], [inf, inf, 1, inf]]
- For the top row, we repeat the same for
dp[0][2]
anddp[0][1]
. Finally,dp[0][0]
is computed, the maximum of1
andmin(dp[0 + 1][0], dp[0][0 + 1]) - dungeon[0][0]
. The minimum ofdp[1][0]
(6) anddp[0][1]
(inf) is6
. Subtracting the dungeon value-2
, we needmax(1, 6 - (-2)) = 8
.
dp = [ [8, inf, inf, inf], [6, 1, 1, 1 ], [inf, inf, 1, inf]]
Now, the DP table shows dp[0][0] = 8
, which means the knight needs at least 8
health points to ensure he can reach the princess without dying.
This simple example illustrates the backward calculation from the end goal, using dynamic programming to efficiently compute the health needed at each step. The final answer as per the dp
table shows that the knight needs a minimum starting health of 8
.
Solution Implementation
1from typing import List
2from math import inf
3
4class Solution:
5 def calculate_minimum_hp(self, dungeon: List[List[int]]) -> int:
6 # Get the dimensions of the dungeon matrix.
7 num_rows, num_columns = len(dungeon), len(dungeon[0])
8
9 # Initialize dp (Dynamic Programming) matrix with infinity.
10 # An extra row and column are added to handle the edge cases easily.
11 dp = [[inf] * (num_columns + 1) for _ in range(num_rows + 1)]
12
13 # The hero needs at least 1 HP to reach the princess.
14 # Initialize the cell to the princess's right and the one below her to 1.
15 dp[num_rows][num_columns - 1] = dp[num_rows - 1][num_columns] = 1
16
17 # Start from the bottom right corner and move to the top left corner.
18 for i in range(num_rows - 1, -1, -1): # Iterate over rows in reverse
19 for j in range(num_columns - 1, -1, -1): # Iterate over columns in reverse
20
21 # Find the minimum HP needed to go to the next cell.
22 # Cannot have less than 1 HP, hence the max with 1.
23 min_hp_on_exit = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
24 dp[i][j] = max(1, min_hp_on_exit)
25
26 # Return the HP needed at the start (0,0) to guarantee reaching the princess.
27 return dp[0][0]
28
29# Example usage:
30# sol = Solution()
31# print(sol.calculate_minimum_hp([[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]))
32
1class Solution {
2
3 // Function to calculate the minimum initial health needed to reach the bottom-right corner
4 public int calculateMinimumHP(int[][] dungeon) {
5 // Dimensions of the dungeon
6 int rows = dungeon.length;
7 int cols = dungeon[0].length;
8
9 // Dynamic programming table where each cell represents the minimum health needed
10 int[][] minHealth = new int[rows + 1][cols + 1];
11
12 // Initialize the dp table with high values except the border cells right and below the dungeon
13 for (int[] row : minHealth) {
14 Arrays.fill(row, Integer.MAX_VALUE);
15 }
16
17 // Initialization for the border cells where the hero can reach the princess with 1 health point
18 minHealth[rows][cols - 1] = minHealth[rows - 1][cols] = 1;
19
20 // Start from the bottom-right corner of the dungeon and move leftward and upward
21 for (int i = rows - 1; i >= 0; --i) {
22 for (int j = cols - 1; j >= 0; --j) {
23 // The health at the current cell is the minimum health needed from the next step minus the current cell's effect
24 // It should be at least 1 for the hero to be alive
25 int healthNeeded = Math.min(minHealth[i + 1][j], minHealth[i][j + 1]) - dungeon[i][j];
26 minHealth[i][j] = Math.max(1, healthNeeded);
27 }
28 }
29
30 // The result is the minimum health needed at the starting cell
31 return minHealth[0][0];
32 }
33}
34
1#include <vector>
2#include <algorithm>
3#include <cstring>
4
5using std::vector;
6using std::max;
7using std::min;
8using std::memset;
9
10class Solution {
11public:
12 // Function to calculate the minimum health needed to reach the princess (at bottom-right of the dungeon)
13 // starting with positive health when moving only rightward or downward.
14 int calculateMinimumHP(vector<vector<int>>& dungeon) {
15 int m = dungeon.size(); // Number of rows
16 int n = dungeon[0].size(); // Number of columns
17 int dp[m + 1][n + 1]; // Create DP table of size (m+1)x(n+1)
18
19 // Initialize the dp array with a very large value, as we are looking for minimum health required.
20 memset(dp, 0x3f, sizeof dp);
21
22 // Set the health needed at the dungeon's exit. We need at least 1 health at the end.
23 dp[m][n - 1] = 1; // If we are at the last cell of the last row
24 dp[m - 1][n] = 1; // If we are at the last cell of the last column
25
26 // Loop through the dungeon starting from the bottom right corner, moving to the upper left corner
27 for (int i = m - 1; i >= 0; --i) { // Loop for rows
28 for (int j = n - 1; j >= 0; --j) { // Loop for columns
29 // The minimum health needed at the start of this cell is 1 or the health we need for the next cell
30 // minus the current cell value, whichever is larger. We are moving to the previous cell hence we use `max`.
31 // We are also trying to find the lesser of the two paths to reach the next cell hence we use `min`.
32 dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
33 }
34 }
35
36 return dp[0][0]; // The minimum health needed at the start is at the top-left corner of the dp table.
37 }
38};
39
1// type definition for the 2D dungeon matrix
2type Dungeon = number[][];
3
4// Function to calculate the minimum health needed to reach the princess (at bottom-right of the dungeon)
5// starting with positive health when moving only rightward or downward.
6function calculateMinimumHP(dungeon: Dungeon): number {
7 const m: number = dungeon.length; // Number of rows
8 const n: number = dungeon[0].length; // Number of columns
9 let dp: number[][] = Array.from(Array(m + 1), () => new Array(n + 1).fill(0x3f3f3f3f)); // Create DP table filled with large values, since we are looking for minimum health required
10
11 // Set the health needed at the dungeon's exit. We need at least 1 health at the end.
12 dp[m][n - 1] = 1; // If at the last cell of the last row
13 dp[m - 1][n] = 1; // If at the last cell of the last column
14
15 // Loop through the dungeon starting from the bottom right corner, moving to the upper left corner
16 for (let i = m - 1; i >= 0; i--) { // Loop for rows
17 for (let j = n - 1; j >= 0; j--) { // Loop for columns
18 // The minimum health needed at the start of this cell is either 1 or the health we need for the next cell
19 // minus the current cell value, whichever is larger. We use `Math.max` to ensure we don't have non-positive health.
20 // We also want the smaller of the two possible paths (rightward or downward) to reach the next cell hence we use `Math.min`.
21 dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
22 }
23 }
24
25 return dp[0][0]; // The minimum health needed at the start is at the top-left corner of the DP table.
26}
27
Time and Space Complexity
The given Python code implements a dynamic programming algorithm to calculate the minimum initial health required for a character to navigate a dungeon represented as a 2D grid where some cells contain positive values (health potions) and others contain negative values (traps).
Time Complexity
The time complexity of the algorithm is O(m*n)
, where m
is the number of rows and n
is the number of columns in the dungeon
grid. This is because the algorithm consists of a nested loop structure that iterates over each cell of the dungeon
grid exactly once.
Space Complexity
The space complexity is also O(m*n)
due to the auxiliary 2D list dp
that has the same dimensions as the dungeon
grid plus one extra row and column to handle the boundary cases. This dp
list is used to store the minimum health required at each cell to reach the bottom right corner of the grid.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!