• 1 ≤ m, n ≤ 200
• -1000 ≤ dungeon[i][j] ≤ 1000
• Movement is right or down only
• Health must stay at 1 or above at every cell, including the starting and final cells

It looks like every other grid problem: right and down, add up the cells, optimise. It is not, and the reason is worth understanding deeply, because it teaches the most important rule about choosing a state.

We want the minimum starting health. Health must never touch zero — not at the end of the journey, at every single cell along the way. So a path is not scored by its total; it is scored by its worst moment.

The instinct is to do what we always do: sweep forward from the top-left, storing at each cell something like "the best health I could have arriving here". Let us try to make that work and watch it fail.

Take this dungeon:

 -2  -3   3
 -5 -10   1
 10  30  -5

Consider two routes to the cell containing 1 at position (1,2):

That comparison was easy. Now the problem. Suppose two routes arrive at the same cell where route A has a better running total but suffered a worse dip, while route B has a worse total but never dipped much. Which one should we keep? Neither dominates. Keeping the better total can be wrong, because the dip might have required an enormous starting health. Keeping the smaller dip can be wrong, because the poorer total will demand more health later.

That means "best health arriving here" is not a valid state at all. Two paths arriving at the same cell do not have the same future requirement, so the cell alone does not determine what comes next — and that is precisely the condition a state must satisfy. You could patch it by carrying both the current health and the worst dip so far, but then the state has a numeric dimension whose range is enormous, and the table becomes unbuildable.

State Definition: f(r, c) is the minimum health the knight must have at the moment he enters cell (r, c) in order to survive from there to the princess. By definition this is at least 1, since he must be alive on arrival.

Now derive the recurrence. Suppose he enters (r, c) with health h. Entering applies the cell's value, so afterwards he has h + dungeon[r][c]. He then steps to whichever neighbour he chooses, and to survive he must arrive there with at least that neighbour's requirement. He will naturally pick the cheaper neighbour, so let

need_next = min( f(r+1, c), f(r, c+1) )

Then he needs h + dungeon[r][c] >= need_next, which rearranges to

h >= need_next - dungeon[r][c]

And on top of that he must be alive on entry, so h >= 1. Putting both together:

f(r, c) = max( 1, need_next - dungeon[r][c] )

That max(1, ...) is doing real work. If the cell is a big health potion, the requirement computed by the subtraction can go to zero or negative — meaning "you could have arrived on fumes". But you cannot arrive with zero health, because you would already be dead. Clamping to 1 encodes that rule exactly.

Base case: at the princess's cell (m-1, n-1) there is no next step, so he only needs to survive entering it: f(m-1, n-1) = max(1, 1 - dungeon[m-1][n-1]). If the final cell is +5 he needs just 1; if it is −5 he needs 6.

The answer is f(0, 0).

def calculate_minimum_hp(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    INF = float('inf')
    memo = {}

    def f(r, c):
        if r >= m or c >= n: return INF                 # off the grid
        if r == m - 1 and c == n - 1:
            return max(1, 1 - dungeon[r][c])
        if (r, c) in memo: return memo[(r, c)]
        need_next = min(f(r + 1, c), f(r, c + 1))
        memo[(r, c)] = max(1, need_next - dungeon[r][c])
        return memo[(r, c)]

    return f(0, 0)

Now the table. Let dp[r][c] hold what f(r, c) returned — the health needed on entering (r, c). Swap the calls for reads:

dp[r][c] = max( 1, min(dp[r+1][c], dp[r][c+1]) - dungeon[r][c] )

Each cell reads the cell below and the cell to its right, both at larger indices. So fill from the bottom-right corner backwards — rows bottom-to-top, columns right-to-left — and both neighbours are ready when you reach (r, c). The base case is folded in with sentinels, explained just below the code. The answer is dp[0][0]:

def calculate_minimum_hp(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    INF = float('inf')

    # one extra row and column of INF so the corner needs no special case
    dp = [[INF] * (n + 1) for _ in range(m + 1)]
    dp[m][n - 1] = 1          # stepping "past" the princess downward costs nothing extra
    dp[m - 1][n] = 1          # ... nor rightward

    for r in range(m - 1, -1, -1):
        for c in range(n - 1, -1, -1):
            need_next = min(dp[r + 1][c], dp[r][c + 1])
            dp[r][c] = max(1, need_next - dungeon[r][c])

    return dp[0][0]

The two sentinel cells set to 1 are a neat trick: they make the princess's cell obey the same formula as every other cell, since min(1, INF) = 1 gives max(1, 1 - dungeon[last]) automatically. Everything else off the grid stays infinite and is never chosen.

Each cell reads the cell below and the cell to its right, so a single array swept right-to-left works: when you compute position c, the array still holds the row below at index c, and already holds this row's value at index c+1.

def calculate_minimum_hp(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    INF = float('inf')
    dp = [INF] * (n + 1)
    dp[n - 1] = 1                                # sentinel for the princess's row

    for r in range(m - 1, -1, -1):
        for c in range(n - 1, -1, -1):
            need_next = min(dp[c], dp[c + 1])    # dp[c] is still the row below
            dp[c] = max(1, need_next - dungeon[r][c])
        dp[n] = INF                              # keep the right-hand sentinel clean

    return dp[0]

Cell (2,2) = -5: max(1, 1 - (-5)) = 6. He must enter the princess's cell with 6.
Cell (2,1) = 30: the only next step is right, needing 6. max(1, 6 - 30) = max(1, -24) = 1. The potion is huge, so 1 health suffices — clamped, as promised.
Cell (2,0) = 10: next is (2,1) needing 1. max(1, 1 - 10) = 1.
Cell (1,2) = 1: the only next step is down to (2,2) needing 6. max(1, 6 - 1) = 5.
Cell (1,1) = -10: next is min(down (2,1)=1, right (1,2)=5) = 1. max(1, 1 + 10) = 11.
Cell (1,0) = -5: next is min(down (2,0)=1, right (1,1)=11) = 1. max(1, 1 + 5) = 6.
Cell (0,2) = 3: next is down (1,2)=5. max(1, 5 - 3) = 2.
Cell (0,1) = -3: next is min(down (1,1)=11, right (0,2)=2) = 2. max(1, 2 + 3) = 5.
Cell (0,0) = -2: next is min(down (1,0)=6, right (0,1)=5) = 5. max(1, 5 + 2) = 7.

Answer 7. Verify it forwards along the chosen route right, right, down, down: start 7 → enter −2 leaves 5 → enter −3 leaves 2 → enter 3 leaves 5 → enter 1 leaves 6 → enter −5 leaves 1. Alive at every step, and starting with 6 would have died on the final cell. The backward table and the forward simulation agree.

This is the page to remember when a table refuses to work.

The rule a state must satisfy is: once you know the state, the rest of the problem must not care how you got there. Whenever you can construct two histories that reach the same cell but face genuinely different futures, your state is wrong. You then have exactly two options — add whatever is missing to the state, or change the direction of the question so the missing information stops mattering.

Here, adding to the state was impractical, and reversing worked perfectly. That reversal is a repeatable move, and its signature is easy to spot: the objective involves a constraint that must hold at every step, rather than only at the end. Minimum required resource, minimum initial fuel, latest safe departure time — all of these are naturally computed backwards from the goal, because a requirement propagates backwards while an accumulation propagates forwards.

The deciding factor is not the grid; it is whether the thing you are optimising is a total or a worst case. A plain sum can be minimised forward or backward — either is fine. A constraint that must hold at every single step, like survival here, is what forces the backward direction.