0364HardArrayDynamic ProgrammingMatrix

Minimum Launch Charge

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def calculate_minimum_h_p(dungeon: list[list[int]]) -> int:

Java

public int calculateMinimumHP(int[][] dungeon)

The intended approach

Time O(m * n)Space O(n) for the two rows

Work backwards from the finish and store, for every cell, the charge the drone must already hold as it arrives there. A cell only needs enough to satisfy the cheaper of its right and down neighbours once its own value has been applied, and never less than 1, which gives need = max(1, cheaper neighbour - cell). Two rows of length n + 1 are enough because each row only ever reads the row below it and the entry to its right, and a sentinel past the finish supplies the closing requirement of 1.

Pythonentry point: calculate_minimum_h_p

def calculate_minimum_h_p(dungeon):
    # Sweep the grid from the exit backwards, keeping two rows of length n + 1.
    # Time O(m * n), space O(n).
    m, n = len(dungeon), len(dungeon[0])
    big = float("inf")
    below = [big] * (n + 1)
    below[n - 1] = 1
    for i in range(m - 1, -1, -1):
        row = [big] * (n + 1)
        for j in range(n - 1, -1, -1):
            onward = below[j] if below[j] < row[j + 1] else row[j + 1]
            need = onward - dungeon[i][j]
            row[j] = 1 if need < 1 else need
        below = row
    return below[0]

The obvious version

Enumerate every route as a choice of which of the m + n - 2 moves go down, track the running total along it, and take 1 minus the lowest running total (floored at 1) as that route's requirement; the answer is the smallest requirement over all routes.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

from itertools import combinations


def bf_calculate_minimum_h_p(dungeon):
    m, n = len(dungeon), len(dungeon[0])
    steps = m + n - 2
    best = None
    for downs in combinations(range(steps), m - 1):
        downset = set(downs)
        i = j = 0
        running = dungeon[0][0]
        worst = running
        for step in range(steps):
            if step in downset:
                i += 1
            else:
                j += 1
            running += dungeon[i][j]
            if running < worst:
                worst = running
        need = 1 - worst
        if need < 1:
            need = 1
        if best is None or need < best:
            best = need
    return best

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in