174. Dungeon Game — DSA Atlas

174

HardTwo-Dimensional Dynamic Programming2D dynamic programming filled from bottom-right to top-leftReverse grid DP (min health from the goal backward)

Dungeon Game

A knight starts at the top-left of an m x n dungeon and must reach the princess at the bottom-right, moving only right or down. Each cell adds (positive) or subtracts (negative) health; if health ever drops to 0 or below the knight dies. Return the minimum initial health needed to guarantee survival to the goal.

Open official problem prompt ↗

In plain English

Find the smallest starting health so that, following some right/down path, the knight's health stays at least 1 in every cell including the goal.

Picture it like this

Planning a desert crossing where each oasis gives or drains water. To know how much water to carry when entering a checkpoint, you must first know how thirsty the road ahead is, so you plan backward from the destination.

Example

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Why: Starting with 7 health the path right,right,down,down keeps health positive at every step; 6 or less fails somewhere.

Constraints

m == dungeon.lengthn == dungeon[i].length1 <= m, n <= 200-1000 <= dungeon[i][j] <= 1000

Pattern lesson

See the pattern, then code

Reverse grid DP (min health from the goal backward)

↗

Two-Dimensional Dynamic Programming

Two changing dimensions, two sequences, grids, or two-index decisions.. Compute the minimum health required upon entering each cell so the knight can survive the rest of the journey. That depends on the cheaper of the two cells ahead, so fill the table from the goal backward.

New words, made simpleKnow these before the algorithm

Backward DP: Filling from the goal toward the start because requirements depend on the future
Entry health: dp[i][j]: minimum health the knight must have when stepping onto cell (i,j)
Floor of 1: Health must never fall to 0, so every entry requirement is clamped to at least 1

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Forward DP maximizing health

Fails: the best past health does not determine future survivability; the two objectives conflict.

Track the max health reachable at each cell moving right/down from the start.

Time O(m*n)Space O(m*n)

Best choiceBackward min-health DP

Correctly couples current cost with future need; each cell solved once.

From the goal backward, store the minimum entry health needed to survive the rest, clamped to >= 1.

Time O(m*n)Space O(m*n)

The rule we keep true

Invariant

dp[i][j] is the minimum health the knight must possess upon entering (i,j) so that some right/down path to the goal keeps health >= 1 throughout.

Why this is correct

Reasoning

On leaving (i,j) the knight steps to the cheaper of (i+1,j) or (i,j+1), whose requirement is known. Entering health minus the cell's effect must meet that requirement, and must itself be at least 1. Taking max(1, needed) enforces both, and backward order guarantees the successors are final.

The algorithm in three movesSay these aloud before coding

1Let dp[i][j] be the minimum health needed on entering cell (i,j) to reach the goal

enter goal (2,2) needing 6 to end at 1

2Health after the goal must be at least 1; pad the grid so the two cells just past the goal require 1

dp[0][1]=5, dp[0][2]=2 along the top

3dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])

dp[0][0] = max(1, min(5, dp[1][0]) + 2) = 7

4Return dp[0][0]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

-20

-31

-53

-104

106

307

-58

1 · Readcells past (2,2)

2 · AskWhat must health be just after the goal?

3 · Update statedp[3][2] = dp[2][3] = 1

4 · ResultSets the survival floor

Key takeaway

The dungeon grid; highlighted cells trace the survivable right,right,down,down path.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4-6Padded DP grid
An extra row and column of infinity, with the two cells just past the goal set to 1, encode the survival floor without special-casing borders.
2
Lines 7-11Backward fill
Iterating from bottom-right, each cell needs the cheaper future requirement minus its own effect, clamped to at least 1.
3
Lines 12Return start requirement
dp[0][0] is the minimum initial health.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A single positive cell still requires at least 1 health
An all-negative dungeon forces large starting health
A large positive cell cannot let entry health drop below 1 (the clamp handles it)

Common beginner mistakes

Doing a forward DP; the future dependency makes it wrong
Forgetting the max(1, ...) clamp and allowing non-positive health
Setting only one of the two goal-exit sentinels to 1 or using 0 instead of 1

Check your understanding

Why must this DP run backward from the goal instead of forward from the start?

Dungeon Game

Dungeon Game

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Two-Dimensional Dynamic Programming