Dungeon Game

Dungeon Game

What is this problem about?

The Dungeon Game coding problem is a grid-based challenge where a knight must rescue a princess. The knight starts at the top-left corner of a dungeon (a 2D grid) and needs to reach the princess at the bottom-right. Each cell contains an integer: positive values increase the knight's health, while negative values decrease it. If the knight's health ever drops to 0 or below, he dies immediately. The goal is to find the minimum initial health the knight needs to survive the journey.

Why is this asked in interviews?

Companies like Uber and Amazon ask the Dungeon Game interview question to test a candidate's mastery of dynamic programming interview pattern, especially when the standard "top-down" approach is insufficient. In this problem, calculating health from the start doesn't work because future cells influence current requirements. It requires "reverse DP," teaching candidates to think about problems from the destination back to the source.

Algorithmic pattern used

This problem is solved using Dynamic Programming (Bottom-Up from Destination).

1. Define dp[i][j] as the minimum health needed before entering cell (i, j).
2. To survive, the health after entering (i, j) must be at least 1.
3. If moving right or down, the knight picks the path that requires less health.
4. The transition: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]).
5. The final answer is dp[0][0].

Example explanation

Suppose we have a 2x2 grid: [-2, -3] [-5, 10] Princess is at (1, 1) with value 10.

1. Health needed after (1, 1) is 1. Health needed before (1, 1): max(1, 1 - 10) = 1.
2. For (0, 1) (value -3): needs to reach (1, 1) (needs 1). max(1, 1 - (-3)) = 4.
3. For (1, 0) (value -5): needs to reach (1, 1) (needs 1). max(1, 1 - (-5)) = 6.
4. For (0, 0) (value -2): can go to (0, 1) (needs 4) or (1, 0) (needs 6). Pick (0, 1). Health before (0, 0): max(1, 4 - (-2)) = 6. Result: 6.

Common mistakes candidates make

• Iterating from Top-Left: Trying to find the "maximum health" path from the start, which doesn't guarantee the minimum initial health needed.
• Health dropping to 0: Forgetting that the knight must have at least 1 health at every single step, including the destination.
• Incorrect Boundary initialization: Not correctly setting the health requirements for the dummy cells outside the grid (should be infinity, except for the cells adjacent to the princess).

Interview preparation tip

Whenever a pathfinding problem depends on future states to determine the current best choice, try solving it backwards from the goal. This is a very common trick in competitive programming and advanced technical interviews.