Dungeon Game

Dungeon Game is a classic grid-DP problem with a twist that breaks the obvious approach: you cannot fill the table from the start, you have to fill it backwards from the exit. Learning why forward DP fails here is the real lesson.

The slow way first

You might try to track the maximum health the knight could have at each cell, filling forward from the start. But that fails: a cell with the most health so far might force you onto a path that needs less health later. The two quantities, health-so-far and health-still-needed, are not the same, and greedily maximizing one does not minimize the other. Trying every path is correct but exponential.

The question to ask: standing on a cell, what is the minimum HP I must have entering it to survive the rest of the journey? That value only depends on the cells after it, so it must be computed back-to-front.

The idea: fill backwards from the exit

Let dp[i][j] be the minimum HP needed entering cell (i, j) to reach the exit alive. The knight leaves (i, j) toward whichever neighbor is cheaper, so:

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

The min picks the easier of the two exits. Subtracting dungeon[i][j] accounts for this cell damage or healing. The outer max(1, ...) enforces the rule that health never drops below 1, even when a cell heals a lot.

Walk through it

Step through the animation. The left grid is the dungeon; the right grid is dp, which fills in from the bottom-right. First the exit corner, then the last row (only move right) and last column (only move down), then the inner cells using min(down, right). The entrance cell dp[0][0] holds the answer, 7.

Pseudocode

dp[exit] = max(1, 1 - dungeon[exit])      # survive the final cell
for the last row, right to left:          # can only move right
    dp[i][j] = max(1, dp[i][j+1] - dungeon[i][j])
for the last column, bottom to top:       # can only move down
    dp[i][j] = max(1, dp[i+1][j] - dungeon[i][j])
for every inner cell, bottom-right to top-left:
    nxt = min(dp[i+1][j], dp[i][j+1])     # cheaper exit
    dp[i][j] = max(1, nxt - dungeon[i][j])
return dp[0][0]

The Python solution

def calculate_min_hp(dungeon):
    R, C = len(dungeon), len(dungeon[0])
    dp = [[0] * C for _ in range(R)]
    # exit cell
    need = 1 - dungeon[R - 1][C - 1]
    dp[R - 1][C - 1] = max(1, need)
    for j in range(C - 2, -1, -1):          # last row
        nxt = dp[R - 1][j + 1]
        dp[R - 1][j] = max(1, nxt - dungeon[R - 1][j])
    for i in range(R - 2, -1, -1):          # last column
        nxt = dp[i + 1][C - 1]
        dp[i][C - 1] = max(1, nxt - dungeon[i][C - 1])
    for i in range(R - 2, -1, -1):          # inner cells
        for j in range(C - 2, -1, -1):
            nxt = min(dp[i + 1][j], dp[i][j + 1])
            dp[i][j] = max(1, nxt - dungeon[i][j])
    return dp[0][0]

• dp[i][j] is the minimum HP needed entering (i, j) to survive to the end.
• The exit cell needs max(1, 1 - dungeon[exit]): enough so HP stays at least 1 after its damage.
• The last row and last column each have only one valid exit, so they use a single neighbor.
• Lines 15 to 16 are the heart: min of the two exits, then max(1, ...) to clamp health to at least 1.
• dp[0][0] is the answer: the minimum HP to start at the entrance.

Complexity

The space can be reduced to O(n) by keeping only the previous row, but the O(m*n) table is clearer and is what the animation shows.

When this pattern shows up

Practice