Dungeon Game

Hard · dynamic programming

A delivery robot crosses a warehouse floor laid out as a rectangular grid. Each cell has a whole number:

a negative number means a hazard that drains that much energy,
a positive number means a charging pad that restores that much energy,
0 means nothing happens.

The robot starts in the top-left cell and must reach the bottom-right cell. On every move it goes one cell down or one cell right. When it enters a cell, including the first and the last, the cell's number is added to its energy.

The robot's energy must be at least 1 at all times. If it ever drops to 0 or below, including on the very first cell, the robot shuts down.

Return the smallest starting energy (a whole number, at least 1) for which the robot can make the trip without shutting down, if it chooses its route well.

Examples

Example 1

Input: grid = [[-4, 2, -6], [3, -9, 1], [5, 4, -3]]

Output: 5

Start with 5 and walk down, down, right, right: 5 - 4 = 1, 1 + 3 = 4, 4 + 5 = 9, 9 + 4 = 13, 13 - 3 = 10. With 4 the robot is at 0 after the first cell.

Example 2

Input: grid = [[7]]

Output: 1

The cell only adds energy, so a starting energy of 1 is enough.

Example 3

Input: grid = [[-6]]

Output: 7

The robot needs 7 so that 7 - 6 = 1 is still at least 1.

Constraints

1 <= len(grid), len(grid[0]) <= 200
Every row of grid has the same length.
-1000 <= grid[i][j] <= 1000