Dungeon Game: Brute Force to Optimal

LeetCode 174, solved three ways — plain recursion, top-down memoization, and a space-optimized bottom-up sweep — with intuition, C++ code, an animated dry run for each approach, and complexity analysis you can explain out loud.

On this page

1. Problem statement
2. Approach 1 — Brute force (plain recursion)
3. Approach 2 — Better (top-down memoization)
4. Approach 3 — Optimal (space-optimized bottom-up)
5. Complexity comparison
6. Interview notes
7. FAQ

Problem Statement

Given an m x n dungeon grid, find the knight's minimum initial health needed to reach the bottom-right room alive, moving only right or down.

Negative cells cost health, positive cells restore it, zero cells do nothing. The knight's health must stay above 0 in every room he enters, including the very first and very last.

Example:

dungeon = [[-2,-3, 3],
           [-5,-10, 1],
           [10, 30,-5]]

Output: 7

A starting health of 7 lets the knight survive the path (0,0) → (0,1) → (0,2) → (1,2) → (2,2): health goes 7 → 5 → 2 → 5 → 6 → 1, never touching zero. We'll trace how each approach arrives at this same answer, 7.

Approach 1 · Brute Force

Plain Recursion Over Every Path

Intuition

The key realization is that this problem is easiest to reason about backward from the princess's room. Define solve(i, j) as the minimum health the knight needs upon entering room (i, j) to survive everything from there onward. Then solve(i, j) depends on whichever of solve(i+1, j) or solve(i, j+1) needs less health — the knight will pick whichever neighbor is cheaper to survive through.

The most direct implementation just recurses on that definition with no bookkeeping. It's correct, but the same cell gets revisited and fully recomputed every time a different path reaches it.

Algorithm

1. Base case: at the bottom-right room, the needed health is max(1, 1 - dungeon[i][j]).
2. On the last row, only solve(i, j+1) exists; on the last column, only solve(i+1, j) exists.
3. Otherwise, take min(solve(i+1, j), solve(i, j+1)) — the cheaper neighbor to survive through.
4. Subtract the current room's value, and clamp the result to at least 1 (health can never be zero or negative while entering a room).
5. The answer is solve(0, 0).

C++ Code

int m, n;
vector<vector<int>>* grid;

int solve(int i, int j) {
    if (i == m - 1 && j == n - 1) {
        return max(1, 1 - (*grid)[i][j]);
    }
    if (i == m - 1) {
        return max(1, solve(i, j + 1) - (*grid)[i][j]);
    }
    if (j == n - 1) {
        return max(1, solve(i + 1, j) - (*grid)[i][j]);
    }
    int need = min(solve(i + 1, j), solve(i, j + 1));
    return max(1, need - (*grid)[i][j]);
}

int calculateMinimumHP(vector<vector<int>>& dungeon) {
    grid = &dungeon;
    m = dungeon.size();
    n = dungeon[0].size();
    return solve(0, 0);
}

Dry Run

Complexity Analysis

Approach 2 · Better

Top-Down Recursion with Memoization

Intuition

The recursion itself was already correct — the only problem was recomputation. Cache each solve(i, j) result the first time it's computed, and return the cached value instantly on every later call to the same cell. This turns the exponential blow-up into work proportional to the number of distinct cells.

Algorithm

1. Keep a memo table memo[i][j], initialized to a sentinel like -1 meaning "not yet computed".
2. Before doing any work in solve(i, j), check the memo — if already computed, return it immediately.
3. Otherwise compute it exactly as in the brute-force recursion.
4. Store the result in memo[i][j] before returning it.

C++ Code

vector<vector<int>> memo;

int solve(int i, int j, vector<vector<int>>& dungeon, int m, int n) {
    if (i == m - 1 && j == n - 1) {
        return max(1, 1 - dungeon[i][j]);
    }
    if (memo[i][j] != -1) return memo[i][j];   // cache hit

    int need = INT_MAX;
    if (i + 1 < m) need = min(need, solve(i + 1, j, dungeon, m, n));
    if (j + 1 < n) need = min(need, solve(i, j + 1, dungeon, m, n));

    return memo[i][j] = max(1, need - dungeon[i][j]);
}

int calculateMinimumHP(vector<vector<int>>& dungeon) {
    int m = dungeon.size(), n = dungeon[0].size();
    memo.assign(m, vector<int>(n, -1));
    return solve(0, 0, dungeon, m, n);
}

Dry Run:

Complexity Analysis

Approach 3 · Optimal

Bottom-Up, One Rolling Row

Intuition

Memoized recursion is already polynomial, but it still pays for a recursion stack and a full m × n table. Since each row of the answer only ever depends on the row directly below it, the grid can be filled iteratively from the bottom-right corner upward and leftward, keeping just one row of results alive at a time — no recursion, no full 2D table.

Algorithm

1. Create a 1D array dp of size n, representing "the row below the one currently being processed".
2. Iterate rows i from m - 1 down to 0, and within each row iterate columns j from n - 1 down to 0.
3. For each cell, look at dp[j] (still holding the row below, i.e. the "down" neighbor) and dp[j+1] (already updated to the current row, i.e. the "right" neighbor).
4. Take the smaller of the two, subtract the current room's value, and clamp to at least 1; overwrite dp[j] in place.
5. After the sweep finishes, dp[0] holds the answer.

C++ Code

int calculateMinimumHP(vector<vector<int>>& dungeon) {
    int m = dungeon.size(), n = dungeon[0].size();
    vector<int> dp(n, INT_MAX);

    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int right = (j + 1 < n) ? dp[j + 1] : INT_MAX;
            int down  = (i + 1 < m) ? dp[j]     : INT_MAX;

            int minHealth;
            if (i == m - 1 && j == n - 1) {
                minHealth = 1 - dungeon[i][j];
            } else {
                minHealth = min(right, down) - dungeon[i][j];
            }
            dp[j] = max(1, minHealth);
        }
    }
    return dp[0];
}

Dry Run

Complexity Analysis

Interview Notes

How to talk through it

• Lead with the key insight before writing any code: this must be solved backward, from the princess to the knight, because "minimum health so far" doesn't compose forward the way "maximum health collected" would — the floor-of-1 constraint depends on the whole remaining path, not just what's already happened.
• Explicitly reject a greedy "always pick the path with the highest total health" approach — it's a common wrong instinct, and calling it out early shows real understanding of why this problem is hard.
• Mention the brute-force recursion briefly to establish the recurrence, then move straight to memoization, and offer the space-optimized bottom-up version as your strongest final answer.

Common follow-ups

• "Can you reduce the space further?" → the 1D rolling array in the optimal approach is already the standard answer; note that going below O(n) isn't generally possible since a full row's worth of information is needed to compute the next row.
• "What if the knight could also move up or left?" → the clean backward DP breaks down because rooms can now depend on each other cyclically; this typically requires a different technique such as binary search on the answer combined with a reachability check (e.g. Bellman-Ford style relaxation or BFS/DFS feasibility).
• "Why clamp to 1 instead of 0?" → the knight dies at health ≤ 0, so the minimum safe value entering any room is exactly 1.

Edge cases to mention

• A 1×1 grid → answer is max(1, 1 - dungeon[0][0]) directly.
• A single row or single column → only one direction of movement is ever possible, so the DP degenerates into a simple linear scan.
• All-positive dungeon → the answer can still be as low as 1, since health only needs to stay positive, not maximized.

Related problems

• Minimum Path Sum
• Unique Paths / Unique Paths II
• Cherry Pickup
• Any "must survive along the way" DP that requires reasoning backward from a fixed endpoint

Frequently Asked Questions

Why can't Dungeon Game be solved with a simple forward DP tracking maximum health?

Because the path that collects the most total health isn't necessarily the one requiring the least starting health — what matters is never dropping to zero at any single room along the way, not the final total, and forward DP can't represent that cleanly.

Which approach should I lead with in an interview?

State the backward recurrence first as your key insight, sketch the recursive version briefly, then write the memoized or bottom-up version as your real solution — the bottom-up, space-optimized version is the strongest one to finish on.

What is the recurrence relation for Dungeon Game?

Working backward from the bottom-right room, each cell's minimum required health is the smaller of its two neighbors' requirements minus the current room's value, floored at 1.

What is the time and space complexity of the optimal solution?

The space-optimized bottom-up sweep runs in O(m · n) time and uses O(n) extra space, since only one row of results needs to stay in memory at a time.

code link:

https://leetcode.com/problems/dungeon-game/