DP — Dungeon Game
↗ LeetCode: Dungeon Game · Hard · pattern chapter →
Knight from top-left to bottom-right; each cell gives/takes HP; HP ≥ 1 always. Find min initial HP.
Constraints — 1 ≤ m, n ≤ 200. Brute enumerate paths + simulate is O(2^(m+n)) — 2^400 ≈ 10¹²⁰ paths at max, impossible past 20×20. Reverse DP is O(mn) = 4·10⁴ ops, ~1 ms; forward-DP attempt burns 5 hour of debugging before you realize you can't know future minimum HP. Example 1 — dungeon=[[-2,-3,3],[-5,-10,1],[10,30,-5]] → 7Example 2 — dungeon=[[0]] → 1Example 3 — dungeon=[[1,-3,3],[0,-2,0],[-3,-3,-3]] → 3
Interview timer00:00
Approach 1 — Forward DP (broken — showing why)
Intuition. Try to fill dp[i][j] = "min HP to reach (i,j) alive". Fails because you might arrive with excess HP that soaks a later damage, so the state must include current HP — that's exponential.
In an interview voice this out: "forward DP would need to track HP as a dimension → O(mn·H) ≈ O(mn·10⁴). Reverse DP eliminates the H dimension because 'HP need' only depends on the future path, not the past."
Approach 2 — Reverse DP from bottom-right (canonical)
Insight. Forward fails: HP need depends on future losses. Instead DP backward: need[i][j] = min HP required to survive starting here.
int calculateMinimumHP(int[][] room) {
int m = room.length, n = room[0].length;
int[][] need = new int[m + 1][n + 1];
for (int[] r : need) Arrays.fill(r, Integer.MAX_VALUE);
need[m][n-1] = need[m-1][n] = 1;
for (int i = m - 1; i >= 0; i--)
for (int j = n - 1; j >= 0; j--) {
int min = Math.min(need[i+1][j], need[i][j+1]);
need[i][j] = Math.max(1, min - room[i][j]);
}
return need[0][0];
}Complexity — Time O(mn); Space O(mn) (compressible to O(n)). Say aloud in an interview: "when forward DP needs future information, reverse the sweep direction. Same trick powers Rod Cutting, Regular Expression Matching."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Forward DP with HP state | O(mn·H) | O(mn·H) | Reference — impractical |
| Reverse DP | O(mn) | O(mn) | Canonical |
When to use which
- "Min initial resource to survive path" → reverse DP.
- "Max resource collectible" → forward DP.