Dungeon Game LeetCode 174 — Reverse DP

LeetCode 174 Dungeon Game places a knight in the top-left cell (0, 0) of an m×n grid dungeon. A princess is locked in the bottom-right cell (m-1, n-1). Each room in the dungeon contains an integer: negative values (demons) drain the knight's health, positive values (magic orbs) restore health, and zero leaves health unchanged. The knight moves only right or down at each step. Your task is to find the minimum initial health the knight must start with so that health is at least 1 in every room visited, including the starting room and the princess's room.

The health constraint is strict: the knight dies if health drops to 0 or below at any point during the path, not just at the end. This means the knight cannot "bank" extra health from later healing rooms to compensate for an early near-death experience — if health ever hits 0 mid-path, the knight is dead. The knight must maintain HP ≥ 1 at every single cell on the chosen path from (0,0) to (m-1,n-1).

This problem is a grid DP variant with a non-standard objective. Unlike Minimum Path Sum (LeetCode 64), which asks for the minimum total cost to reach the bottom-right, Dungeon Game asks for the minimum initial value such that a running total never drops below 1. This subtle difference is what makes forward DP — the natural instinct — incorrect, and reverse DP — thinking from the destination backward — the right approach.

The instinctive approach to a grid path problem is forward DP: define dp[i][j] as some optimal value when reaching cell (i, j), fill from (0,0) to (m-1,n-1), and read the answer at the bottom-right. For Minimum Path Sum this works perfectly because the cost to reach (i,j) depends only on costs already incurred, not on what lies ahead. But for Dungeon Game the same forward approach breaks down fundamentally.

Consider a dungeon where cell (0,0) has value -5 and cell (1,0) has value +100. A forward DP might record that arriving at (1,0) requires starting with health 6 (to survive the -5 at (0,0)). But if cell (0,1) has value -50 and leads to a healing corridor that ends at (m-1,n-1) with large positive values, the forward DP cannot correctly account for the minimum starting HP for that path — because the minimum HP needed depends on the worst point in the remaining path, which hasn't been visited yet.

The core problem is a dependency inversion: the minimum starting HP at (0,0) depends on the minimum HP needed at (0,1) or (1,0), which in turn depends on what comes after. "How much HP do I need here?" is a question answered by looking forward, not backward. Forward DP naturally accumulates past information, but this problem requires future information. Reverse DP resolves this by starting at the destination and propagating "minimum HP needed at this cell" backward to the source.

Define dp[i][j] as the minimum health the knight must have upon entering room (i, j) in order to reach the princess alive. The answer we want is dp[0][0] — the minimum HP needed at the starting cell. We fill the table from the bottom-right corner to the top-left, so each cell can rely on already-computed values for the cells below and to the right.

The recurrence is: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). The min(dp[i+1][j], dp[i][j+1]) picks the better next step — the direction requiring less HP. Subtracting dungeon[i][j] accounts for the room's effect: if the room heals (+value), entering it requires less HP; if it hurts (-value), entering requires more HP. The max(1, ...) enforces the constraint that HP must always be at least 1, even in rooms with large positive values.

The subtraction and the max(1, ...) work together precisely. If dungeon[i][j] = +10 and dp[i+1][j] = 3, then min(...) - dungeon[i][j] = 3 - 10 = -7. Without the max(1, ...) we would incorrectly conclude the knight can enter with negative HP. The max(1, ...) clamps this to 1, reflecting that the room heals so generously that the knight only needs 1 HP to enter. If dungeon[i][j] = -5 and dp[i+1][j] = 3, then 3 - (-5) = 8, so the knight needs 8 HP to enter.

The base case is the bottom-right corner: dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1]). The knight must exit this room with HP ≥ 1, so the minimum HP upon entering is max(1, 1 - dungeon[m-1][n-1]). If the room heals (dungeon value > 0), entering with 1 HP is sufficient. If the room drains (dungeon value < 0), the knight needs more than 1 HP to survive.

For cells in the last row (i = m-1, j < n-1), the knight can only move right, so dp[i][j] = max(1, dp[i][j+1] - dungeon[i][j]). For cells in the last column (j = n-1, i < m-1), the knight can only move down, so dp[i][j] = max(1, dp[i+1][j] - dungeon[i][j]). These are edge cases of the general formula if we set out-of-bounds dp values to infinity — the min() naturally selects the valid neighbor.

The cleanest implementation uses a (m+1)×(n+1) table with dp[m][j] = infinity for all j and dp[i][n] = infinity for all i, except dp[m][n-1] = 1 and dp[m-1][n] = 1. This sentinel setup makes the recurrence uniform for all cells including the last row and column, eliminating special-case branches. Alternatively, initialize the actual base case dp[m-1][n-1] first, then fill last row and last column before the general loop.

The 2D DP table has O(m·n) space. Since each row only depends on the row below it, a 1D array of length n+1 suffices. Process rows from bottom (i = m-1) to top (i = 0), and within each row process columns from right (j = n-1) to left (j = 0). The 1D array dp[j] always holds the value for the current row at column j, and dp[j+1] holds the already-computed value for the same row one step to the right.

Before starting the loop, initialize the 1D array: dp[n] = infinity for j=0..n-1, and set dp[n-1] appropriately for the last row. As you process each cell (i, j), dp[j] = max(1, min(dp[j], dp[j+1]) - dungeon[i][j]). Here dp[j] (before update) holds the value from the row below at column j (dp[i+1][j] in 2D notation), and dp[j+1] holds the already-updated value for the same row at column j+1 (dp[i][j+1] in 2D notation). The in-place update works because of the right-to-left processing order.

This space optimization mirrors the pattern used in Minimum Path Sum and Unique Paths: any 2D grid DP where dp[i][j] depends only on dp[i+1][j] and dp[i][j+1] (or their forward equivalents) can be reduced to O(n) space with careful in-place updates. Recognizing this pattern across the grid DP family makes each new problem faster to implement correctly.

Python (space-optimized): m, n = len(dungeon), len(dungeon[0]); dp = [float('inf')] * (n + 1); dp[n-1] = 1; for i in range(m-1, -1, -1): for j in range(n-1, -1, -1): need = min(dp[j], dp[j+1]) - dungeon[i][j]; dp[j] = max(1, need). The initialization dp[n-1] = 1 anchors the boundary: at the start of the last row loop, dp[j] for j < n-1 contains infinity (representing "no valid move below for last row cells"), and dp[n-1] = 1 represents the sentinel next to the princess's room. Time O(m·n), space O(n).

Java (space-optimized): int m = dungeon.length, n = dungeon[0].length; int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[n-1] = 1; for (int i = m-1; i >= 0; i--) { for (int j = n-1; j >= 0; j--) { int next = Math.min(dp[j], dp[j+1]); dp[j] = Math.max(1, next == Integer.MAX_VALUE ? 1 : next - dungeon[i][j]); } } return dp[0]; Note the Integer.MAX_VALUE guard: subtracting dungeon[i][j] from MAX_VALUE would overflow. In practice only the in-bounds neighbors are ever MAX_VALUE (out-of-grid sentinels), so the min() always picks the valid neighbor for non-corner cells.

Edge cases: (1) All-positive grid — every room heals, so dp[0][0] = 1 (enter with minimum HP 1 everywhere). (2) Single cell — dp[0][0] = max(1, 1 - dungeon[0][0]). (3) Path forced through a large negative room — the dp correctly propagates the high HP requirement backward through all cells leading to that room. Both Python and Java handle all these uniformly through the max(1, ...) and min(below, right) logic.

Dungeon Game (LeetCode 174) and Minimum Path Sum (LeetCode 64) are the canonical contrast for forward vs reverse DP. Minimum Path Sum asks "what is the minimum cost to reach the destination?" — the answer accumulates as you move forward, so forward DP is natural. Dungeon Game asks "what is the minimum starting value such that a running constraint is never violated?" — this depends on what lies ahead, so reverse DP from the destination is required. Recognizing which direction the dependency flows is the key insight separating the two.

Cherry Pickup (LeetCode 741) and Cherry Pickup II (LeetCode 1463) extend 2D grid DP to two simultaneous paths. They require a different DP formulation (both paths move simultaneously, tracked as a single 3D or 4D state), but share the grid traversal and space-optimization patterns. Out of Boundary Paths (LeetCode 576) and Knight Probability (LeetCode 688) add probability to grid DP, using forward-propagation of probability mass rather than backward-propagation of required values.

The broader grid DP family — Unique Paths, Minimum Path Sum, Triangle, Dungeon Game, Cherry Pickup — forms a natural learning progression. Start with simple forward DP on deterministic grids, then tackle reverse DP (Dungeon Game), then multi-agent or probabilistic variants. Each problem in the family reinforces the same skills: identifying DP state, choosing traversal direction, and applying the rolling-array space optimization. Dungeon Game is the essential reverse-DP representative in any DP study plan.