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]]