Show problems as
Classic problem #174HardArrayDynamic ProgrammingMatrix

Dungeon Game

Real-world version: Minimum Launch Charge
Tracked in this browser only
Read Dungeon Game on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A survey drone crosses a rectangular block of airspace laid out as the m x n grid dungeon. It is released over the top-left cell and has to finish over the bottom-right cell, and from any cell it may only move one cell right or one cell down.

Each cell holds a whole number that is applied to the drone's charge the moment the drone arrives over that cell: a positive cell is a thermal that tops the battery up, a negative cell is a headwind that drains it. The release cell and the finishing cell are applied like every other cell.

The drone falls out of the sky the instant its charge reaches 0, so along the whole route the charge has to stay at 1 or more once each cell has been applied.

Return the smallest charge the drone can be released with and still finish over the bottom-right cell. That charge is a whole number of 1 or more.

Examples

Example 1

Input
dungeon = [[-3,2],[1,-4]]
Output
6

Released with 6 the drone reads 3 over the release cell, 5 after the 2, and 1 after the -4, so it never drops below 1 and it finishes.

Example 2

Input
dungeon = [[5,-1,2]]
Output
1

Released with 1 the drone reads 6, then 5, then 7, staying at 1 or more the whole way across the single row.

Example 3

Input
dungeon = [[-6]]
Output
7

The only cell is both the release cell and the finish, and 7 - 6 = 1.

Example 4

Input
dungeon = [[-2,1],[1,-3],[2,-1]]
Output
3

Released with 3 the drone reads 1 over the release cell, and taking down, down, right it reads 2, then 4, then 3, so it never drops below 1.

Constraints

  • m == dungeon.length
  • n == dungeon[i].length
  • 1 <= m, n <= 200
  • -1000 <= dungeon[i][j] <= 1000

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def calculate_minimum_h_p(dungeon: list[list[int]]) -> int:
Java
public int calculateMinimumHP(int[][] dungeon)

More on the same topics