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.
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: 1
Constraints:
m == dungeon.lengthn == dungeon[i].length1 <= m, n <= 200-1000 <= dungeon[i][j] <= 1000The key challenge in #174 Dungeon Game is determining the minimum initial health a knight needs to survive a grid of positive and negative cells while moving only right or down. A greedy strategy does not work because a locally optimal choice may lead to failure later. Instead, this problem is best solved using Dynamic Programming.
The idea is to work backwards from the destination. For each cell, compute the minimum health required to enter that cell so the knight can safely reach the princess. At every step, choose the smaller health requirement between moving right or down, then adjust based on the dungeon cell's value. The health must always remain at least 1.
This leads to a bottom-up DP table where each entry represents the minimum health needed before entering that cell. The standard solution runs in O(m × n) time for an m x n grid, with O(m × n) space, which can be optimized to O(n) using a rolling array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bottom-Up Dynamic Programming | O(m × n) | O(m × n) |
| Space Optimized DP | O(m × n) | O(n) |
Techdose
In this approach, we'll utilize dynamic programming to calculate the minimum health needed at each room starting from the bottom-right corner (princess's location) up to the top-left corner (knight's starting point). We'll create a 2D DP array where dp[i][j] represents the minimum health required to reach the princess when starting at cell (i, j). The main idea is to ensure that at any point, the knight never drops to zero or negative health.
The transition involves ensuring that the knight has enough health to move to one of the neighboring cells (right or down), covering the requirement to sustain the journey until the end.
Time Complexity: O(m * n), where m is the number of rows and n the number of columns.
Space Complexity: O(m * n), used by the dp table.
1def calculateMinimumHP(dungeon):
2 m, n = len(dungeon), len(dungeon[0])
3 dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
4 dp[m][n - 1] = dp[m - 1][n] = 1
5 for i in range(m - 1, -1, -1):
6 for j in range(n - 1, -1, -1):
7 min_health_on_exit = min(dp[i + 1][j], dp[i][j + 1])
8 dp[i][j] = max(min_health_on_exit - dungeon[i][j], 1)
9 return dp[0][0]This solution initializes a DP table with values set to infinity for easier minimum comparisons, except for the 'virtual' edges that allow transitions. Starting from the bottom-right corner, it calculates the health required from the target cell back to the knight's starting point, adjusting the minimum health based on the room's value and ensuring it doesn't fall below 1.
In this approach, we use only a single row (or column) to store intermediate results, thereby reducing space complexity. The idea is based on modifying the DP solution to use space proportional to the minimum dimension of the matrix, proceeding row by row or column by column and updating the required health values as we simulate moving from the goal to the start in the minimal dimension.
Time Complexity: O(m * n), where m is the number of rows and n the number of columns.
Space Complexity: O(n), using reduced 1D list for the dp array.
1public int calculateMinimumHP(int[][] dungeon) {
2 Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Dungeon Game is a well-known hard dynamic programming problem that can appear in FAANG-style interviews. It tests grid DP reasoning, reverse thinking, and careful handling of constraints like maintaining minimum health.
The optimal approach uses dynamic programming starting from the bottom-right cell. By computing the minimum health required to enter each cell based on future moves, we ensure the knight never drops below 1 health. This guarantees the minimum initial health needed to rescue the princess.
A 2D dynamic programming table is typically used to store the minimum health required at each cell. For memory optimization, the solution can also be implemented using a 1D array that represents a rolling row of the DP table.
Working backward makes it easier to determine the minimum health required before entering each cell. Since the knight must reach the princess alive, we compute the health needed to survive future steps and propagate that requirement backward through the grid.
In this Java solution, we've reduced space complexity by storing results for each row traversal in a single 1D array. The solution iterates backward through columns while updating each min-health leaving values, ultimately outputting the starting health for the knight accurately.