LeetCode 174: Dungeon Game

Problem Restatement

We are given a 2D grid:

dungeon

A knight starts at the top-left cell:

(0, 0)

and wants to rescue the princess at the bottom-right cell.

The knight may move only:

Each cell changes the knight’s health:

The knight dies immediately if health becomes:

<= 0

We must return the minimum initial health required so the knight can reach the princess alive.

LeetCode guarantees the grid dimensions are at most 200 x 200. (leetcode.com)

Input and Output

Example function shape:

def calculateMinimumHP(dungeon: list[list[int]]) -> int:
    ...

Examples

Example 1:

dungeon = [
    [-2, -3,  3],
    [-5, -10, 1],
    [10, 30, -5]
]

The optimal path is:

RIGHT -> RIGHT -> DOWN -> DOWN

Health changes:

The minimum starting health that keeps health positive throughout is:

7

Example 2:

dungeon = [[0]]

No damage occurs.

The knight still needs at least:

1

health to survive.

Return:

1

First Thought: Forward Dynamic Programming

One possible idea is:

dp[i][j] = best health when reaching cell (i, j)

But this does not work well.

The problem is that maximizing current health does not guarantee future survival.

Example:

large positive now
huge negative later

A locally good path may still fail later.

We need to think backward.

Key Insight

Instead of asking:

How much health do we have here?

ask:

How much health must we have before entering this cell?

This reverse perspective makes the transitions clean.

Define:

dp[i][j]

as the minimum health needed before entering cell (i, j) so the knight can still reach the princess alive.

The knight may move:

right
down

So from (i, j) we need enough health to survive whichever next cell requires less health.

Suppose the next required health is:

need

If the current cell gives:

dungeon[i][j]

then before entering this cell we need:

need - dungeon[i][j]

But health must never fall below 1.

So:

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

Reverse Dynamic Programming Transition

For a normal cell:

need = min(dp[i + 1][j], dp[i][j + 1])

because we choose the better next direction.

Then:

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

Base Case

At the princess cell:

(m - 1, n - 1)

Suppose the cell value is:

x

After entering the cell, health must remain at least 1.

So before entering, we need:

max(1, 1 - x)

Examples:

Algorithm

Let:

m = number of rows
n = number of columns

Create:

dp[m][n]

where:

dp[i][j]

stores the minimum health required before entering (i, j).

Fill the table backward:

1. Initialize the princess cell.
2. Fill the last row.
3. Fill the last column.
4. Fill the remaining cells from bottom-right to top-left.

Return:

dp[0][0]

Walkthrough

Use:

dungeon = [
    [-2, -3,  3],
    [-5, -10, 1],
    [10, 30, -5]
]

Start from bottom-right:

dp[2][2] = max(1, 1 - (-5))
          = 6

Last row:

dp[2][1] = max(1, 6 - 30)
          = 1

dp[2][0] = max(1, 1 - 10)
          = 1

Last column:

dp[1][2] = max(1, 6 - 1)
          = 5

dp[0][2] = max(1, 5 - 3)
          = 2

Now inner cells.

Cell (1,1):

need = min(1, 5) = 1

dp[1][1] = max(1, 1 - (-10))
          = 11

Cell (1,0):

need = min(1, 11) = 1

dp[1][0] = max(1, 1 - (-5))
          = 6

Cell (0,1):

need = min(11, 2) = 2

dp[0][1] = max(1, 2 - (-3))
          = 5

Cell (0,0):

need = min(6, 5) = 5

dp[0][0] = max(1, 5 - (-2))
          = 7

Return:

7

Correctness

The dynamic programming state:

dp[i][j]

represents the minimum health needed before entering cell (i, j) so the knight can still reach the princess alive.

At the princess cell, the knight must leave the cell with health at least 1. Therefore:

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

For any other cell, the knight may move right or down. The next step should minimize the required health, so the algorithm chooses:

min(dp[i + 1][j], dp[i][j + 1])

Suppose this value is need.

After applying the current cell’s effect:

dungeon[i][j]

the knight must still have at least need health. Therefore, before entering the current cell, the knight needs:

need - dungeon[i][j]

health.

Because health must always stay positive, the minimum valid health is at least 1. Thus:

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

The table is filled backward, so every required future state is already known when computing the current state.

Therefore, dp[0][0] equals the minimum initial health required to rescue the princess.

Complexity

Let:

m = number of rows
n = number of columns

Implementation

class Solution:
    def calculateMinimumHP(self, dungeon: list[list[int]]) -> int:
        m = len(dungeon)
        n = 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):
                need = min(
                    dp[i + 1][j],
                    dp[i][j + 1],
                )

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

        return dp[0][0]

Code Explanation

The DP table stores minimum required health before entering each cell:

dp = [[0] * n for _ in range(m)]

Initialize the princess cell:

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

The last row may move only right:

dp[m - 1][j]

depends on:

dp[m - 1][j + 1]

The last column may move only down:

dp[i][n - 1]

depends on:

dp[i + 1][n - 1]

Inner cells choose the cheaper future path:

need = min(
    dp[i + 1][j],
    dp[i][j + 1],
)

Then compute the health needed before entering the current cell:

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

Finally:

return dp[0][0]

returns the minimum initial health.

Space Optimization

We only need the current row and the next row.

So space can be reduced to:

O(n)

using a 1D DP array.

Testing

def run_tests():
    sol = Solution()

    assert sol.calculateMinimumHP([
        [-2, -3, 3],
        [-5, -10, 1],
        [10, 30, -5],
    ]) == 7

    assert sol.calculateMinimumHP([[0]]) == 1

    assert sol.calculateMinimumHP([[100]]) == 1

    assert sol.calculateMinimumHP([[-5]]) == 6

    assert sol.calculateMinimumHP([
        [1, -3, 3],
        [0, -2, 0],
        [-3, -3, -3],
    ]) == 3

    print("all tests passed")

run_tests()