Dungeon Game
Hard · Dynamic Programming · Array · Dynamic Programming · Matrix
Problem
A knight enters an m x n dungeon at the top-left room and must reach the princess held in the bottom-right room. He may only move right or down one room at a time.
Each room holds an integer: a negative value is damage that reduces the knight’s health, a positive value is a potion that restores it, and 0 does nothing. The first and last rooms apply their values too. If his health ever drops to 0 or below, he dies.
Return the minimum positive starting health that lets the knight reach the princess alive.
Examples
Input: dungeon = [[-2,1],[-4,-1]] Output: 3
Going right then down, health 3 becomes 1, then 2, then 1, and never reaches 0.
Input: dungeon = [[5]] Output: 1
The single room heals, so the knight only needs the smallest possible health, 1.
Input: dungeon = [[0,-3,0],[-1,0,-5]] Output: 7
The cheapest route goes down first: 7 drops to 6, stays 6, then drops to 1 in the last room.
Constraints
- m == len(dungeon), n == len(dungeon[i])
- 1 <= m, n <= 200
- -1000 <= dungeon[i][j] <= 1000
Approaches
- Baseline: binary search the start, simulate forward — time O(m · n · log(m · n · 1000)), space O(n)
Follow-up
What if potions could not lift his health above a cap? The backward pass still works; a requirement above the cap simply makes the room a dead end (see the use case “Health that cannot exceed a cap”).
Related problems
Start free on Cariara · Coding problems · System design studio
