Problem 29.7 · DP on GridsHard

Dungeon Game

What it teaches: Filling backwards because the requirement depends on what comes later.

Practise it on judges as “Dungeon Game”.

The problem

A knight starts top-left and must reach the princess bottom-right, moving right or down. Each cell adds (positive) or removes (negative) health. Health must stay at least 1 at all times. Return the minimum starting health.

Example 1

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7

Constraints

1 ≤ m, n ≤ 200

Pattern clues in the wording

→ Minimum starting resource so it never drops below a floor

These clues point to Grid DP: Each cell's answer comes from the cells above and to the left; fill the grid row by row.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        return 1;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]	7
2	dungeon = [[0]]	1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Backward DP · O(m × n)

Backward DP

Time O(m × n) Space O(m × n)

need beyond the grid is ∞ except the two cells next to the princess, which are 1. need[r][c] = max(1, min(need[r + 1][c], need[r][c + 1]) − dungeon[r][c]).

Approach 1

import java.util.Arrays;

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        int[][] need = new int[m + 1][n + 1];
        for (int[] row : need) Arrays.fill(row, Integer.MAX_VALUE);
        need[m][n - 1] = 1;
        need[m - 1][n] = 1;
        for (int r = m - 1; r >= 0; r--)
            for (int c = n - 1; c >= 0; c--)
                need[r][c] = Math.max(1, Math.min(need[r + 1][c], need[r][c + 1]) - dungeon[r][c]);
        return need[0][0];
    }
}

Verdict: The direction is the insight.

Before you submit

Edge cases and common mistakes

Test these inputs

Single cell
All positive cells (answer 1)

Mistakes people make

Tracking maximum health forwards (a path with high health now may hit a deep pit later).

Interview

Follow-up questions

Could binary search work?

Command Palette

The problem

Approaches

Backward DP

Edge cases and common mistakes

Follow-up questions