Leetcode 174. Dungeon Game

Hadjshell1/20/26About 2 min

Brute-force

Let’s start with the brute-force approach. Assume m = dungeon.length and n = dungeon[0].length. If we enumerate all possible paths from the top-left to the bottom-right cell, at each step we have two choices: move right or move down. Each path has a length of m + n − 1. For each path, we can track the minimum health encountered along the way to determine the minimum initial health required to survive that path. The time complexity is $O(2^{m + n})$ . Given the constraints 1 <= m, n <= 200, this brute-force approach is computationally infeasible and will result in a TLE.

DP

To decrease the exponential complexity, we can consider to use dynamic programming. The hardest part for this question is to properly define memo. If you are not familiar with DP, please look at my website, there is a detailed explanation.

Wrong Approach

A natural first attempt is to define memo[i][j] as the minimum initial health required to reach cell[i, j] from the start. The base case would be memo[0][0].

However, this state definition does not lead to a correct solution. When determining the minimum health required for the current cell, we also need to know how much health remains when the hero reaches that cell. Knowing only the minimum required health of the left and upper cells is insufficient, because different paths may reach the same cell with different remaining health values.

In other words, the remaining health depends on the exact path taken and the cumulative effect of demons and magic orbs along that path. Since this information is not captured by memo[i][j], we cannot formulate a correct state transition using this definition.

Correct Approach

To correctly solve the problem, we need to think in reverse. Define memo[i][j] as the minimum health required upon entering cell(i, j) such that the hero can reach the bottom-right cell with strictly positive health. The base case is memo[m - 1][n - 1].

For any cell (i, j), the hero can move either right or down. To minimize the required health at the current cell, we choose the path that requires less health among these two options. After accounting for the health change caused by dungeon[i][j], the remaining health must still be at least 1.

Therefore, the state transition equation is: dp[i][j] = Math.max(Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j], 1).

Complexity

Time complexity: $O(mn)$ , m * n states, each $O(1)$ .
Space complexity: $O(mn)$ , memo: $O(mn)$ + m * n function stacks, each $O(1)$

Code

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        // memo[i][j]: minimum health required, starting from (i, j), leaving the bottom right with positive health
        Integer[][] memo = new Integer[m][n];

        return dp(dungeon, 0, 0, memo);
        // for (int i = 0; i < m; i++)
        //     for (int j = 0; j < n; j++)
        //         System.out.printf("(%d, %d): %d\n", i, j, memo[i][j]);
    }

    private int dp(int[][] dungeon, int i, int j, Integer[][] memo) {
        int m = dungeon.length, n = dungeon[0].length;

        if (i == m - 1 && j ==  n - 1) {
            memo[i][j] = dungeon[i][j] < 0 ? -dungeon[i][j] + 1 : 1;
            return memo[i][j];
        }

        if (memo[i][j] != null)
            return memo[i][j];

        int minHealth = Integer.MAX_VALUE, health = 0;
        // memo[i][j] + dungeon[i + 1][j] or dungeon[i][j + 1] >= memo[i + 1][j] or memo[i][j + 1]
        // down
        if (i + 1 < m) {
            health = Math.max(dp(dungeon, i + 1, j, memo) - dungeon[i][j], 1);
            minHealth = Math.min(minHealth, health);
        }
        // right
        if (j + 1 < n) {
            health = Math.max(dp(dungeon, i, j + 1, memo) - dungeon[i][j], 1);
            minHealth = Math.min(minHealth, health);
        }
        memo[i][j] = minHealth;

        return memo[i][j];
    }
}