Dungeon Game

Hard Dynamic Programming 2D DP Original on LeetCode

Dungeon Game is a hard dynamic programming problem solved with the 2d dp pattern. The best approach, optimal (bottom-up dp from the exit, one row), runs in O(m · n) time and O(n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try every path) up.

Problem

A hero starts in the top-left room of an m x n grid called dungeon and must reach the princess in the bottom-right room. Each step goes either right or down.

Every room holds an integer: a negative value is damage that lowers the hero’s health, a positive value is a potion that raises it, and 0 does nothing. The first and last rooms count too. The moment the hero’s health drops to 0 or below, the hero dies.

Return the smallest positive starting health that lets the hero reach the princess alive along some path.

Examples

Example 1

Input
dungeon = [[-3,4,-6],[-2,-5,1],[5,-8,-1]]
Output
5
Why
Go right, down, right, down: health 5 -> 2 -> 6 -> 1 -> 2 -> 1. It never drops to 0, and 4 would not be enough.

Example 2

Input
dungeon = [[1,-4],[-2,3]]
Output
2
Why
Go down then right: health 2 -> 3 -> 1 -> 4. Going right first would need 4.

Example 3

Input
dungeon = [[-7]]
Output
8
Why
The single room takes 7 points, and the hero must still have at least 1 left.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every path)O(2^(m+n))O(m + n)
Memoized recursionO(m · n)O(m · n)
Optimal (bottom-up DP from the exit, one row)O(m · n)O(n)

1Brute force (try every path)

TimeO(2^(m+n))Each call branches twice and the same rooms are reached by many different paths.
SpaceO(m + n)Recursion depth is the path length m + n - 1.

Recursively compute the minimum health needed when entering room (i, j): look at the requirement of the room below and the room to the right, take the smaller one, subtract this room's value, and never let the result fall under 1. Without caching, every path is explored.

  1. need(i, j) at the princess room: max(1, 1 - dungeon[i][j]).
  2. Outside the grid return infinity.
  3. Otherwise: max(1, min(need(i + 1, j), need(i, j + 1)) - dungeon[i][j]).
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        return need(dungeon, 0, 0);
    }

    private int need(int[][] d, int i, int j) {
        int m = d.length, n = d[0].length;
        if (i >= m || j >= n) return Integer.MAX_VALUE;
        if (i == m - 1 && j == n - 1) return Math.max(1, 1 - d[i][j]);
        int next = Math.min(need(d, i + 1, j), need(d, i, j + 1));
        return Math.max(1, next - d[i][j]);
    }
}

2Memoized recursion

TimeO(m · n)m · n states, each done in O(1) after its two neighbours.
SpaceO(m · n)The memo table plus the recursion stack.

The requirement of a room depends only on its position, so store it in an m x n table the first time it is computed. Each room is then solved once.

  1. memo filled with 0 (0 means not computed, since every real answer is at least 1).
  2. Same recurrence as the brute force; return memo[i][j] if set, otherwise compute and store.
class Solution {
    private int[][] memo;

    public int calculateMinimumHP(int[][] dungeon) {
        memo = new int[dungeon.length][dungeon[0].length];
        return need(dungeon, 0, 0);
    }

    private int need(int[][] d, int i, int j) {
        int m = d.length, n = d[0].length;
        if (i >= m || j >= n) return Integer.MAX_VALUE;
        if (memo[i][j] != 0) return memo[i][j];
        int res;
        if (i == m - 1 && j == n - 1) res = Math.max(1, 1 - d[i][j]);
        else res = Math.max(1, Math.min(need(d, i + 1, j), need(d, i, j + 1)) - d[i][j]);
        memo[i][j] = res;
        return res;
    }
}

3Optimal (bottom-up DP from the exit, one row)

TimeO(m · n)Every room is processed once.
SpaceO(n)One array of length n + 1.

Fill the requirements backwards from the bottom-right room. Row i only needs row i + 1, so keep a single array dp of length n + 1: before dp[j] is overwritten it holds the value of the room below, and dp[j + 1] already holds the room to the right. Treat the area outside the grid as infinity, except for a virtual room just below the exit that needs 1, so the exit room uses the same formula as every other room.

  1. dp = n + 1 values, all infinity; dp[n - 1] = 1 (the virtual room under the exit). dp[n] stays infinity.
  2. For i from m - 1 down to 0, for j from n - 1 down to 0: dp[j] = max(1, min(dp[j], dp[j + 1]) - dungeon[i][j]).
  3. Return dp[0].
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[n - 1] = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int next = Math.min(dp[j], dp[j + 1]);
                dp[j] = Math.max(1, next - dungeon[i][j]);
            }
        }
        return dp[0];
    }
}

Edge cases to test

  • A 1 x 1 dungeon (positive, zero or negative)
  • All rooms positive (the answer is 1)
  • A single row or a single column (only one path)
  • A big reward early that cannot pay for a deep drop later on the path
  • The path with the best final total is not the path that needs the least starting health

Hints

Hint 1

Going forward from the start does not work: the best path so far depends on both the current health and the lowest point reached, and those two can disagree.

Hint 2

Think backwards. If you know the minimum health needed when you step into the room to the right and the room below, what do you need when entering the current room?

Hint 3

need(i, j) = max(1, min(need(i+1, j), need(i, j+1)) - dungeon[i][j]). Fill it from the bottom-right corner.

FAQ

What is the best time complexity for Dungeon Game?

Optimal (bottom-up DP from the exit, one row) runs in O(m · n) time and O(n) extra space. Every room is processed once.

Which pattern does Dungeon Game use?

It is a dynamic programming problem that uses the 2d dp pattern. Other problems with the same pattern: Minimum Path Sum, Unique Paths, Unique Paths II.

Is there a brute force solution for Dungeon Game?

Yes. Brute force (try every path) takes O(2^(m+n)) time and O(m + n) space. Recursively compute the minimum health needed when entering room (i, j): look at the requirement of the room below and the room to the right, take the smaller one, subtract this room's value, and never let the result fall under 1.

Which edge cases should I test for Dungeon Game?

A 1 x 1 dungeon (positive, zero or negative); All rooms positive (the answer is 1); A single row or a single column (only one path); A big reward early that cannot pay for a deep drop later on the path; The path with the best final total is not the path that needs the least starting health.