171. Dungeon Game
A knight enters the top-left room of an m × n dungeon grid; the princess waits in the bottom-right room. He can only move right or down, one room at a time.
Each room dungeon[i][j] holds an integer. Negative rooms hold demons that drain that much health, positive rooms hold healing orbs that restore it, and zero rooms are empty. A room's value is applied the moment the knight steps in — including the first room and the last one. If his health ever drops to 0 or below, he dies on the spot.
Return the smallest positive starting health that lets the knight reach the princess alive along some route.
The trap: the best route is not the one that ends with the most health — it is the one whose worst moment is shallowest. That is what makes a forward scan so slippery, and a backward one so clean.
Example 1:
Input: dungeon = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]
Output: 7
Explanation: Starting with 7 HP and going right, right, down, down: 7 → 5 → 2 → 5 → 6 → 1. Health never touches 0, and no route allows a smaller start.
Example 2:
Input: dungeon = [[0]]
Output: 1
Explanation: The knight starts on the princess's room. It costs nothing, but health must always be at least 1, so he needs 1 HP.
Constraints:
- m == dungeon.length, n == dungeon[i].length
- 1 ≤ m, n ≤ 200
- -1000 ≤ dungeon[i][j] ≤ 1000
Hints:
Greedy route-picking fails, and so does a forward DP on "health lost so far": two routes can tie on total damage yet differ on how deep their worst dip goes. You need to track the requirement, not the running total.
Work backward from the princess. Define need[i][j] = the minimum health the knight must have at the moment he steps into room (i, j) to still make it. At the last room, need = max(1, 1 − dungeon[m−1][n−1]).
Transition: need[i][j] = max(1, min(need[i+1][j], need[i][j+1]) − dungeon[i][j]). The max(1, …) clamp encodes "health can never sit at 0", and it is exactly why the backward direction works. The answer is need[0][0].
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: dungeon = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]
Expected output: 7