Skip to main content

174. Dungeon Game

hard

Find the minimum starting health a knight needs to reach the bottom-right of an m x n dungeon moving right or down. The classic 'fill the table backwards' trick — you can only know minimum start health by working back from the goal.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers). To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step. Return the knight's minimum initial health so that he can rescue the princess.

Constraints

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

Examples

Example 1

Input
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output
7

Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

Example 2

Input
dungeon = [[0]]
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Forward DP fails — the constraint 'health must stay positive at every step' is non-monotonic in the path sum.

Hint 2

Fill backwards: dp[i][j] = minimum health needed when ENTERING (i, j) to survive to the goal.

Hint 3

Recurrence: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). The max(1, ...) keeps health positive.

Hint 4

Base case (one step past the goal in each direction): treat dp[m][n-1] and dp[m-1][n] as 1.

Solution approach

Reveal approach

Bottom-up DP filling from the bottom-right corner backward. dp[i][j] is the minimum health required when entering cell (i, j) to reach the princess alive. Sentinel: dp[m][n-1] = dp[m-1][n] = 1 (the knight needs at least 1 health to step into the goal alive). For each (i, j) from (m-1, n-1) down to (0, 0): need = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]. If need <= 0 (the cell heals so much the knight could enter at 1 hp), set dp[i][j] = 1. Else dp[i][j] = need. Return dp[0][0]. Forward DP fails because optimal sub-path health is not additive — backward DP cleanly separates 'incoming need' from 'cell effect'. Space optimization: O(n) with a single rolling row.

Complexity

Time
O(m * n)
Space
O(n)

Related patterns

  • dynamic-programming
  • grid-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Dungeon Game and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →