Dungeon Game
hardTime: O(m*n)Space: O(m*n)
Recognize the pattern
minimum starting health to reach endhealth ≥ 1 at every cellwork backward
Brute force idea
Try all paths — O(2^(m+n)).
Better approach
DP from bottom-right to top-left. dp[i][j] = max(1, min(right,down) - dungeon[i][j]). O(mn).
Key invariant
Working backward: each cell knows minimum health needed to survive from there to the end. Clamped to ≥ 1.
Watch out for
Working forward — requires tracking both current and minimum health. Backward only needs one value.