Hints — p76 Dungeon Game

Hint 1. Try forward DP from (0,0) first (“min HP to reach this cell alive”). You’ll discover the recurrence depends on FUTURE cells. This is the “future affects past” diagnostic — switch to reverse DP.

Hint 2. Define dp[i][j] = minimum HP the knight needs at the moment of entering cell (i,j) in order to survive from here to the princess. Goal: dp[0][0]. Fill from bottom-right to top-left.

Hint 3. Recurrence: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). Pick the cheaper successor; back-derive HP needed before applying this cell’s effect.

Hint 4. The max(1, ...) is essential. Even if dungeon[i][j] = +100 would let you enter with negative HP and survive, you can’t be alive with HP ≤ 0. Minimum entering HP is always ≥ 1.

Hint 5. Base case: dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1]). Pad bottom/right boundary with +inf sentinels so the min(dp[i+1][j], dp[i][j+1]) doesn’t need special-casing. Space-optimize to O(n) with right-to-left scan.

If stuck: see solution.py.