Problem Statement

Dungeon Game

A knight starts at the top-left corner of a grid and wants to reach the bottom-right corner. He can only move right or down. Each cell either heals him (a positive number) or hurts him (a negative number). His health changes as he walks, and if it ever drops to 0 or below, he dies. The question is: what is the smallest amount of health he can start with and still survive the whole trip? Here is the trick that makes this solvable: we work BACKWARDS, from the bottom-right cell back to the start. We build a table called dp, where dp[i][j] means "the smallest amount of health the knight needs to have the moment he steps onto cell (i,j), so that he can finish the rest of the path alive." Working backwards sounds odd, so here is the real-world picture. Imagine planning a road trip where you must arrive with at least a quarter tank of gas. You cannot know how much gas to start with until you first figure out how much each later leg of the trip burns. So you plan the last leg first, then the one before it, and so on, back to the start. That is exactly what we do here with health instead of gas.

hardDynamic ProgrammingDynamic ProgrammingTime: O(m*n) · Space: O(m*n)

Signals to notice

minimum starting health to reach endhealth ≥ 1 at every cellwork backward

Brute force first

Try all paths — O(2^(m+n)).

The key insight

DP from bottom-right to top-left. dp[i][j] = max(1, min(right,down) - dungeon[i][j]). O(mn).

Trace it on `dungeon=[[-2,-3,3],[-5,-10,1],[10,30,-5]]`

Fill bottom-right first: dp[2][2]=max(1,1-(-5))=6
Last row (right-to-left): dp[2][1]=max(1,6-30)=1; dp[2][0]=max(1,1-10)=1
Last col (bottom-up): dp[1][2]=max(1,6-1)=5; dp[0][2]=max(1,5-3)=2
dp[1][1]=max(1,min(dp[2][1]=1,dp[1][2]=5)-(-10))=max(1,11)=11
dp[1][0]=max(1,min(dp[2][0]=1,dp[1][1]=11)-(-5))=max(1,6)=6
dp[0][1]=max(1,min(dp[1][1]=11,dp[0][2]=2)-(-3))=max(1,5)=5
dp[0][0]=max(1,min(dp[1][0]=6,dp[0][1]=5)-(-2))=max(1,7)=7
return dp[0][0]=7

What must stay true

Working backward: each cell knows minimum health needed to survive from there to the end. Clamped to ≥ 1.

Shape of the loop

for i from m-1 down to 0:
  for j from n-1 down to 0:
    need = (last cell) ? 1 : min(dp[i+1][j], dp[i][j+1])   # missing neighbor = +inf
    dp[i][j] = max(1, need - dungeon[i][j])
return dp[0][0]

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Working forward — requires tracking both current and minimum health. Backward only needs one value.

Dynamic Programming Pattern