Dungeon Game

▶

Steps

setup

Initialize DP Table with Infinity

Create a dp table with dimensions (m+1) x (n+1) filled with infinity to represent uncomputed or unreachable states.

💡 Using infinity helps handle boundaries uniformly and prevents invalid paths from affecting calculations.

Line:

dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]

💡 This initialization sets a clean slate where no cell has a computed health requirement yet.

setup

Set Base Cases for Princess Adjacent Cells

Set dp[m][n-1] and dp[m-1][n] to 1, representing the minimum health needed just beyond the princess cell.

💡 These base cases anchor the DP, indicating the knight needs at least 1 health to survive after rescuing the princess.

Line:

dp[m][n - 1] = 1
dp[m - 1][n] = 1

💡 These cells represent the 'exit' points, ensuring the knight's health never drops below 1 after reaching the princess.

fill_cells

Start Filling dp at Bottom-Right Cell (2,2)

Calculate dp[2][2] by taking the minimum of dp[3][2] and dp[2][3], subtract dungeon[2][2], then max with 1.

💡 This step computes the health needed at the princess cell itself, considering the knight's health after this cell.

Line:

need = min(dp[3][2], dp[2][3]) - dungeon[2][2]
dp[2][2] = max(1, need)

💡 The knight needs at least 6 health entering cell (2,2) to survive the -5 damage and still have 1 health after.

fill_cells

Fill dp at Cell (2,1)

Compute dp[2][1] using dp[3][1] and dp[2][2], subtract dungeon[2][1], then max with 1.

💡 This step shows how health needed propagates leftwards in the bottom row.

Line:

need = min(dp[3][1], dp[2][2]) - dungeon[2][1]
dp[2][1] = max(1, need)

💡 Because dungeon[2][1] is +30, the knight gains health, so only 1 health is needed entering this cell.

fill_cells

Fill dp at Cell (2,0)

Calculate dp[2][0] using dp[3][0] and dp[2][1], subtract dungeon[2][0], then max with 1.

💡 This completes the bottom row, showing how health needed is affected by a positive dungeon value.

Line:

need = min(dp[3][0], dp[2][1]) - dungeon[2][0]
dp[2][0] = max(1, need)

💡 Again, a positive dungeon value reduces the health needed entering this cell to the minimum of 1.

fill_cells

Fill dp at Cell (1,2)

Calculate dp[1][2] using dp[2][2] and dp[1][3], subtract dungeon[1][2], then max with 1.

💡 Moving up one row, this step shows how a positive dungeon value affects health needed.

Line:

need = min(dp[2][2], dp[1][3]) - dungeon[1][2]
dp[1][2] = max(1, need)

💡 The knight needs 5 health entering cell (1,2) to survive the +1 gain and reach the princess.

fill_cells

Fill dp at Cell (1,1)

Calculate dp[1][1] using dp[2][1] and dp[1][2], subtract dungeon[1][1], then max with 1.

💡 This cell has a large negative dungeon value, increasing health needed to survive.

Line:

need = min(dp[2][1], dp[1][2]) - dungeon[1][1]
dp[1][1] = max(1, need)

💡 The knight needs 11 health entering cell (1,1) to survive the -10 damage and continue safely.

fill_cells

Fill dp at Cell (1,0)

Calculate dp[1][0] using dp[2][0] and dp[1][1], subtract dungeon[1][0], then max with 1.

💡 This step shows how a negative dungeon value affects health needed in the middle row.

Line:

need = min(dp[2][0], dp[1][1]) - dungeon[1][0]
dp[1][0] = max(1, need)

💡 The knight needs 6 health entering cell (1,0) to survive the -5 damage and continue.

fill_cells

Fill dp at Cell (0,2)

Calculate dp[0][2] using dp[1][2] and dp[0][3], subtract dungeon[0][2], then max with 1.

💡 Moving to the top row, this step shows how a positive dungeon value affects health needed.

Line:

need = min(dp[1][2], dp[0][3]) - dungeon[0][2]
dp[0][2] = max(1, need)

💡 The knight needs 2 health entering cell (0,2) to survive the +3 gain and continue.

fill_cells

Fill dp at Cell (0,1)

Calculate dp[0][1] using dp[1][1] and dp[0][2], subtract dungeon[0][1], then max with 1.

💡 This cell has a negative dungeon value, increasing health needed to survive.

Line:

need = min(dp[1][1], dp[0][2]) - dungeon[0][1]
dp[0][1] = max(1, need)

💡 The knight needs 5 health entering cell (0,1) to survive the -3 damage and continue.

fill_cells

Fill dp at Cell (0,0)

Calculate dp[0][0] using dp[1][0] and dp[0][1], subtract dungeon[0][0], then max with 1.

💡 This final cell computes the minimum initial health needed to start the dungeon.

Line:

need = min(dp[1][0], dp[0][1]) - dungeon[0][0]
dp[0][0] = max(1, need)

💡 The knight must start with at least 7 health to survive the dungeon and rescue the princess.

from typing import List

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]  # STEP 1
        dp[m][n - 1] = 1  # STEP 2
        dp[m - 1][n] = 1  # STEP 2

        for i in range(m - 1, -1, -1):  # STEP 3-11 outer loop
            for j in range(n - 1, -1, -1):  # STEP 3-11 inner loop
                need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]  # STEP 3-11
                dp[i][j] = max(1, need)  # STEP 3-11

        return dp[0][0]  # STEP 11 final answer

📊

Dungeon Game - Watch the Algorithm Execute, Step by Step

Watching each cell fill reveals how the knight's health requirements propagate backward, clarifying the dynamic programming logic beyond just reading code.

Initializing dp array

i\w	0	1	2	3
i=0	∞	∞	∞	∞
i=1	∞	∞	∞	∞
i=2	∞	∞	∞	∞
i=3	∞	∞	∞	∞

∞ (unfilled)

Initializing dp array

i\w	0	1	2	3
i=0	∞	∞	∞	∞
i=1	∞	∞	∞	∞
i=2	∞	∞	∞	1
i=3	∞	∞	1	∞

dp[m][n-1] = 1

Item 2 - wt:-5 val:0

i\w	0	1	2	3
i=0	∞	∞	∞	∞
i=1	∞	∞	∞	∞
i=2	∞	∞	6	1
i=3	∞	∞	1	∞

Calculating dp[2][2]

Item 2 - wt:30 val:0

i\w	0	1	2	3
i=0	∞	∞	∞	∞
i=1	∞	∞	∞	∞
i=2	∞	1	6	1
i=3	∞	∞	1	∞

Calculating dp[2][1]

Item 2 - wt:10 val:0

i\w	0	1	2	3
i=0	∞	∞	∞	∞
i=1	∞	∞	∞	∞
i=2	1	1	6	1
i=3	∞	∞	1	∞

Calculating dp[2][0]

Item 1 - wt:1 val:0

i\w	0	1	2	3
i=0	∞	∞	∞	∞
i=1	∞	∞	5	∞
i=2	1	1	6	1
i=3	∞	∞	1	∞

Calculating dp[1][2]

Item 1 - wt:-10 val:0

i\w	0	1	2	3
i=0	∞	∞	∞	∞
i=1	∞	11	5	∞
i=2	1	1	6	1
i=3	∞	∞	1	∞

Calculating dp[1][1]

Item 1 - wt:-5 val:0

i\w	0	1	2	3
i=0	∞	∞	∞	∞
i=1	6	11	5	∞
i=2	1	1	6	1
i=3	∞	∞	1	∞

Calculating dp[1][0]

Item 0 - wt:3 val:0

i\w	0	1	2	3
i=0	∞	∞	2	∞
i=1	6	11	5	∞
i=2	1	1	6	1
i=3	∞	∞	1	∞

Calculating dp[0][2]

Item 0 - wt:-3 val:0

i\w	0	1	2	3
i=0	∞	5	2	∞
i=1	6	11	5	∞
i=2	1	1	6	1
i=3	∞	∞	1	∞

Calculating dp[0][1]

Item 0 - wt:-2 val:0

i\w	0	1	2	3
i=0	7	5	2	∞
i=1	6	11	5	∞
i=2	1	1	6	1
i=3	∞	∞	1	∞

Answer cell dp[0][0] = 7

Key Takeaways

✓ The dp table is filled from bottom-right to top-left, reflecting the knight's backward health requirements.

This direction is hard to grasp from code alone but is clear when watching each cell fill in order.

✓ Each dp cell depends only on the right and down neighbors, showing the knight's possible moves and simplifying the recurrence.

Visualizing dependencies helps understand why the table is sized (m+1) x (n+1) with infinity boundaries.

✓ Positive dungeon values can reduce the health needed entering a cell, sometimes down to the minimum of 1.

Seeing this effect in the dp table clarifies how health gains influence the path's feasibility.

Practice

1. You are given a grid of non-negative integers representing costs. Starting from the top-left corner, you want to reach the bottom-right corner by moving only down or right, minimizing the total cost along the path. Which algorithmic approach guarantees finding the minimum total cost efficiently?

easy

A. A greedy algorithm that always moves to the adjacent cell with the smallest cost

B. Dynamic programming that builds up solutions from smaller subproblems using a grid-based state

C. Pure brute force recursion exploring all possible paths without memoization

D. Divide and conquer by splitting the grid into halves and solving independently

Solution

1. Step 1: Understand problem constraints

   The problem requires minimizing path cost with only down or right moves, which naturally forms overlapping subproblems.

2. Step 2: Identify suitable algorithmic pattern

   Dynamic programming efficiently solves overlapping subproblems by storing intermediate results, unlike greedy which can fail on some grids, brute force which is exponential, or divide and conquer which doesn't handle dependencies well.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP uses subproblem solutions to build the answer bottom-up [OK]

Hint: DP handles overlapping subproblems and optimal substructure [OK]

Common Mistakes:

• Assuming greedy always works for grid path problems
• Thinking brute force is efficient enough
• Believing divide and conquer applies without overlapping subproblems

2. What is the time complexity of the bottom-up dynamic programming solution for the Burst Balloons problem with input size n, and why?

medium

A. O(n^3) because for each interval we try all possible last balloons to burst

B. O(n^3) due to three nested loops iterating over intervals and burst positions

C. O(2^n) because of the exponential number of burst orders

D. O(n^2) because we fill a 2D dp table of size n by n

Solution

1. Step 1: Identify loops in bottom-up DP

   There are three nested loops: length of interval (up to n), start index i (up to n), and position k (up to n) inside the interval.

2. Step 2: Calculate complexity

   Each loop runs up to n times, so total time is O(n * n * n) = O(n^3). The dp table is size O(n^2), but filling it requires the third loop over k.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three nested loops over n -> O(n^3) time complexity [OK]

Hint: Three nested loops over intervals and positions cause cubic time [OK]

Common Mistakes:

• Confusing dp table size with time complexity
• Ignoring the innermost loop over k
• Assuming exponential time for DP solution

3. The following code attempts to implement the space-optimized DP solution for Maximal Square. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def maximalSquare(matrix):
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    dp = [0] * (cols + 1)
    max_side = 0
    prev = 0
    for i in range(rows):
        for j in range(1, cols + 1):
            temp = dp[j]
            if matrix[i][j-1] == '1':
                dp[j] = 1 + min(dp[j], dp[j-1], prev)  # Bug here
                max_side = max(max_side, dp[j])
            else:
                dp[j] = 0
            prev = temp
    return max_side * max_side

medium

A. Line with 'dp[j] = 1 + min(dp[j], dp[j-1], dp[j-1])'

B. Line with 'temp = dp[j]'

C. Line with 'prev = temp'

D. Line with 'max_side = max(max_side, dp[j])'

Solution

1. Step 1: Identify the DP recurrence

   The recurrence requires min(dp[j], dp[j-1], prev), but code uses dp[j-1] twice, missing 'prev'.

2. Step 2: Understand impact

   Using dp[j-1] twice ignores the diagonal value 'prev', causing incorrect dp values and max square size.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct recurrence uses three distinct values [OK]

Hint: Check if all three DP states are used in min() [OK]

Common Mistakes:

• Forgetting to use 'prev' in min()
• Overwriting dp before using dependencies
• Incorrect dp initialization

4. What is the time complexity of the bottom-up dynamic programming solution for the Stone Game problem with n piles, and why?

medium

A. O(n^3) because of three nested loops over the piles

B. O(n^2) because the DP table of size nxn is filled once with constant work per cell

C. O(2^n) because all subsets of piles are considered

D. O(n) because only linear passes over the piles are needed

Solution

1. Step 1: Identify loops in bottom-up DP

   There are two nested loops: one for length from 2 to n, and one for start index i, total O(n^2) iterations.

2. Step 2: Constant work per dp[i][j]

   Each dp[i][j] is computed with a constant number of operations (max of two values), so total time is O(n^2).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP table size nxn filled once with O(1) work per cell [OK]

Hint: Two nested loops over intervals -> O(n^2) [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming triple nested loops cause O(n^3)

5. Suppose the Burst Balloons problem is modified so that each balloon can be burst multiple times (reused), and bursting a balloon again yields coins based on the current adjacent balloons. Which of the following changes to the bottom-up DP approach correctly adapts to this variant?

hard

A. Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts

B. Modify the DP to consider only the first burst of each balloon and ignore reuse

C. Use the same interval DP but allow k to be chosen multiple times per interval

D. Use a greedy approach bursting the balloon with the maximum product of neighbors repeatedly

Solution

1. Step 1: Understand reuse impact

   Allowing multiple bursts per balloon means the problem state must track how many times each balloon has been burst, increasing complexity.

2. Step 2: Adapt DP state

   Interval DP assuming each balloon bursts once no longer works. We need a DP or memoization that tracks burst counts per balloon to correctly compute coins.

3. Step 3: Evaluate options

   Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts correctly proposes a stateful DP with counts and memoization. Use the same interval DP but allow k to be chosen multiple times per interval incorrectly reuses interval DP without state changes. Modify the DP to consider only the first burst of each balloon and ignore reuse ignores reuse, and D is greedy and incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking burst counts is necessary for reuse variants [OK]

Hint: Reuse requires tracking burst counts, not just intervals [OK]

Common Mistakes:

• Trying naive interval DP for reuse
• Ignoring state explosion
• Using greedy for complex DP variants