Dungeon Game — Reverse 2D DP from Goal to Start

Problem Statement#

A demon has captured the princess and imprisoned her in the bottom-right corner of a 2D grid dungeon. The knight starts at the top-left corner and must reach the bottom-right corner moving only right or down. Each cell contains an integer:

• A negative integer reduces the knight's hit points (HP) by that amount.
• A positive integer increases his HP.
• A zero leaves it unchanged.

The knight dies the moment his HP drops to 0 or below. Return the minimum initial HP that guarantees the knight reaches the princess alive.

Example:

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

Returns 7. The optimal path is right, right, down, down with HP trajectory 7 -> 5 -> 2 -> 5 -> 6 -> 1. With initial HP 6, the knight would hit 0 after entering the second cell.

Constraints: 1 is less than or equal to m, n is less than or equal to 200 with cell values in [-1000, 1000]. The grid is small enough for O(m * n) DP.

Why This Problem Matters#

Dungeon Game is one of the most asked grid-DP problems at Amazon, Google, Microsoft, Bloomberg, and most quant interviews. What makes it special is that the obvious forward DP does not work. You cannot greedily pick the maximum HP arriving at each cell because that decision interacts with future cells: a path that arrives with high HP might still die later, while a path that arrives with lower HP but a higher floor along the way survives.

The fix is to flip the DP direction and reason from the goal backward. That insight — that DP direction is a design decision, not a default — is exactly what FAANG interviewers want to evaluate.

The Core Insight (Recurrence)#

Define dp[i][j] as the minimum HP needed when entering cell (i, j) so that the knight survives from (i, j) to the bottom-right corner.

Working backward from the destination, the recurrence at cell (i, j) is:

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

The intuition: pick the easier of the two outgoing moves (down or right), subtract the current cell's effect (a positive cell reduces the requirement, a negative cell increases it), and clamp at 1 because the knight must stay strictly above 0 HP.

Base case at the goal: dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1]). The bottom-right needs enough HP to survive its own value.

Sentinel rows and columns: pad with infinity beyond the bottom-right. Setting dp[m][n-1] = dp[m-1][n] = 1 (and the rest infinity) makes the recurrence uniform.

Building the DP Solution (Recursion to Memo to Tabulation)#

Top-down: solve(i, j) returns the min HP needed entering (i, j). Recurse into (i+1, j) and (i, j+1), take the smaller, subtract the current value, clamp at 1. Memoize on (i, j) for O(m * n) time.

Tabulation: allocate dp[m + 1][n + 1] filled with infinity. Set the two cells just past the goal to 1, then loop i from m-1 down to 0 and j from n-1 down to 0. This is the cleanest interview answer.

Space optimization: each row only depends on the next row plus its own right neighbor. Keep one row of length n + 1 and update right to left within the row, top to bottom external loop. This brings memory from O(m * n) to O(n).

Why forward DP fails: dp[i][j] = max(1, prev_required - dungeon[i][j]) would need to know the future minimum. Even if we tracked (min_hp, current_hp) pairs the optimization is multidimensional and Pareto-frontier-based, drastically harder than the backward formulation.

Visual Dry Run (DP Table Trace)#

Trace the canonical example:

dungeon =
 -2 -3  3
 -5 -10 1
 10  30 -5

Initialize dp[3][2] = dp[2][3] = 1 and surrounding sentinels at infinity.

Row 2 (i = 2):

• (2, 2): dp[2][2] = max(1, min(1, 1) - (-5)) = 6.
• (2, 1): dp[2][1] = max(1, min(6, inf) - 30) = max(1, -24) = 1.
• (2, 0): dp[2][0] = max(1, min(1, inf) - 10) = max(1, -9) = 1.

Row 1 (i = 1):

• (1, 2): dp[1][2] = max(1, min(6, 1) - 1) = max(1, 0) = 1.
• (1, 1): dp[1][1] = max(1, min(1, 6) - (-10)) = 11.
• (1, 0): dp[1][0] = max(1, min(11, 1) - (-5)) = 6.

Row 0 (i = 0):

• (0, 2): dp[0][2] = max(1, min(1, inf) - 3) = max(1, -2) = 1.
• (0, 1): dp[0][1] = max(1, min(11, 1) - (-3)) = 4.
• (0, 0): dp[0][0] = max(1, min(4, 6) - (-2)) = 6. Wait — let me recheck: min(dp[1][0], dp[0][1]) = min(6, 4) = 4. Then 4 - (-2) = 6. So dp[0][0] = 6.

But the expected answer is 7. Let me recheck the inner cells.

Recompute (1, 1): min(dp[2][1], dp[1][2]) = min(1, 1) = 1. Then 1 - (-10) = 11. Correct. Recompute (1, 0): min(dp[2][0], dp[1][1]) = min(1, 11) = 1. Then 1 - (-5) = 6. Correct. Recompute (0, 1): min(dp[1][1], dp[0][2]) = min(11, 1) = 1. Then 1 - (-3) = 4. Correct. Recompute (0, 0): min(dp[1][0], dp[0][1]) = min(6, 4) = 4. Then 4 - (-2) = 6. So dp[0][0] = 6?

LeetCode says the answer is 7. The issue is the optimal path on this dungeon visits right -> right -> down -> down (HP starts at 7, goes 5, 2, 5, 6, 1), but our DP found a path needing only 6. Let me trace down -> right -> down -> right: HP start, start+(-5)+(-2), then.... Path (0,0) -> (1,0) -> (1,1) -> (2,1) -> (2,2): values -2, -5, -10, 30, -5. Cumulative: start - 2 - 5 - 10 + 30 - 5. The minimum prefix sum is at step 3 = start - 17. We need start - 17 to be at least 1, so start at least 18. That is much worse.

Path (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2): -2 - 5 + 10 + 30 - 5. Cumulative: -2, -7, 3, 33, 28. Minimum is -7. Need start - 7 at least 1, so start at least 8.

Path (0,0) -> (0,1) -> (1,1) -> ...: -2 - 3 - 10. Already at -15 after three moves. Worse.

Path (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2): -2 - 3 + 3 + 1 - 5. Cumulative: -2, -5, -2, -1, -6. Minimum is -6. Need start at least 7.

So the true minimum is 7 (the path right-right-down-down). My DP trace gave 6, meaning I made an arithmetic error somewhere. Let me recheck (2, 1) = 1: min(dp[3][1], dp[2][2]) = min(inf, 6) = 6. Then 6 - 30 = -24. max(1, -24) = 1. OK that is correct.

(1, 1): min(dp[2][1], dp[1][2]) = min(1, 1) = 1. 1 - (-10) = 11. Correct.

(0, 1): min(dp[1][1], dp[0][2]) = min(11, 1) = 1. 1 - (-3) = 4. Correct.

(0, 0): min(dp[1][0], dp[0][1]) = min(6, 4) = 4. 4 - (-2) = 6.

There is a subtle issue with my hand trace — I should double check (1, 2): min(dp[2][2], dp[1][3]) = min(6, inf) = 6. 6 - 1 = 5. max(1, 5) = 5. NOT 1.

Let me redo from (1, 2): dp[1][2] = max(1, min(dp[2][2], dp[1][3]) - dungeon[1][2]) = max(1, min(6, inf) - 1) = max(1, 5) = 5.

Then (0, 1): min(dp[1][1], dp[0][2]) = min(11, dp[0][2]). Recompute dp[0][2] = max(1, min(dp[1][2], dp[0][3]) - dungeon[0][2]) = max(1, min(5, inf) - 3) = max(1, 2) = 2. So min(11, 2) = 2, and dp[0][1] = max(1, 2 - (-3)) = 5.

(0, 0): min(dp[1][0], dp[0][1]) = min(6, 5) = 5. dp[0][0] = max(1, 5 - (-2)) = 7.

That matches the expected answer of 7. The lesson: every cell must be carefully recomputed; do not skim cells.

Optimized Solution — Space-Optimized Python and JavaScript#

Python — 1D Rolling Row#

from typing import List
import math
 
class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [math.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)
            dp[n] = math.inf
        return dp[0]

JavaScript — 1D Rolling Row#

var calculateMinimumHP = function (dungeon) {
  const m = dungeon.length;
  const n = dungeon[0].length;
  const INF = Number.POSITIVE_INFINITY;
  const dp = new Array(n + 1).fill(INF);
  dp[n - 1] = 1;
  for (let i = m - 1; i >= 0; i -= 1) {
    for (let j = n - 1; j >= 0; j -= 1) {
      const need = Math.min(dp[j], dp[j + 1]) - dungeon[i][j];
      dp[j] = Math.max(1, need);
    }
    dp[n] = INF;
  }
  return dp[0];
};

Complexity Analysis#

• Time: O(m * n). Each cell is computed in O(1) and we visit every cell.
• Space: O(m * n) for the textbook 2D table, O(n) for the rolling-row optimization.
• The recursion + memoization version has the same time but adds O(m + n) stack depth — usually fine for m, n at most 200.

Common Mistakes#

• Forward DP attempts. The greedy maximum-HP-on-arrival fails because future cells can still kill the knight; you would need a Pareto frontier of (incoming HP, max future HP) pairs.
• Forgetting the max(1, ...) clamp. A positive cell can make the required HP zero or negative; the knight still needs at least 1 HP entering the cell.
• Mis-initialized sentinels. Setting dp[m][n-1] and dp[m-1][n] to 0 instead of 1 makes the goal cell think the knight can survive with 0 HP afterwards.
• Iterating in the wrong direction. The DP must fill bottom-right to top-left; reverse it and you read uninitialized cells.
• Treating the values as multiplicative. They are additive HP changes; do not confuse with product paths.

Interview Tips#

• Spend the first minute explaining why forward DP fails. That demonstrates DP-direction maturity and earns the most credit.
• Draw the recurrence: a cell needs the minimum of its two outgoing requirements, minus its own value, clamped at 1.
• Code the 2D tabulation first (cleanest), then mention the 1D rolling-row optimization to show production thinking.
• Discuss whether path reconstruction is needed; if yes, store the chosen direction in a parallel table.

Follow-up Questions#

• Print the optimal path, not just the minimum HP.
• Allow moves in all four directions. The DP becomes a shortest-path problem on a graph; you would use Dijkstra-style relaxation.
• Maximize the HP collected along the way instead of minimizing the starting HP. Different objective, different recurrence.
• Allow "potions" that can be used to skip damage on a single cell. State expands to (i, j, potions_left).

Key Takeaways#

• Dungeon Game is the textbook example of why DP direction matters: forward DP is provably suboptimal, backward DP is clean.
• The recurrence dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]) captures both the "follow the easier exit" intuition and the "stay alive" clamp.
• Sentinel rows and columns simplify the recurrence by removing edge cases.
• Time complexity is O(m * n); memory is O(n) with rolling rows, the senior-level optimization.
• The clamp at 1 is the single most common bug — negative or zero requirements still mean "1 HP minimum."
• Mastering this problem cements the skill of designing DP traversals from the goal backward when forward greedy choices interact badly with the future.