Paint House (K Colors)

▶

Steps

setup

Initialize dp with costs of first house

We start by setting dp to the costs of painting the first house with each color. This forms the base case for our DP.

💡 Initializing dp with the first house costs sets the foundation for accumulating minimal costs for subsequent houses.

Line:

dp = costs[0][:]

💡 The dp array now holds the minimal cost to paint house 0 with each color, which is just the direct cost since no previous houses exist.

fill_row

Start processing house 1

We begin processing the second house (index 1). A new dp array, new_dp, is initialized to store minimal costs for house 1.

💡 Creating a new dp array for the current house allows us to compute costs based on previous results without overwriting them prematurely.

Line:

new_dp = [0]*k

💡 new_dp will hold minimal costs for house 1 with each color, computed from dp of house 0.

fill_cells

Compute minimal cost for house 1, color 0

For house 1 and color 0, find the minimal cost from previous house excluding color 0, then add current cost.

💡 Excluding the same color from previous house ensures no two adjacent houses share the same color.

Line:

min_prev = min(dp[x] for x in range(k) if x != 0)
new_dp[0] = costs[1][0] + min_prev

💡 Minimal previous cost excluding color 0 is min(5,3) = 3; adding current cost 2 gives 5.

fill_cells

Compute minimal cost for house 1, color 1

For house 1 and color 1, find minimal previous cost excluding color 1, then add current cost.

💡 We continue to enforce the no-adjacent-same-color constraint for each color choice.

Line:

min_prev = min(dp[x] for x in range(k) if x != 1)
new_dp[1] = costs[1][1] + min_prev

💡 Minimal previous cost excluding color 1 is min(1,3) = 1; adding current cost 9 gives 10.

fill_cells

Compute minimal cost for house 1, color 2

For house 1 and color 2, find minimal previous cost excluding color 2, then add current cost.

💡 Each color's cost is computed independently to find the minimal total cost for the current house.

Line:

min_prev = min(dp[x] for x in range(k) if x != 2)
new_dp[2] = costs[1][2] + min_prev

💡 Minimal previous cost excluding color 2 is min(1,5) = 1; adding current cost 4 gives 5.

fill_row

Update dp to new_dp after house 1

We replace dp with new_dp, finalizing minimal costs for house 1.

💡 Updating dp allows the next iteration to build upon the latest minimal costs.

Line:

dp = new_dp

💡 dp now holds minimal costs for painting houses 0 and 1 with each color choice for house 1.

fill_row

Start processing house 2

We begin processing the third house (index 2). Initialize new_dp for house 2 costs.

💡 A fresh new_dp array is needed to compute minimal costs for the current house based on dp from house 1.

Line:

new_dp = [0]*k

💡 new_dp will hold minimal costs for house 2 with each color.

fill_cells

Compute minimal cost for house 2, color 0

For house 2 and color 0, find minimal previous cost excluding color 0, then add current cost.

💡 Excluding the same color from previous house ensures no two adjacent houses share the same color.

Line:

min_prev = min(dp[x] for x in range(k) if x != 0)
new_dp[0] = costs[2][0] + min_prev

💡 Minimal previous cost excluding color 0 is min(10,5) = 5; adding current cost 15 gives 20.

fill_cells

Compute minimal cost for house 2, color 1

For house 2 and color 1, find minimal previous cost excluding color 1, then add current cost.

💡 We continue to compute minimal costs for each color choice at the current house.

Line:

min_prev = min(dp[x] for x in range(k) if x != 1)
new_dp[1] = costs[2][1] + min_prev

💡 Minimal previous cost excluding color 1 is min(5,5) = 5; adding current cost 7 gives 12.

fill_cells

Compute minimal cost for house 2, color 2

For house 2 and color 2, find minimal previous cost excluding color 2, then add current cost.

💡 Calculating all color options allows us to find the overall minimal cost for the current house.

Line:

min_prev = min(dp[x] for x in range(k) if x != 2)
new_dp[2] = costs[2][2] + min_prev

💡 Minimal previous cost excluding color 2 is min(5,10) = 5; adding current cost 6 gives 11.

fill_row

Update dp to new_dp after house 2

We update dp to new_dp, finalizing minimal costs for all houses.

💡 This update completes the DP computation, allowing us to find the minimal total cost.

Line:

dp = new_dp

💡 dp now holds minimal total costs for painting all houses with each color choice for the last house.

traverse

Find minimal cost in dp after last house

We find the minimal value in dp, which represents the minimal total painting cost for all houses.

💡 The minimal value in dp after processing all houses is the answer to the problem.

Line:

return min(dp)

💡 Minimal cost is min(20,12,11) = 11, but this is not the minimal cost path; we need to re-examine the path for correctness.

prune

Re-examine minimal cost path and correct minimal cost is 8

By carefully selecting colors: house 0 color 0 (cost 1), house 1 color 2 (cost 4), house 2 color 1 (cost 7), total cost is 8, which is minimal and respects constraints.

💡 The DP table shows cumulative costs, but the minimal cost path must be traced to confirm the minimal total cost.

💡 The minimal cost 8 is consistent with the problem constraints and is the correct minimal total painting cost.

def minCost(costs):
    n = len(costs)  # STEP 1
    if n == 0:
        return 0
    k = len(costs[0])
    dp = costs[0][:]  # STEP 1

    for i in range(1, n):  # STEP 2, 6, 7, 11
        new_dp = [0]*k  # STEP 2, 7
        for c in range(k):  # STEP 3,4,5,8,9,10
            min_prev = min(dp[x] for x in range(k) if x != c)  # STEP 3,4,5,8,9,10
            new_dp[c] = costs[i][c] + min_prev  # STEP 3,4,5,8,9,10
        dp = new_dp  # STEP 6,11

    return min(dp)  # STEP 12

📊

Paint House (K Colors) - Watch the Algorithm Execute, Step by Step

Watching each update to the dp array reveals how the algorithm efficiently excludes invalid color choices and accumulates minimal costs.

Item 0 - wt:0 val:0

i\w	0	1	2
i=0	1	5	3
i=1	?	?	?
i=2	?	?	?

cost=1

Item 1 - wt:0 val:0

i\w	0	1	2
i=0	1	5	3
i=1	0	0	0
i=2	?	?	?

computing costs

Item 1 - wt:0 val:2

i\w	0	1	2
i=0	1	5	3
i=1	5	0	0
i=2	?	?	?

prev cost=5

Item 1 - wt:1 val:9

i\w	0	1	2
i=0	1	5	3
i=1	5	10	0
i=2	?	?	?

prev cost=1

Item 1 - wt:2 val:4

i\w	0	1	2
i=0	1	5	3
i=1	5	10	5
i=2	?	?	?

prev cost=1

Item 1 - wt:0 val:0

i\w	0	1	2
i=0	1	5	3
i=1	5	10	5
i=2	?	?	?

cost=5

Item 2 - wt:0 val:0

i\w	0	1	2
i=0	1	5	3
i=1	5	10	5
i=2	0	0	0

computing costs

Item 2 - wt:0 val:15

i\w	0	1	2
i=0	1	5	3
i=1	5	10	5
i=2	20	0	0

prev cost=10

Item 2 - wt:1 val:7

i\w	0	1	2
i=0	1	5	3
i=1	5	10	5
i=2	20	12	0

prev cost=5

Item 2 - wt:2 val:6

i\w	0	1	2
i=0	1	5	3
i=1	5	10	5
i=2	20	12	11

prev cost=5

Item 2 - wt:0 val:0

i\w	0	1	2
i=0	1	5	3
i=1	5	10	5
i=2	20	12	11

cost=20

Item 2 - wt:2 val:6

i\w	0	1	2
i=0	1	5	3
i=1	5	10	5
i=2	20	12	11

min cost=11

Item 2 - wt:1 val:7

i\w	0	1	2
i=0	1	5	3
i=1	5	10	5
i=2	20	12	11

cost=1

Key Takeaways

✓ The DP array accumulates minimal costs house by house, excluding the same color for adjacent houses.

This insight is hard to see from code alone because the exclusion logic is embedded in a nested min operation.

✓ Each cell depends only on the previous row's minimal costs excluding the same color, showing a clear dependency pattern.

Visualizing this dependency clarifies why the algorithm avoids invalid color adjacencies.

✓ The minimal cost is found by scanning the last dp array, representing all houses painted with valid color choices.

Seeing the final dp array and the minimal value highlights how the answer emerges from accumulated computations.

Practice

1. You are given a 2D grid representing a dungeon where each cell contains an integer indicating health points gained or lost upon entering. You start at the top-left and must reach the bottom-right cell, moving only right or down. Your health must never drop below 1 at any point. Which algorithmic approach guarantees finding the minimum initial health required to survive the dungeon?

easy

A. Dynamic programming starting from the bottom-right cell and moving backward to the top-left

B. Greedy algorithm that always chooses the next cell with the highest health gain

C. Pure brute force recursion exploring all paths from start to end

D. Dijkstra's shortest path algorithm treating health as distance

Solution

1. Step 1: Understand problem constraints

   The problem requires minimum initial health ensuring health never drops below 1, which depends on future cells, so greedy or shortest path won't work.

2. Step 2: Identify correct DP direction

   Starting from the bottom-right cell and moving backward allows computing minimum health needed at each cell based on future states.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backward DP correctly accounts for future health requirements [OK]

Hint: Backward DP from goal ensures future states known [OK]

Common Mistakes:

• Assuming greedy or forward DP works
• Using shortest path ignoring health constraints

2. Given the following code for the Dungeon Game problem, what is the value of dp[0][0] returned by calculateMinimumHP when called with dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]?

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)]
        dp[m][n - 1] = 1
        dp[m - 1][n] = 1

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
                dp[i][j] = max(1, need)

        return dp[0][0]

easy

A. 7

B. 5

C. 3

D. 1

Solution

1. Step 1: Initialize dp boundaries

   dp[3][2] and dp[2][3] set to 1, others infinity.

2. Step 2: Compute dp bottom-up

   Calculate dp values from bottom-right to top-left considering dungeon values and ensuring health ≥1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Known example output is 7 for this input [OK]

Hint: Trace dp from bottom-right to top-left [OK]

Common Mistakes:

• Off-by-one errors in dp indices
• Forgetting max(1, need)

3. Consider the following bottom-up DP code for the Triangle minimum path sum problem. Given the input triangle = [[2],[3,4],[6,5,7]], what is the value of dp after the first iteration of the outer loop (i = 1)?

easy

A. [8, 9, 7]

B. [9, 10, 7]

C. [11, 10, 7]

D. [7, 9, 7]

Solution

1. Step 1: Initialize dp with last row

   dp = [6, 5, 7]

2. Step 2: Compute dp for i=1 (row [3,4])

   For j=0: dp[0] = 3 + min(6,5) = 3 + 5 = 8 For j=1: dp[1] = 4 + min(5,7) = 4 + 5 = 9 Updated dp = [8, 9, 7]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp updated correctly for row 1 [OK]

Hint: dp[j] updated using min of dp[j], dp[j+1] from row below [OK]

Common Mistakes:

• Off-by-one error in indexing dp
• Not copying last row correctly
• Mixing up dp[j] and dp[j+1] in min calculation

4. The following code attempts to compute the minimum falling path sum using bottom-up DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def minFallingPathSum(matrix):
    n = len(matrix)
    dp = matrix[0][:]

    for i in range(1, n):
        for j in range(n):
            best = dp[j]
            if j > 0:
                best = min(best, dp[j-1])
            if j < n - 1:
                best = min(best, dp[j+1])
            dp[j] = matrix[i][j] + best

    return min(dp)

medium

A. Line 7: Updating dp[j] inside the inner loop without backup

B. Line 9: Checking if j > 0 before accessing dp[j-1]

C. Line 3: dp initialization with matrix[0][:]

D. Line 12: Returning min(dp) after the loops

Solution

1. Step 1: Understand dp update logic

   dp array holds minimum sums for previous row. Updating dp[j] in place overwrites values needed for neighbors in the same iteration.

2. Step 2: Identify the bug

   Updating dp[j] inside the inner loop without using a separate array causes premature overwriting, leading to incorrect neighbor comparisons.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using a separate new_dp array fixes the bug [OK]

Hint: Don't overwrite dp while still reading from it in same iteration [OK]

Common Mistakes:

• Updating dp in place without backup
• Ignoring boundary checks

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