Compile Ready
Module 3 · Grid Dynamic Programming

Dungeon Game

HardProblem 11 of 30 11 min read ~30 min to solve LeetCode
Dynamic ProgrammingGrid DPReverse DPMatrix
Asked atAmazonGoogleMicrosoftMetaBloomberg

Problem Statement

A knight starts in the top-left cell of a dungeon and must rescue the princess in the bottom-right cell. The knight may move only right or down. Each cell either removes health with a negative value, adds health with a positive value, or does nothing with zero. The knight dies immediately if health ever drops to 0 or below. Return the minimum initial health needed to guarantee rescue.

Input

A 2D integer grid dungeon, where negative values are damage and positive values are healing.

Output

An integer: the minimum initial health the knight needs before entering the top-left cell.

Constraints

  • •m == dungeon.length
  • •n == dungeon[i].length
  • •1 <= m, n <= 200
  • •-1000 <= dungeon[i][j] <= 1000

Examples

Example 1

Input: 
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: With 7 initial health, the knight can follow a route that never drops below 1 and reaches the princess. Any smaller starting health fails on every valid route.

Example 2

Input: 
dungeon = [[0]]
Output: 1
Explanation: The knight must always have at least 1 health, even when the only room has no effect.

Example 3

Input: 
dungeon = [[100]]
Output: 1
Explanation: A healing start still requires at least 1 initial health before entering the room.

Learning Objectives

  • Define a reverse DP state as the health required before entering a cell.
  • Explain why forward accumulated-sum DP is insufficient for this problem.
  • Derive the bottom-right to top-left recurrence from future health requirements.
  • Use sentinel values to implement a 1D reverse grid DP cleanly.

Intuition

This problem is tricky because the best prefix is not enough information. A forward DP that stores maximum health gained so far, minimum damage so far, or best remaining health can choose a path that looks good early but fails after a later deep negative room. The required starting health at a cell depends on what must be true after leaving that cell, so it depends on the future.

Reverse the question. Instead of asking how much health do I have when I reach this cell, ask how much health must I have before entering this cell so that I can still survive from here to the princess. Now the future is already known if we fill from bottom-right to top-left.

If the cheaper future requirement among right and down is nextNeed, then entering the current cell with nextNeed - dungeon[i][j] health is enough after applying the room value. But health can never be below 1, so every state is clamped with max(1, ...).

Common mistakes

  • ×Trying to solve forward with one value per cell; different paths can have the same current sum but very different worst future damage.
  • ×Maximising total health collected instead of minimising the initial health needed to never die.
  • ×Forgetting to clamp each state to at least **1**.
  • ×Using top and left predecessors even though the correct dependency is future cells: down and right.
  • ×Initialising the princess cell as its raw dungeon value instead of the health required before entering it.

State Definition

Let dp[i][j] be the minimum health required before entering cell (i, j) so that the knight can reach the princess alive from that cell. The answer is dp[0][0].

This definition is intentionally future-facing. It stores a requirement, not a reward collected so far.

State Transition

At the princess cell, the knight must leave the room alive, so the required health is max(1, 1 - dungeon[m - 1][n - 1]).

For any other cell, choose the easier future between moving down and moving right:

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

We fill from bottom-right to top-left because dp[i][j] needs future states. A forward recurrence from top and left fails because it cannot summarise both current health and the minimum health ever seen along the path in one safe scalar without knowing future damage.

Solutions

Solution: Reverse 1D DP with sentinels

Store one row of required health values while scanning from bottom-right to top-left. Sentinel values make cells outside the dungeon impossible, except for one virtual cell next to the princess that represents needing 1 health after rescue.

Step-by-step

  1. Create need with cols + 1 entries and fill it with a very large value.
  2. Set need[cols - 1] = 1 so the princess cell can choose a valid virtual exit requirement.
  3. Process rows from bottom to top and columns from right to left.
  4. Let nextNeed be the smaller of the down requirement need[col] and the right requirement need[col + 1].
  5. Set need[col] = max(1, nextNeed - dungeon[row][col]).
  6. Return need[0] after the top-left cell is processed.
Time

O(m · n)

Space

O(n)

Every cell is processed once, and the DP stores required health for one row plus a sentinel.

Java implementation

Loading…

Dry Run

Sample input

dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]. The array includes an impossible sentinel at the far right and starts with need[2] = 1 for the virtual exit beside the princess.

celldungeon valuedown needright needneed after update
(2,2)-51inf[inf,inf,6,inf]
(2,1)30inf6[inf,1,6,inf]
(2,0)10inf1[1,1,6,inf]
(1,2)16inf[1,1,5,inf]
(1,1)-1015[1,11,5,inf]
(1,0)-5111[6,11,5,inf]
(0,2)35inf[6,11,2,inf]
(0,1)-3112[6,5,2,inf]
(0,0)-265[7,5,2,inf]

The top-left requirement becomes 7. The table stores how much health is needed before entering each cell, so positive rooms can reduce the requirement but never below 1.

Complexity Analysis

The reverse DP is O(m · n) time and O(n) space. The direction is not an optimization detail; it is required by the meaning of the state because each cell depends on future survival requirements.

Reverse 1D DP with sentinels

Time

O(m · n)

Space

O(n)

Every cell is processed once, and the DP stores required health for one row plus a sentinel.

Interview Tips

Spend time explaining why forward DP fails. A single forward value cannot decide between paths without knowing the worst future damage still ahead. Once you define the state as health needed before entering a cell, the backward recurrence becomes straightforward and shows strong DP judgment.

Likely follow-ups

  • How would you reconstruct a path that works with the minimum initial health?
  • What if the knight could move right, down, or diagonally down-right?
  • What if health were capped at a maximum value after healing rooms?
  • Can the same reverse-state idea help with other survival threshold problems?

Similar Problems

Minimum Path Sum
MediumA forward grid minimisation problem that highlights why Dungeon Game needs a different state.
Triangle
MediumAlso solves from future choices backward to the current state.
Unique Paths II
MediumSame grid boundary discipline, but with forward counting instead of reverse requirements.
Cherry Pickup
HardAnother hard grid DP where choosing the right state is the main challenge.

Key Takeaways

  • Dungeon Game is solved backward because the state depends on future survival needs.
  • Define **dp[i][j]** as required health before entering a cell, not health collected so far.
  • The recurrence chooses the easier future move and subtracts the current room value.
  • Every required-health state must be clamped to at least **1**.
Reusable template: Reverse grid requirement DP: define what must be true before entering each cell, seed the destination, fill from bottom-right to top-left, and clamp survival requirements to valid bounds.