Given a dungeon grid containing positive and negative health effects, return the minimum initial health required to move from the top-left cell to the bottom-right cell while keeping health strictly above zero at all times. Pattern focus: Dungeon / cherry pickup. Work backward from the destination to compute the required health at each cell.
dungeon contains positive and negative integers
minimum initial health
Example 1:
Input:
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output:
7
Explanation:
The knight needs 7 health to survive the dungeon.
Example 2:
Input:
dungeon = [[0]]
Output:
1
Explanation:
A zero-valued single cell still requires at least 1 health.
Example 3:
Input:
dungeon = [[1,-3,3],[-2,-2,-2],[2,-5,-3]]
Output:
5
Explanation:
The minimum initial health is 5.