Dungeon Game: Reverse DP for Minimum Health

A knight starts in the top-left cell of an m x n grid and must reach the bottom-right cell to rescue the princess. Each cell contains an integer: negative values deal damage, positive values restore health. The knight can only move right or down. At every point along the path, the knight's health must be at least 1. Find the minimum initial health the knight needs to reach the princess alive.

This is LeetCode 174: Dungeon Game, and it is one of the trickiest grid DP problems because it forces you to think backwards. If you have solved Minimum Path Sum or Unique Paths, you already know how to fill a 2D table. But this time, forward DP does not work. You need to fill from the destination back to the start.

For the grid [[-2,-3,3],[-5,-10,1],[10,30,-5]], the answer is 7. The knight takes the path right, right, down, down. Starting with 7 HP: 7 + (-2) = 5, 5 + (-3) = 2, 2 + 3 = 5, 5 + 1 = 6, 6 + (-5) = 1. Health never drops below 1.

Why forward DP fails

Your first instinct might be to apply the same approach as Minimum Path Sum: define dp[i][j] as something computed from the top-left corner. But what should that value represent?

If you define dp[i][j] as the minimum initial health to reach (i, j), you run into a problem. The health you need at (i, j) depends not just on what happened before, but also on what will happen after. A path that arrives at (i, j) with very little health might encounter a huge heal later, while a path that arrives with plenty of health might hit a devastating damage cell. You cannot decide the optimal initial health at (i, j) without knowing the future.

This is the key insight: the constraint is about surviving the entire path, not just reaching an intermediate cell. Forward DP computes accumulated cost (or health) from the start, but it cannot account for future damage. You need to work from the end backward, where the future is already settled.

The reverse DP approach

Define dp[i][j] as the minimum health the knight needs when entering cell (i, j) to survive all the way to the princess at the bottom-right corner.

Starting from the princess cell and working backward:

• Base case: at the princess cell (m-1, n-1), the knight needs enough health to survive that cell and still have at least 1 HP. So dp[m-1][n-1] = max(1, 1 - grid[m-1][n-1]).
• Transition: from cell (i, j), the knight moves right to (i, j+1) or down to (i+1, j). The knight picks whichever neighbor requires less health. The health needed at (i, j) is: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - grid[i][j]).
• Last row: can only go right, so dp[i][j] = max(1, dp[i][j+1] - grid[i][j]).
• Last column: can only go down, so dp[i][j] = max(1, dp[i+1][j] - grid[i][j]).

The max(1, ...) ensures the knight always has at least 1 HP. Even if a cell gives a massive heal, you still need to be alive to receive it.

Walkthrough

Let's trace through the grid [[-2,-3,3],[-5,-10,1],[10,30,-5]] filling the DP table from the bottom-right corner to the top-left.

The answer is dp[0][0] = 7. The knight starts with 7 HP and follows the path right, right, down, down, arriving at the princess with exactly 1 HP remaining.

Python solution

def calculateMinimumHP(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    dp = [[0] * n for _ in range(m)]

    dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1])

    for j in range(n - 2, -1, -1):
        dp[m - 1][j] = max(1, dp[m - 1][j + 1] - dungeon[m - 1][j])

    for i in range(m - 2, -1, -1):
        dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1])

    for i in range(m - 2, -1, -1):
        for j in range(n - 2, -1, -1):
            dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])

    return dp[0][0]

The structure mirrors Minimum Path Sum, but everything is reversed: you iterate from bottom-right to top-left, and the recurrence subtracts the cell value (since you are computing what you need before entering the cell, not what you have accumulated after leaving it).

Why max(1, ...) is essential

Consider a cell with grid[i][j] = 100 and dp[i+1][j] = 5. Without the floor: dp[i][j] = 5 - 100 = -95. That would mean you could enter the cell with -95 HP, which makes no sense. The knight must always have at least 1 HP. The max(1, ...) clamps every DP value to a minimum of 1, ensuring the knight is alive at every step.

This minimum-to-survive calculation is the core building block that distinguishes the Dungeon Game from simpler grid DP problems. In Minimum Path Sum, you never have a survivability constraint, so you never need a floor.

Complexity analysis

Time: O(m * n). Every cell is visited exactly once during the backward pass.

Space: O(m * n) for the full 2D table. You can optimize to O(n) using the same single-row trick from Minimum Path Sum. Since each cell only depends on the cell below (previous row in the backward pass) and the cell to the right (already updated in the current row), a single 1D array of length n is sufficient. Process rows from bottom to top, and within each row, process columns from right to left.

def calculateMinimumHP(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    dp = [0] * n

    dp[n - 1] = max(1, 1 - dungeon[m - 1][n - 1])
    for j in range(n - 2, -1, -1):
        dp[j] = max(1, dp[j + 1] - dungeon[m - 1][j])

    for i in range(m - 2, -1, -1):
        dp[n - 1] = max(1, dp[n - 1] - dungeon[i][n - 1])
        for j in range(n - 2, -1, -1):
            dp[j] = max(1, min(dp[j], dp[j + 1]) - dungeon[i][j])

    return dp[0]

The building blocks

This problem is built on two reusable patterns:

Reverse DP (fill from destination to source). When the constraint depends on the future path, not the past, you cannot fill from the start. You fill from the end so that every cell's value already accounts for everything that comes after it. This pattern appears whenever the problem asks for a minimum starting quantity to survive a journey, rather than a minimum total cost.

Minimum-to-survive calculation. The max(1, needed - cell_value) formula ensures the knight is always alive. This is a specific instance of a more general pattern: when a variable has a lower bound (health cannot drop below 1, budget cannot go negative), you apply a floor at each step. Without the floor, the DP values can go negative and produce incorrect results.

These two building blocks combine to handle the Dungeon Game, but each one appears independently in other problems as well. Reverse DP shows up in problems where you need to find the minimum starting resource. The survival floor shows up in any problem with a "must stay above zero" constraint.

Edge cases to watch for

• Single cell (1x1): if grid[0][0] = -5, the answer is 6. If grid[0][0] = 5, the answer is 1. You always need at least 1 HP.
• All positive values: every cell heals the knight. The answer is always 1, since the knight never takes damage.
• All negative values: every cell deals damage. The knight must have enough HP to absorb the entire optimal path's damage and still have 1 HP at the end.
• Large grid (up to 200x200): the O(m * n) algorithm handles this easily. No performance concerns.
• Zero-value cells: grid[i][j] = 0 means no health change. The max(1, ...) still applies, so the knight passes through with no adjustment.

From understanding to recall

You have seen why forward DP fails, traced the reverse DP table, and understand the max(1, ...) survival floor. But understanding the backward fill direction is different from producing it under pressure.

In an interview, you need to quickly identify that the future-dependency makes forward DP impossible, decide to fill from the bottom-right, write the recurrence with max(1, min(...) - grid[i][j]), handle the base cases for the last row and last column, and implement the space optimization if asked. That fluency comes from practice, not reading.

Spaced repetition closes the gap. You revisit this problem at increasing intervals, each time writing the reverse DP setup from memory. After a few reps, the pattern of "survive to the end, so fill backwards" becomes automatic. You see a survivability constraint and your hands know to reverse the fill direction.

The reverse DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding problems randomly and hoping the patterns stick.

Related posts

• Minimum Path Sum - The forward version of grid DP optimization, and the natural predecessor to this problem
• Unique Paths - The counting version of grid DP, teaching the 2D table structure before adding optimization