Dungeon Game

I had this on a Bloomberg fintech onsite and the moment I tried to walk the grid TOP-DOWN with a forwards DP, the interviewer cut me off: "the answer depends on what comes AFTER, not what came before. Try the other direction." Once you flip and walk RIGHT-TO-LEFT, BOTTOM-TO-TOP, the recurrence becomes one line. The catalog covered minimum-path-sum (forwards) but it skipped this reverse-DP variant where the goal cell pins the boundary condition.

Dungeon Game

The demons captured the princess and imprisoned her in the bottom-right corner of an m x n dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight starts at the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health drops to 0 or below, he dies immediately. Some rooms are guarded by demons (so entering these rooms costs the knight health), and other rooms are empty (0) or contain magic orbs that increase the knight's health (positive integers). Each room can be entered exactly once.

In order to reach the princess as quickly as possible, the knight decides to move only RIGHT or DOWN at each step. Return the knight's minimum initial health such that he is able to rescue the princess.

Note that any health point drop to 0 or below means the knight dies, so the health must be strictly positive at every step.

Examples

Example 1:

• Input: dungeon = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]
• Output: 7
• Explanation: With initial health 7, the path RIGHT->RIGHT->DOWN->DOWN works: 7 - 2 = 5; 5 - 3 = 2; 2 + 3 = 5; 5 + 1 = 6; 6 - 5 = 1. With 6, the knight dies before the last room.

Example 2:

• Input: dungeon = [[0]]
• Output: 1
• Explanation: Single empty cell. Knight needs at least 1 HP to be alive.

Example 3:

• Input: dungeon = [[100]]
• Output: 1
• Explanation: A friendly orb does not lower the requirement below 1; the knight must START alive.

Example 4:

• Input: dungeon = [[-200]]
• Output: 201
• Explanation: Need 201 HP to survive the -200 hit and stay above 0.

Constraints

• m == dungeon.length.
• n == dungeon[i].length.
• 1 <= m, n <= 200.
• -1000 <= dungeon[i][j] <= 1000.

Follow-up

Why does forwards DP fail? In minimum-path-sum the cost of a step is path-INDEPENDENT, so we can ignore the future and minimize the running sum. Here, the running health depends on a path-DEPENDENT MIN over the entire trajectory, so a high running health early can be wasted by a deep dip later. Reverse DP works because the bottom-right cell PINS the boundary condition: at the goal, the knight needs max(1, 1 - dungeon[m-1][n-1]) HP. From there, every cell's requirement is determined purely by its two NEXT cells, with no path dependence.