LeetCode 174 - Dungeon Game

LeetCode Problem 174

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

This problem asks us to determine the minimum initial health a knight needs in order to safely travel through a dungeon and rescue a princess.

The dungeon is represented as a 2D grid where each cell contains an integer value:

• A negative value means the knight loses health because of demons.
• A positive value means the knight gains health through healing orbs.
• A zero means the room has no effect.

The knight starts in the top-left corner and wants to reach the bottom-right corner, where the princess is imprisoned. At every move, he can only travel right or down.

The important constraint is that the knight's health must always remain strictly greater than 0. If his health becomes 0 or negative at any point, he dies immediately.

We are not asked to maximize the knight's remaining health. Instead, we must determine the smallest initial health value that guarantees survival all the way to the princess.

Restating the Problem

We want to find the smallest starting HP such that, following an optimal path from (0,0) to (m-1,n-1), the knight never dies.

This is subtle because the best path is not necessarily the path with the highest total sum. A path that gives large healing later may still be impossible if the knight dies before reaching it.

For example:

[-100, +1000]

Even though the total gain is positive, the knight still needs at least 101 HP to survive the first room.

This tells us that the problem is fundamentally about survival constraints, not maximizing rewards.

Understanding the Constraints

The grid dimensions satisfy:

• 1 <= m, n <= 200

This means there can be up to:

200 × 200 = 40,000 cells

A brute-force path search would be infeasible because the number of possible right/down paths grows exponentially.

Each cell value lies within:

-1000 <= dungeon[i][j] <= 1000

The values are small enough for standard integer arithmetic.

The constraint sizes strongly suggest that we need a polynomial-time dynamic programming solution, ideally around O(m × n).

Important Edge Cases

Several edge cases can easily break a naive solution.

A single-cell dungeon is important because the knight starts and ends in the same room. If the value is negative, extra health is needed immediately. If it is zero or positive, the answer is always 1.

A dungeon filled with positive values is another key case. Even though the knight gains health everywhere, he still needs at least 1 HP initially because health must always stay positive.

Large negative values near the beginning of the path are dangerous because the knight may die before reaching later healing rooms.

Finally, the optimal route may not be the route with the largest total sum. A path with better survivability may temporarily avoid large damage even if its overall reward is smaller.

Approaches

Brute Force Approach

A brute-force solution would try every possible path from the top-left corner to the bottom-right corner.

For each path, we simulate the knight's journey and determine the minimum initial health needed to survive that specific sequence of rooms.

One way to compute the required HP for a path is to track the cumulative health changes and find the lowest point reached. If the minimum cumulative sum is -x, then we need at least x + 1 starting health.

Since the knight can only move right or down, the number of paths is:

C(m+n-2, m-1)

This grows exponentially for large grids.

For a 200 × 200 grid, brute force becomes completely impractical.

Key Insight

The key realization is that thinking forward is difficult, but thinking backward is easy.

Instead of asking:

"How much health do I have now?"

we ask:

"How much health must I have when entering this room to safely reach the princess?"

This transforms the problem into dynamic programming.

Suppose we are standing at cell (r, c).

We can move either:

• Right to (r, c+1)
• Down to (r+1, c)

If we already know the minimum health needed for those future cells, then:

required_health =
min(right_requirement, down_requirement)

because we will choose the cheaper path.

Then we adjust for the current room value:

needed = future_requirement - dungeon[r][c]

However, health can never fall below 1, so:

dp[r][c] = max(1, needed)

This naturally leads to a bottom-up dynamic programming solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(m+n)	Tries every valid path
Optimal Dynamic Programming	O(m × n)	O(m × n)	Computes minimum required health backward

Algorithm Walkthrough

Optimal Dynamic Programming Strategy

We define:

dp[r][c]

as:

The minimum health required when entering cell (r, c) so the knight can eventually rescue the princess.

We compute this table from bottom-right to top-left.

1. Initialize the DP table

Create an m × n table where dp[r][c] stores the minimum required HP for that cell. 2. Handle the princess cell

At the bottom-right corner, the knight must survive the room and still remain alive.

Formula:

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

Why?

• If the room is negative, extra health is needed.
• If the room is positive or zero, only 1 HP is required.

3. Fill the last row

In the last row, movement is only possible to the right.

Therefore:

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

4. Fill the last column

In the last column, movement is only downward.

Therefore:

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

5. Fill remaining cells

For interior cells, we choose the cheaper of the two future paths:

min_health_next =
min(dp[r+1][c], dp[r][c+1])

Then compute:

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

6. Return the answer

The top-left cell contains the minimum initial HP:

dp[0][0]

Why it works

The invariant is:

dp[r][c] always represents the minimum HP needed upon entering (r, c) to guarantee survival to the princess.

Since every state only depends on already-computed future states, and we always choose the cheaper valid future path, the recurrence guarantees optimality. The max(1, ...) condition ensures the knight never starts a room dead or with zero HP.

Python Solution

from typing import List

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        rows = len(dungeon)
        cols = len(dungeon[0])

        dp = [[0] * cols for _ in range(rows)]

        # Princess cell
        dp[rows - 1][cols - 1] = max(
            1,
            1 - dungeon[rows - 1][cols - 1]
        )

        # Last row
        for col in range(cols - 2, -1, -1):
            dp[rows - 1][col] = max(
                1,
                dp[rows - 1][col + 1] - dungeon[rows - 1][col]
            )

        # Last column
        for row in range(rows - 2, -1, -1):
            dp[row][cols - 1] = max(
                1,
                dp[row + 1][cols - 1] - dungeon[row][cols - 1]
            )

        # Remaining cells
        for row in range(rows - 2, -1, -1):
            for col in range(cols - 2, -1, -1):
                min_health_next = min(
                    dp[row + 1][col],
                    dp[row][col + 1]
                )

                dp[row][col] = max(
                    1,
                    min_health_next - dungeon[row][col]
                )

        return dp[0][0]

The implementation directly follows the dynamic programming strategy.

First, we allocate a dp matrix of the same size as the dungeon. Each entry represents the minimum health needed before entering that room.

We initialize the princess cell because it acts as the base case. From there, we process the last row and last column separately since those positions only have one valid move direction.

Finally, we fill the remaining cells in reverse order, bottom-right toward top-left. At every cell, we choose the cheaper future path and calculate how much health is needed to survive the current room.

The answer naturally appears in dp[0][0], which represents the minimum health required at the starting position.

Go Solution

func calculateMinimumHP(dungeon [][]int) int {
	rows := len(dungeon)
	cols := len(dungeon[0])

	dp := make([][]int, rows)
	for i := range dp {
		dp[i] = make([]int, cols)
	}

	// Princess cell
	dp[rows-1][cols-1] = max(
		1,
		1-dungeon[rows-1][cols-1],
	)

	// Last row
	for col := cols - 2; col >= 0; col-- {
		dp[rows-1][col] = max(
			1,
			dp[rows-1][col+1]-dungeon[rows-1][col],
		)
	}

	// Last column
	for row := rows - 2; row >= 0; row-- {
		dp[row][cols-1] = max(
			1,
			dp[row+1][cols-1]-dungeon[row][cols-1],
		)
	}

	// Remaining cells
	for row := rows - 2; row >= 0; row-- {
		for col := cols - 2; col >= 0; col-- {
			minHealthNext := min(
				dp[row+1][col],
				dp[row][col+1],
			)

			dp[row][col] = max(
				1,
				minHealthNext-dungeon[row][col],
			)
		}
	}

	return dp[0][0]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation mirrors the Python logic closely. Since Go does not provide built-in min and max functions for integers, helper functions are implemented manually.

The dp table is created using slices of slices. Since the problem guarantees a non-empty grid, no special nil handling is required.

Integer overflow is not a concern because the maximum possible health requirement remains safely within Go's integer range.

Worked Examples

Example 1

Input:

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

We build the DP table backward.

Step 1: Princess Cell

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

Cell	Value
(2,2)	6

Step 2: Fill Last Row

Position	Calculation	Result
(2,1)	max(1, 6 - 30)	1
(2,0)	max(1, 1 - 10)	1

Current DP:

	0	1	2
0	?	?	?
1	?	?	?
2	1	1	6

Step 3: Fill Last Column

Position	Calculation	Result
(1,2)	max(1, 6 - 1)	5
(0,2)	max(1, 5 - 3)	2

DP table:

	0	1	2
0	?	?	2
1	?	?	5
2	1	1	6

Step 4: Fill Interior Cells

Position	Calculation	Result
(1,1)	max(1, min(1,5) - (-10))	11
(1,0)	max(1, min(1,11) - (-5))	6
(0,1)	max(1, min(11,2) - (-3))	5
(0,0)	max(1, min(6,5) - (-2))	7

Final DP:

	0	1	2
0	7	5	2
1	6	11	5
2	1	1	6

Answer:

7

Example 2

Input:

[[0]]

Princess cell:

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

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Every cell is processed exactly once
Space	O(m × n)	DP table stores one value per grid cell

The algorithm visits each cell a constant number of times and performs only constant-time operations at each step. Since the grid contains m × n cells, the runtime is linear in the size of the input.

The additional memory usage comes from the dynamic programming table, which stores one integer for every cell.

Test Cases

sol = Solution()

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

assert sol.calculateMinimumHP(
    [[0]]
) == 1  # Example 2

# Single cell edge cases
assert sol.calculateMinimumHP(
    [[5]]
) == 1  # Positive single cell

assert sol.calculateMinimumHP(
    [[-5]]
) == 6  # Negative single cell

# All positive dungeon
assert sol.calculateMinimumHP(
    [[1, 2], [3, 4]]
) == 1  # Only minimum health required

# All negative dungeon
assert sol.calculateMinimumHP(
    [[-1, -2], [-3, -4]]
) == 8  # Continuous damage

# Single row
assert sol.calculateMinimumHP(
    [[-2, -3, 5]]
) == 6  # Only move right

# Single column
assert sol.calculateMinimumHP(
    [[-2], [-3], [5]]
) == 6  # Only move down

# Large healing after large damage
assert sol.calculateMinimumHP(
    [[-100, 1000]]
) == 101  # Must survive first room

# Optimal path is not max sum
assert sol.calculateMinimumHP(
    [[1, -3, 3], [0, -2, 0], [-3, -3, -3]]
) == 3  # Requires careful path selection

Test Summary

Test	Why
[[−2,−3,3],[-5,−10,1],[10,30,−5]]	Validates standard example
[[0]]	Smallest valid input
[[5]]	Single positive room
[[-5]]	Single damaging room
[[1,2],[3,4]]	All positive cells
[[-1,-2],[-3,-4]]	Continuous health loss
[[-2,-3,5]]	Single-row traversal
[[-2],[-3],[5]]	Single-column traversal
[[-100,1000]]	Large damage before healing
[[1,-3,3],[0,-2,0],[-3,-3,-3]]	Confirms optimal path selection

Edge Cases

A single-cell dungeon is easy to mishandle because the knight both starts and finishes in the same room. If the room contains a negative value such as -5, the knight must enter with enough HP to survive immediately, which means 6. The implementation handles this naturally through the base case initialization of the princess cell.

A dungeon with only positive values can cause logical mistakes if the implementation assumes extra health is always required. Even if every room heals the knight, health must still begin above zero. The max(1, ...) condition guarantees the minimum answer never drops below 1.

A case with large early damage followed by large healing can break greedy thinking. For example:

[-100, 1000]

Even though the total gain is positive, the knight still needs 101 HP to survive the first room. The backward DP formulation correctly captures this because it computes the minimum required health before entering each room, rather than focusing on total accumulated gain.

Another subtle edge case occurs when the path with the highest total reward is not optimal. A naive strategy might maximize total health gained, but survivability matters more than total sum. By minimizing the required future health at every step, the DP solution automatically chooses the safest path.