LeetCode 174: Dungeon Game Solution in Python Explained

Problem Statement

In LeetCode 174, you’re given a 2D integer array dungeon of size m x n. Each cell dungeon[i][j] represents health points:

• Negative values (e.g., -5) reduce HP.
• Positive values (e.g., 3) increase HP.

Starting at the top-left cell (0,0) with some initial HP, you can move only right or down to reach the bottom-right cell (m-1,n-1). Your task is to return the minimum initial HP required so that HP remains ≥ 1 at all times. This differs from BST iteration like LeetCode 173: Binary Search Tree Iterator, focusing on path optimization rather than tree traversal.

Constraints

• m, n ≥ 1
• m * n ≤ 10^5
• -10^4 ≤ dungeon[i][j] ≤ 10^4

Example

Let’s see some cases:

Copy codeInput: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation:
<ul>
<li>Path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)</li>
<li>Min HP = 7: 7→5→2→5→1 (never ≤ 0)</li>
</ul>

Copy codeInput: dungeon = [[0]]
Output: 1
Explanation: Single cell, need 1 HP to stay ≥ 1.

Copy codeInput: dungeon = [[1,-3,3],[0,-2,0],[-3,-3,-3]]
Output: 3
Explanation: Min HP = 3 ensures HP ≥ 1 throughout.

These examples show we’re finding the minimum starting health.

Understanding the Problem

How do you solve LeetCode 174: Dungeon Game in Python? Take dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]. We need the minimum initial HP to reach (2,2) from (0,0), staying alive (HP ≥ 1). Brute-forcing all paths is inefficient, but dynamic programming (DP) can optimize by working backward from the princess (bottom-right) to the knight (top-left), ensuring the minimum HP needed at each step. This isn’t a majority element task like LeetCode 169: Majority Element; it’s about path health optimization. We’ll use: 1. Dynamic Programming Bottom-Up: O(mn) time, O(mn) space—our best solution. 2. Dynamic Programming Top-Down with Memoization: O(mn) time, O(mn) space—an alternative.

Let’s dive into the best solution.

Best Solution: Dynamic Programming Bottom-Up Approach

Explanation

Dynamic Programming Bottom-Up builds a DP table from the bottom-right to top-left:

• dp[i][j] represents the minimum HP needed at (i,j) to reach (m-1,n-1) with HP ≥ 1.
• Base case: At (m-1,n-1), need enough HP to stay alive after applying dungeon[m-1][n-1].
• For each cell, compute dp[i][j] as the minimum HP needed from right or down, adjusted by dungeon[i][j].
• Ensure HP ≥ 1 by taking max(1, min_hp - dungeon[i][j]).

This achieves O(mn) time (fill table), O(mn) space (DP table), and efficiency by avoiding recursion, making it optimal for the problem.

For [[-2,-3,3],[-5,-10,1],[10,30,-5]]:

• Work backward: dp[2][2]=1, dp[2][1]=6, ..., dp[0][0]=7.

Step-by-Step Example

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

Goal: Return 7.

• Setup: m=3, n=3, dp = [[0]*4 for _ in range(4)].
• Step 1: Base case (2,2).
• dungeon[2][2] = -5, need 1 HP after, dp[2][2] = max(1, 1 - (-5)) = 6.
• Step 2: Last row/col.
• (2,1)=30: min(6) - 30 = -24, dp[2][1] = 1.
• (2,0)=10: min(1) - 10 = -9, dp[2][0] = 1.
• (1,2)=1: min(6) - 1 = 5, dp[1][2] = 6.
• Step 3: Fill rest.
• (1,1)=-10: min(6,1) - (-10) = 11, dp[1][1] = 11.
• (1,0)=-5: min(11,1) - (-5) = 6, dp[1][0] = 6.
• (0,2)=3: min(6) - 3 = 3, dp[0][2] = 3.
• (0,1)=-3: min(3,11) - (-3) = 6, dp[0][1] = 6.
• (0,0)=-2: min(6,6) - (-2) = 8, dp[0][0] = 7.
• Finish: Return dp[0][0] = 7.

Example 2: dungeon = [[0]]

Goal: Return 1.

• Step 1: dp[0][0] = max(1, 1 - 0) = 1.
• Finish: Return 1.

How the Code Works (Dynamic Programming Bottom-Up) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef calculateMinimumHP(dungeon: list[list[int]]) -> int:
    # Line 1: Get dimensions
    m, n = len(dungeon), len(dungeon[0])
    # Rows and cols (e.g., 3, 3)

    # Line 2: Initialize DP table
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # Extra row/col for boundaries (e.g., 4x4)
    dp[m][n-1] = dp[m-1][n] = float('inf')
    # Sentinel values (e.g., inf)

    # Line 3: Fill base case
    dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
    # HP needed at princess (e.g., max(1, 1-(-5))=6)

    # Line 4: Fill last row and column
    for i in range(m-2, -1, -1):
        # Bottom-up row (e.g., 1, 0)
        dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
        # Min HP from below (e.g., max(1, 6-1)=6)
    for j in range(n-2, -1, -1):
        # Bottom-up col (e.g., 1, 0)
        dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
        # Min HP from right (e.g., max(1, 6-30)=1)

    # Line 5: Fill rest of table
    for i in range(m-2, -1, -1):
        # Rows bottom-up (e.g., 1, 0)
        for j in range(n-2, -1, -1):
            # Cols right-to-left (e.g., 1, 0)
            min_hp = min(dp[i+1][j], dp[i][j+1])
            # Min HP needed from right or down (e.g., min(11,1)=1)
            dp[i][j] = max(1, min_hp - dungeon[i][j])
            # Ensure HP ≥ 1 (e.g., max(1, 1-(-10))=11)

    # Line 6: Return minimum initial HP
    return dp[0][0]
    # e.g., 7

This detailed breakdown clarifies how bottom-up DP efficiently computes the minimum initial HP.

Alternative: Dynamic Programming Top-Down with Memoization Approach

Explanation

Dynamic Programming Top-Down with Memoization uses recursion with a memo table:

• dp(i,j): Minimum HP needed at (i,j) to reach (m-1,n-1).
• Base case: (m-1,n-1) needs enough HP to stay alive.
• Recurse: Min HP from right or down, adjusted by current cell.
• Memoize results to avoid recomputation.

It’s a practical alternative, O(mn) time (each cell computed once), O(mn) space (memo table), but involves recursion overhead.

For [[-2,-3,3],[-5,-10,1],[10,30,-5]]:

• Recurse from (0,0), memoize, reach 7.

Step-by-Step Example (Alternative)

For [[-2,-3,3],[-5,-10,1],[10,30,-5]]:

• (0,0): Min((0,1),(1,0)) - (-2) = 5+2 = 7.
• (0,1): Min((0,2),(1,1)) - (-3) = 2+3 = 5.
• Continue: Bottom-up fills memo, return 7.

How the Code Works (Top-Down)

Copy codedef calculateMinimumHP_TopDown(dungeon: list[list[int]]) -> int:
    m, n = len(dungeon), len(dungeon[0])
    memo = {{

    def dp(i: int, j: int) -> int:
        if i == m-1 and j == n-1:
            return max(1, 1 - dungeon[i][j])
        if i >= m or j >= n:
            return float('inf')
        if (i, j) in memo:
            return memo[(i, j)]
        min_hp = min(dp(i+1, j), dp(i, j+1))
        memo[(i, j)] = max(1, min_hp - dungeon[i][j])
        return memo[(i, j)]

    return dp(0, 0)

Complexity

• Dynamic Programming Bottom-Up:
• Time: O(m*n) – fill table.
• Space: O(m*n) – DP table.
• Dynamic Programming Top-Down with Memoization:
• Time: O(m*n) – memoized calls.
• Space: O(m*n) – memo table.

Efficiency Notes

Dynamic Programming Bottom-Up is the best solution with O(mn) time and O(mn) space, offering clarity and avoiding recursion overhead—Dynamic Programming Top-Down with Memoization matches complexity but uses recursion, making it flexible but slightly less efficient due to call stack.

Key Insights

• Bottom-Up: Direct table fill.
• Top-Down: Recursive with memo.
• Min HP: Ensures survival.

Additional Example

For dungeon = [[1,-3],[0,2]]:

• Goal: 3.
• Bottom-Up: dp[0][0]=3, ensures HP ≥ 1.

Edge Cases

• Single Cell: [[0]] → 1.
• Negative: [[-200]] → 201.
• Positive: [[100]] → 1.

Both solutions handle these well.

Final Thoughts

LeetCode 174: Dungeon Game in Python is a challenging DP puzzle. The Dynamic Programming Bottom-Up solution excels with its efficiency and straightforwardness, while Dynamic Programming Top-Down with Memoization offers a recursive approach. Want more? Try LeetCode 64: Minimum Path Sum for path DP or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 174 on LeetCode with [[-2,-3,3],[-5,-10,1],[10,30,-5]], aiming for 7—test your skills now!