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.

Dungeon Game - LeetCode Solution & Explanation

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.

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

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. At each cell, compute the minimum health needed to enter it so that moving forward (right or down) the knight never dies. This transforms the problem into a DP over the grid, where each cell's state depends on the minimum health required in its neighbors.

Optimal Approach

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.

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.

Solution

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

1

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.

2

Compute Minimum Health Requirements Backward for Each Cell

10for r in range(rows - 1, -1, -1):
  for c in range(cols - 1, -1, -1):
      if r == rows - 1 and c == cols - 1:
          continue
      down = dp[r+1][c] if r+1 < rows else float("inf")
      right = dp[r][c+1] if c+1 < cols else float("inf")
      need = min(down, right)
      dp[r][c] = max(1, need - dungeon[r][c])

Objective

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

Key Insight

At each cell, the knight must have enough health to move either right or down safely. The minimum health needed is the lesser of the two neighbors' requirements minus the current cell's dungeon value, but never less than 1. Using max(1, ...) enforces the health floor. This backward propagation ensures the knight can survive all paths from the current cell to the destination.

Interview Quick-Check

Core Logic

For each cell, dp[r][c] = max(1, min(dp[r+1][c], dp[r][c+1]) - dungeon[r][c]) computes the minimum health needed to enter safely.

State & Boundaries

Use float('inf') for out-of-bound neighbors to simplify min calculations at edges.

Common Pitfalls & Bugs

Skipping the base case cell or miscalculating neighbors leads to incorrect DP values.

3

Return the Minimum Initial Health Required at Start

23	`return dp[0][0]`

Objective

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

Key Insight

After filling the DP table, dp[0][0] holds the minimum health required at the start cell to guarantee survival through any path to the destination. Returning this value completes the solution.

Interview Quick-Check

Core Logic

Returning dp[0][0] provides the minimum initial health required to survive the dungeon starting at the top-left.

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.

Line 6 Core

dp = [[0] * cols for _ in range(rows)]

Initialize a 2D DP table with zeros matching the dungeon's dimensions.

The DP table stores the minimum health needed to enter each cell, enabling bottom-up computation of the solution.

Line 16 Core

down = dp[r+1][c] if r+1 < rows else float("inf")

Calculate the minimum health needed from the cell below, or infinity if out of bounds.

Using infinity for out-of-bound neighbors simplifies min calculations and handles edge cases cleanly.

Line 17 Core

right = dp[r][c+1] if c+1 < cols else float("inf")

Calculate the minimum health needed from the cell to the right, or infinity if out of bounds.

This complements the downward neighbor calculation, ensuring both possible moves are considered for DP.

Line 23 Core

return dp[0][0]

Return the minimum initial health required at the start cell.

After filling the DP table, dp[0][0] holds the final answer representing the minimum health needed to survive the entire dungeon.

Line 13 Core

if r == rows - 1 and c == cols - 1:

Skip the bottom-right cell since it's already initialized.

Avoids overwriting the base case, preserving the correct starting point for DP computation.

Line 19 Core

need = min(down, right)

Determine the minimum health needed from the next step (down or right).

Choosing the minimum of the two neighbors reflects the knight's ability to choose the optimal path forward.

Line 14 Standard

continue

Continue to the next iteration without processing the base cell.

This control flow ensures the base case remains intact and the DP logic applies only to other cells.

Line 10 Standard

for r in range(rows - 1, -1, -1):

Iterate over rows backward from bottom to top.

Backward iteration aligns with the DP approach of computing minimum health needed from the destination back to the start.

Line 11 Standard

for c in range(cols - 1, -1, -1):

Iterate over columns backward from right to left.

Backward iteration over columns complements the row iteration to fill the DP table from bottom-right to top-left.

Line 3 Basic

rows = len(dungeon)

Calculate the number of rows in the dungeon grid.

Knowing the number of rows is essential for iterating over the grid and setting up the DP table dimensions.

Line 4 Basic

cols = len(dungeon[0])

Calculate the number of columns in the dungeon grid.

Knowing the number of columns is essential for iterating over the grid and setting up the DP table dimensions.

Test Your Understanding

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

Because the minimum health needed at each cell depends on the minimum health required in the next steps (right and down), which are unknown when moving forward. Backward computation ensures these future requirements are known and can be used to calculate the current cell's requirement.

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

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])`

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]`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize DP Table and Set Base Case at Destination

Compute Minimum Health Requirements Backward for Each Cell

Return the Minimum Initial Health Required at Start

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.