How do you solve Dungeon Game?

Use a 2D DP array where dp[r][c] represents the minimum health needed to enter cell (r, c). Initialize dp at the bottom-right cell as max(1, 1 - dungeon[r][c]) to ensure survival after the last cell. Then fill dp backward from bottom-right to top-left, computing dp[r][c] = max(1, min(dp[r+1][c], dp[r][c+1]) - dungeon[r][c]). The answer is dp[0][0], the minimum initial health needed at the start.

Dungeon Game

Q: What is the time complexity of Dungeon Game?

O(m * n). The algorithm fills a dp table of size m x n once, performing constant work per cell, resulting in O(m*n) time.

Q: What pattern does Dungeon Game use?

The Pattern: Dynamic Programming (Grid Backward State Propagation) The Heuristic: When a problem requires a minimum or maximum resource to survive a path with constraints, working backward from the destination to compute the required state at each step often transforms an exponential search into a polynomial DP solution.

Hard Dynamic Programming

Problem

Given a 2D grid dungeon where each cell contains an integer representing health points gained or lost, return the minimum initial health required for a knight to reach the bottom-right cell from the top-left cell, moving only right or down, such that the knight's health never drops below 1 at any point.

1 ≤ dungeon.length, dungeon[0].length ≤ 200
−1000 ≤ dungeon[i][j] ≤ 1000

Example

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

Output: 7

Starting with 7 health, the knight moves right and down to reach the bottom-right cell without health dropping below 1. For example, path: (0,0) -2 health → health = 7 - 2 = 5, (0,1) -3 health → health = 5 - 3 = 2, (0,2) +3 health → health = 2 + 3 = 5, (1,2) +1 health → health = 5 + 1 = 6, (2,2) -5 health → health = 6 - 5 = 1. At every step, health is at least 1, so 7 is the minimum initial health.

Approach

Straightforward Solution

A brute-force approach would try all paths from start to end, tracking health at each step, which is exponential in time and infeasible for large grids.

Core Observation

The knight's health must remain at least 1 at every cell, and the minimum health needed at each cell depends on the minimum health needed in the next cells (right and down). This backward dependency suggests a dynamic programming approach starting from the destination.

Path to Optimal

Preview

Recognizing that the problem requires the minimum initial health to survive all cells along any path, the key insight is to work backward from the destination cell…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a 2D DP array where dp[r][c] represents the minimum health needed to enter cell (r, c). Initialize dp at the bottom-right cell as max(1, 1 - dungeon[r][c]) to ensure survival after the last cell…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

The algorithm fills a dp table of size m x n once, performing constant work per cell, resulting in O(m*n) time.

Space

O(m * n)

The dp table stores minimum health requirements for each cell, requiring O(m*n) auxiliary space proportional to the input grid size.

Pattern Spotlight

Dynamic Programming (Grid Backward State Propagation)

When a problem requires a minimum or maximum resource to survive a path with constraints, working backward from the destination to compute the required state at each step often transforms an exponential search into a polynomial DP solution.

Solution

Python

1class Solution:
2    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
3        rows = len(dungeon)
4        cols = len(dungeon[0])
5
6        dp = [[0] * cols for _ in range(rows)]
7
8        dp[-1][-1] = max(1, 1 - dungeon[-1][-1])
9
10        for r in range(rows - 1, -1, -1):
11            for c in range(cols - 1, -1, -1):
12
13                if r == rows - 1 and c == cols - 1:
14                    continue
15
16                down = dp[r+1][c] if r+1 < rows else float("inf")
17                right = dp[r][c+1] if c+1 < cols else float("inf")
18
19                need = min(down, right)
20
21                dp[r][c] = max(1, need - dungeon[r][c])
22
23        return dp[0][0]

Step-by-Step Solution

Initialize DP Table and Set Base Case at Destination

3rows = len(dungeon)
4cols = len(dungeon[0])
6dp = [[0] * cols for _ in range(rows)]
8dp[-1][-1] = max(1, 1 - dungeon[-1][-1])

Objective

To create a DP table matching the dungeon's dimensions and initialize the minimum health needed at the bottom-right cell.

Key Insight

The bottom-right cell is the destination; the knight must have at least 1 health point after entering it. The minimum health needed to enter this cell is max(1, 1 - dungeon value), ensuring survival regardless of whether the cell adds or subtracts health. This base case anchors the backward DP computation.

Interview Quick-Check

Core Logic

Initializing dp[-1][-1] as max(1, 1 - dungeon[-1][-1]) ensures the knight survives the last cell with at least 1 health.

Common Pitfalls & Bugs

Failing to use max with 1 can cause the DP to underestimate health needed when the dungeon cell has positive value.

Compute Minimum Health Requirements Backward for Each Cell

To fill the DP table from bottom-right to top-left, calculating the minimum health needed to enter each cell based on its neighbors.

Return the Minimum Initial Health Required at Start

To output the minimum initial health needed for the knight to start at the top-left cell and survive the dungeon.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 21 Critical

dp[r][c] = max(1, need - dungeon[r][c])

Compute and store the minimum health needed to enter the current cell.

This max operation is the core DP logic that ensures the knight's health never falls below 1 by accounting for the minimum health needed in the next step minus the current cell's effect, guaranteeing survival along the path.

Line 8 Critical

dp[-1][-1] = max(1, 1 - dungeon[-1][-1])

Set the base case for the bottom-right cell in the DP table.

This line ensures the knight has at least 1 health after entering the destination cell, accounting for positive or negative dungeon values, anchoring the backward DP.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why must the DP computation proceed backward from the destination rather than forward from the start?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Dungeon Game from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Dungeon Game drill

or drill a free problem

1	`class Solution:`
2	`def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:`
3	`rows = len(dungeon)`
4	`cols = len(dungeon[0])`
5
6	`dp = [[0] * cols for _ in range(rows)]`
7
8	`dp[-1][-1] = max(1, 1 - dungeon[-1][-1])`
9
10	`for r in range(rows - 1, -1, -1):`
11	`for c in range(cols - 1, -1, -1):`
12
13	`if r == rows - 1 and c == cols - 1:`
14	`continue`
15
16	`down = dp[r+1][c] if r+1 < rows else float("inf")`
17	`right = dp[r][c+1] if c+1 < cols else float("inf")`
18
19	`need = min(down, right)`
20
21	`dp[r][c] = max(1, need - dungeon[r][c])`
22
23	`return dp[0][0]`

3	`rows = len(dungeon)`
4	`cols = len(dungeon[0])`
6	`dp = [[0] * cols for _ in range(rows)]`
8	`dp[-1][-1] = max(1, 1 - dungeon[-1][-1])`