Dungeon Game
Implement calculateMinimumHP
Given a grid where every cell either subtracts from or adds to a running value, and starting at the top-left corner with only right and down moves allowed, find the smallest possible starting value that keeps the running total at 1 or above at every single cell along some path to the bottom-right corner — a total that ever drops to 0 or below along the way makes that path invalid, no matter how it recovers afterward.
Working backward from the bottom-right corner makes this tractable: the minimum value needed to safely enter any cell depends only on the minimum value needed to enter whichever of the two cells after it — one step down, one step right — turns out to be the safer choice, adjusted for this cell's own effect and never allowed to drop below 1. Sweeping backward from the bottom-right corner to the top-left, one row at a time, resolves every cell using requirements already computed for the cells that follow it, and the top-left cell's requirement is the answer.
Example 1:
Input: dungeon = [[-3,5,2],[1,-4,1],[2,-1,3]]
Output: 4
Example 2:
Input: dungeon = [[3,-2],[-4,1]]
Output: 1
Example 3:
Input: dungeon = [[6]]
Output: 1
+ 7 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ dungeon.length, dungeon[0].length ≤ 15 - ●
-1000 ≤ dungeon[i][j] ≤ 1000
dungeon =
[[-3,5,2], [1,-4,1], [2,-1,3]]