Dungeon Game
hardTime: O(m*n)Space: O(m*n)
Signals to notice
minimum starting health to reach endhealth ≥ 1 at every cellwork backward
Brute force first
Try all paths — O(2^(m+n)).
The key insight
DP from bottom-right to top-left. dp[i][j] = max(1, min(right,down) - dungeon[i][j]). O(mn).
What must stay true
Working backward: each cell knows minimum health needed to survive from there to the end. Clamped to ≥ 1.
Easy way to go wrong
Working forward — requires tracking both current and minimum health. Backward only needs one value.