Dungeon Game
Hard
Topics
A knight starts at the top-left cell of grid and must reach the bottom-right cell, moving only right or down. Each cell adds its value to the knight's health (negative values are demons, positive are potions). The knight dies if health drops to 0 or below at any point. Return the minimum initial health needed to survive the journey.
Example 1
Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] Output: 7
Example 2
Input: dungeon = [[0]] Output: 1
Constraints
- 1 <= rows, cols <= 200
- -1000 <= grid[i][j] <= 1000
Run ⌘' · Submit ⌘⏎
SensAI