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. Given the following code for finding the cheapest flight within K stops, what is the returned value for the input below? Input: n = 3 flights = [[0,1,100],[1,2,100],[0,2,500]] src = 0 dst = 2 K = 1

def findCheapestPrice(n, flights, src, dst, K):
    INF = float('inf')
    prev = [INF] * n
    prev[src] = 0
    for _ in range(K + 1):
        curr = prev[:]
        for u, v, w in flights:
            if prev[u] != INF:
                curr[v] = min(curr[v], prev[u] + w)
        prev = curr
    return prev[dst] if prev[dst] != INF else -1

print(findCheapestPrice(n, flights, src, dst, K))

easy

A. 500

B. 200

C. -1

D. 100

Solution

1. Step 1: Trace dp arrays for each iteration

   Initially prev = [0, inf, inf]. After first iteration (0 stops), curr updates cost to city 1 as 100 and city 2 as 500. After second iteration (1 stop), curr updates city 2 cost to min(500, 100 + 100) = 200.

2. Step 2: Return final cost for destination

   prev[2] after K+1=2 iterations is 200, which is the cheapest cost with at most 1 stop.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP updates costs correctly over K+1 iterations [OK]

Hint: DP updates cost over K+1 iterations [OK]

Common Mistakes:

• Returning direct edge cost ignoring stops
• Off-by-one in iteration count
• Confusing curr and prev arrays

2. 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

3. Consider the following snippet from the optimal Zuma Game solution. Given board = "WRRBBW" and hand = "RB", what is the return value of findMinStep(board, hand)?

easy

A. 2

B. -1

C. 3

D. 1

Solution

1. Step 1: Trace initial calls with board="WRRBBW" and hand="RB"

   Hand has 1 R and 1 B. The board requires more balls to clear groups of 3, but hand is insufficient to clear all.

2. Step 2: Check if any insertion sequence clears board

   Trying to insert R or B balls to form groups of 3 fails due to insufficient balls; no sequence clears the board fully.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Return -1 indicates no solution with given hand [OK]

Hint: Insufficient hand balls cause no solution -> -1 [OK]

Common Mistakes:

• Assuming partial removals suffice to clear board
• Miscounting balls needed for group removal
• Forgetting to restore hand counts after recursion

4. Suppose the Unique Paths problem is modified so that you can move right, down, or diagonally (down-right) at each step. Which of the following changes correctly adapts the space-optimized DP solution to count all unique paths?

hard

A. Use a 2D DP array where dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]

B. Update dp[j] as dp[j] + dp[j - 1] + dp[j - 2] in the inner loop

C. Keep the 1D dp array and update dp[j] = dp[j] + dp[j - 1] only, ignoring diagonal moves

D. Use recursion without memoization to handle the extra diagonal move

Solution

1. Step 1: Understand diagonal move impact

   Diagonal moves depend on the top-left neighbor dp[i-1][j-1], which cannot be tracked with a single 1D array.

2. Step 2: Choose correct DP structure

   A 2D DP array is needed to access dp[i-1][j-1] directly; update rule: dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1].

3. Step 3: Reject incorrect options

   Update dp[j] as dp[j] + dp[j - 1] + dp[j - 2] in the inner loop incorrectly accesses dp[j-2] in 1D array which doesn't represent diagonal; Keep the 1D dp array and update dp[j] = dp[j] + dp[j - 1] only, ignoring diagonal moves ignores diagonal; Use recursion without memoization to handle the extra diagonal move is inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Diagonal requires 2D DP for correct neighbor access [OK]

Hint: Diagonal moves require 2D DP for top-left neighbor [OK]

Common Mistakes:

• Trying to handle diagonal with 1D DP
• Ignoring diagonal moves in update

5. Suppose the Zuma Game variant allows reusing balls from the hand infinitely many times (unlimited supply). Which modification to the algorithm is necessary to correctly compute the minimal insertions?

hard

A. Add a visited set to memoize only board states without hand counts

B. Keep hand_count but reset counts after each recursion to simulate reuse

C. Use greedy insertion since infinite supply guarantees minimal moves by earliest removal

D. Remove hand_count tracking and treat hand as infinite supply; use interval DP without hand state

Solution

1. Step 1: Understand infinite supply impact

   With unlimited balls, hand counts are irrelevant; only board intervals matter.

2. Step 2: Modify DP state and transitions

   Remove hand_count from state and transitions; interval DP can focus solely on board intervals to find minimal insertions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Infinite supply simplifies state, removing hand count dimension [OK]

Hint: Infinite supply removes hand count dimension [OK]

Common Mistakes:

• Resetting hand counts incorrectly simulates reuse
• Using greedy approach which may not be minimal
• Memoizing without hand counts but missing board state uniqueness