Dungeon Game

Hard

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