Dungeon Game — Hard Problem & Solution

A knight starts at the top-left of dungeon and must reach the princess at the bottom-right, moving only right or down.

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Matrix
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A knight starts at the top-left of dungeon and must reach the princess at the bottom-right, moving only right or down. Each room changes the knight's health by dungeon[i][j] (negative rooms hurt, positive rooms heal).

The knight dies the moment health drops to 0 or below. Return the minimum starting health that guarantees arrival.

Example 1

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: Going right, right, down, down needs 7 health to survive.

Example 2

Input: dungeon = [[0]]
Output: 1
Explanation: Health must stay strictly positive.

Example 3

Input: dungeon = [[100]]
Output: 1

Constraints

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

How to solve Dungeon Game

Reverse the direction of the DP. Forwards, maximising health is not enough because a path with more health can still dip below zero earlier. Backwards, the requirement is well defined: the health needed entering a room depends only on the cheaper of the two rooms it leads to.

Approach

Pad the grid with a border of 'infinite requirement', except the two cells adjacent to the exit, which need 1.
Fill from bottom-right to top-left with need = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j].
Clamp to at least 1, since health must stay positive at every step.
The answer is dp[0][0].

Why it works

The quantity 'minimum health on entry' is exactly what composes backwards: to survive room (i, j) and everything after it, you need enough to absorb this room's damage and still meet the next room's requirement. The clamp encodes the death rule — extra healing cannot be banked below 1, because you could die before reaching it.

Complexity

Time — O(m · n)
Space — O(m · n)

Pitfalls

A forward DP maximising health is wrong; the classic counterexample is a big heal placed after a lethal room.
Forgetting the clamp lets a healing room drive the requirement to zero or negative.
The answer is at least 1 even in an all-positive dungeon.

Reference solution

Python

from typing import List

def calculateMinimumHP(dungeon: List[List[int]]) -> int:
    m, n = len(dungeon), len(dungeon[0])
    BIG = 10 ** 9
    dp = [[BIG] * (n + 1) for _ in range(m + 1)]
    dp[m][n - 1] = 1
    dp[m - 1][n] = 1
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
            dp[i][j] = 1 if need <= 0 else need
    return dp[0][0]

JavaScript

var calculateMinimumHP = function(dungeon) {
    var BIG = 1000000000;
    var m = dungeon.length, n = dungeon[0].length;
    var dp = [];
    for (var a = 0; a <= m; a++) {
        var row = [];
        for (var b = 0; b <= n; b++) row.push(BIG);
        dp.push(row);
    }
    dp[m][n - 1] = 1;
    dp[m - 1][n] = 1;
    for (var i = m - 1; i >= 0; i--) {
        for (var j = n - 1; j >= 0; j--) {
            var need = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
            dp[i][j] = need <= 0 ? 1 : need;
        }
    }
    return dp[0][0];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue