222. Dungeon Game
Hard•
Start in the top-left cell of dungeon and reach the bottom-right by moving only right or down. Entering a cell adds its value to your health: negative values cause damage, positive values heal, and zero changes nothing. This applies to both endpoints.
Health must remain at least 1 after entering every cell. Return the smallest positive initial health that allows some complete route. A later healing cell cannot rescue you if you already reached zero health. Do not modify dungeon.
Example 1:
Input: dungeon = [[-3,4,5],[-2,-10,1],[1,2,-6]]
Output: 4
Explanation: The highlighted route goes right, right, down, down through values -3, 4, 5, 1, and -6. Starting at 4 leaves health 1, 5, 10, 11, and 5. Any starting health below 4 fails in the first room, so 4 is minimal even though the route ends with health 5.
Example 2:
Input: dungeon = [[-5,100]]
Output: 6
Explanation: The first room removes 5 health, so initial health must be at least 6. The later gain of 100 cannot revive someone who already reached zero.
Example 3:
Input: dungeon = [[5,-10],[1,-1]]
Output: 1
Explanation: Starting at 1 and moving down, then right changes health to 6, 7, and 6. The alternative right-first route hits -10 too early and fails with that starting health.
Constraints
- 1 <= dungeon.length, dungeon[row].length <= 200
- -1000 <= dungeon[row][col] <= 1000
Accepted5/5|Acceptance Rate100.0%