#174

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Dungeon Game

Calculate the minimum initial health the knight needs to survive the dungeon using state transition dynamic programming techniques.

array dynamic programming matrix

Problem Statement

The knight starts at the top-left corner of an m x n dungeon grid and must reach the bottom-right corner where the princess is held captive. Each cell may contain demons (negative values), health orbs (positive values), or be empty (0). The knight loses or gains health upon entering each room and dies if health drops to zero or below at any point.

Determine the minimum initial health the knight requires to rescue the princess, assuming he takes the optimal path through the dungeon. The solution must ensure survival in all cells, respecting the constraints of health loss and gain as dictated by the grid values.

Examples

Example 1

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]

Output: 7

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

Example details omitted.

Constraints

m == dungeon.length
n == dungeon[i].length
1 <= m, n <= 200
-1000 <= dungeon[i][j] <= 1000

Solution Approach

Dynamic Programming from Princess Backward

Start from the bottom-right cell where the princess is located and calculate the minimum health required to enter each cell. Use the recurrence: minHealth[i][j] = max(1, min(minHealth[i+1][j], minHealth[i][j+1]) - dungeon[i][j]). This ensures the knight survives all negative rooms and accumulates enough health.

Space Optimization

Since only the next row and column values are needed, reduce the 2D DP table to a single array representing one row at a time. Update values in-place from bottom-right to top-left to save memory while preserving correctness.

Path Validation and Edge Handling

Check the edges carefully: the last row and column must only consider the next valid cell. Ensure health never drops below 1 at any step. Negative cells reduce health, positive cells can reduce the required starting health. Properly handling these edge cases prevents invalid path calculations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m n) due to visiting each cell once for DP calculation. Space complexity is O(n) if optimizing to a single row, otherwise O(m n) for the full DP table.

What Interviewers Usually Probe

Expect discussion of reverse DP and minimum health calculations.
Check if candidate optimizes space from O(m*n) to O(n).
Look for correct handling of edge cases with demons and health orbs.

Common Pitfalls or Variants

Common pitfalls

Forgetting that health cannot drop below 1 at any cell.
Attempting forward DP from start without reverse reasoning leads to incorrect min health.
Mishandling last row or column calculations and off-by-one errors.

Follow-up variants

Allowing diagonal moves changes the DP recurrence and state transitions.
Variable health regeneration rates in positive cells introduce different state updates.
Multiple princesses require multi-target DP or BFS with min health tracking.

FAQ

What is the main strategy to solve Dungeon Game efficiently?

Use reverse state transition dynamic programming from the princess back to the knight to calculate the minimum initial health required.

Can we optimize space usage in Dungeon Game DP solution?

Yes, instead of a full m x n table, a single row array can store current minimum health values and be updated in-place.

Why must health never drop below 1 in this problem?

The knight dies immediately if health reaches zero or below, so the DP must ensure a minimum of 1 at every step.

How do demons and health orbs affect the DP calculation?

Negative values decrease required health in previous cells, while positive values reduce the minimum initial health needed, impacting the DP recurrence.

Is Dungeon Game considered a state transition dynamic programming problem?

Yes, it is a classic state transition DP problem where each cell's required health depends on the minimum of its right and bottom neighbors.

terminal

Solution

Solution 1: Dynamic Programming

We define $dp[i][j]$ as the minimum initial value needed from $(i, j)$ to the end point. The value of $dp[i][j]$ can be obtained from $dp[i+1][j]$ and $dp[i][j+1]$, that is:

1

2

3

4

5

6

7

8

9

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [[inf] * (n + 1) for _ in range(m + 1)]
        dp[m][n - 1] = dp[m - 1][n] = 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
        return dp[0][0]

Continue Practicing

#221 maximal square #85 maximal rectangle #64 minimum path sum