Dungeon Game (LeetCode 174)

The problem

A knight starts at the top-left of a grid and must reach the princess at the bottom-right, moving only right or down. Each cell changes his health: negative values are damage, positive values are potions. If his health ever drops to 0 or below, he dies. Return the minimum health he must start with to get through.

Input:
-2  -3   3
-5 -10   1
10  30  -5

Output: 7

Going right, right, down, down, his health goes 7 → 5 → 2 → 5 → 6 → 1. He never drops to 0, and starting with 6 would leave him dead on the last cell.

How to think about it

Start with brute force. Try every right/down path, track the lowest health along each, and pick the path whose lowest point is the best. That is exponential in the grid size.

Why a forward DP fails. It’s tempting to run Minimum Path Sum from the top-left, tracking the best health so far. But two quantities matter, current health and lowest point reached, and a path that looks worse now can be better later thanks to a big potion. A forward table can’t pick one number per cell that’s correct for the future.

The key insight: work backwards from the goal. Let dp[i][j] be the minimum health needed on entering (i, j) to survive to the end. That depends only on what comes after, so it’s well defined. From (i, j) you go to the cheaper of the two next cells, needing min(dp[i+1][j], dp[i][j+1]) after this cell. So on entry you need that minus this cell’s value: need = min(down, right) - dungeon[i][j]. You must always have at least 1 HP, so dp[i][j] = max(1, need). A big potion can make need negative, but you still can’t enter with less than 1.

Which pattern is this? 2-D grid DP filled in reverse. The tell is “the minimum starting value”: the requirement depends on the future, so the base case is at the end.

Approach

1. Make an (R + 1) × (C + 1) table filled with infinity (the padding means “you can’t go this way”).
2. Set the two cells just past the princess, dp[R][C-1] and dp[R-1][C], to 1: you need 1 HP after the last cell.
3. For i from R - 1 down to 0, j from C - 1 down to 0: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]).
4. Return dp[0][0].

Solution

def calculate_minimum_hp(dungeon):
    R, C = len(dungeon), len(dungeon[0])
    dp = [[float('inf')]*(C+1) for _ in range(R+1)]   # padding = impossible move
    dp[R][C-1] = dp[R-1][C] = 1                   # need 1 HP after leaving the princess's cell
    for i in range(R-1, -1, -1):
        for j in range(C-1, -1, -1):
            need = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]   # cheaper next move, minus this cell
            dp[i][j] = max(1, need)               # never enter with less than 1 HP
    return dp[0][0]
# calculate_minimum_hp([[-2,-3,3],[-5,-10,1],[10,30,-5]]) -> 7

Dry run

The finished table for the example (the last row and column are padding):

Reading a few cells: the princess’s cell (2, 2) has value -5, so you need 1 - (-5) = 6. Cell (0, 2) has +3 and leads to 5, so 5 - 3 = 2. Cell (2, 0) has +10, so need is negative and it’s clamped to 1. The start needs min(5, 6) - (-2) = 7.

Complexity

• Time: O(R · C). Each cell is computed once.
• Space: O(R · C) for the table; one row of length C + 1 is enough if you roll it.

Edge cases and pitfalls

• Single positive cell ([[5]]) returns 1: you still need to be alive.
• Single negative cell ([[-5]]) returns 6.
• Forgetting max(1, …) lets a potion “pay back” health you never had, giving answers of 0 or less.
• Forward DP is the classic wrong approach; explain why the future decides the requirement.

Related problems

• Minimum Path Sum (LeetCode 64): the forward min-cost grid DP this problem looks like, but isn’t.
• Unique Paths II (LeetCode 63): right/down grid DP with blocked cells.
• Path With Minimum Effort (LeetCode 1631): another “minimise the worst point on a path” problem, solved with Dijkstra.