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 convex polygon with n vertices, each vertex having an associated value. The goal is to triangulate the polygon such that the sum of the products of the values of the vertices of each triangle is minimized. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Divide and conquer by splitting the polygon into two halves and solving independently

B. A greedy algorithm that always picks the triangle with the smallest immediate product first

C. A simple depth-first search without memoization that explores all triangulations

D. Dynamic programming over intervals that considers all possible triangulations and chooses the minimal cost

Solution

1. Step 1: Understand problem structure

   The problem requires considering all possible triangulations to find the minimal sum of triangle costs, which depends on intervals of vertices.

2. Step 2: Identify suitable algorithm

   Dynamic programming over intervals (interval DP) systematically explores all sub-polygons and stores minimal costs, ensuring optimality.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Interval DP is the classic approach for polygon triangulation problems [OK]

Hint: Interval DP handles overlapping subproblems optimally [OK]

Common Mistakes:

• Greedy fails due to local minima
• DFS without memoization is exponential
• Divide and conquer ignores polygon connectivity

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

3. Identify the bug in the following code snippet for minimum score triangulation of a polygon:

medium

A. Line missing dp[i][j] = float('inf') before minimization

B. Line initializing dp array with zeros

C. Loop boundaries for k from i+1 to j-1

D. Return statement returning dp[0][n-1]

Solution

1. Step 1: Check dp initialization inside loops

   dp[i][j] must be set to infinity before checking for minimal cost; otherwise, dp[i][j] starts at 0 and may never update correctly.

2. Step 2: Confirm other lines are correct

   dp array initialization, loop boundaries, and return statement are correct and standard.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without dp[i][j] = float('inf'), minimal cost calculation is incorrect [OK]

Hint: Always initialize dp[i][j] before minimization [OK]

Common Mistakes:

• Forgetting dp initialization
• Off-by-one in loops
• Mixing indices i,j,k

4. What is the time and space complexity of the optimal space-optimized bottom-up DP solution for the Unique Paths II problem on an m x n grid with obstacles?

medium

A. Time: O(m*n), Space: O(m*n)

B. Time: O(m+n), Space: O(m+n)

C. Time: O(m*n), Space: O(n)

D. Time: O(2^(m+n)), Space: O(m*n)

Solution

1. Step 1: Analyze time complexity

   The algorithm iterates over each cell once in nested loops: O(m*n).

2. Step 2: Analyze space complexity

   Uses a single 1D dp array of length n, so space is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested loops over m and n, dp array size n [OK]

Hint: Nested loops over m and n, dp array size n [OK]

Common Mistakes:

• Confusing recursion stack space with dp array
• Assuming full 2D dp array used
• Mistaking linear time for exponential

5. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the Unique Paths problem on an m x n grid?

medium

A. O(m^2 * n^2)

B. O(m + n)

C. O(m * n * min(m, n))

D. O(m * n)

Solution

1. Step 1: Identify loops in the code

   The solution uses two nested loops: outer loop runs m-1 times, inner loop runs n-1 times.

2. Step 2: Calculate total operations

   Total operations ≈ (m-1) * (n-1) -> O(m * n). No extra hidden loops or recursion stack.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested loops over m and n -> O(m*n) [OK]

Hint: Nested loops over m and n -> O(m*n) [OK]

Common Mistakes:

• Confusing with recursion exponential time
• Forgetting loops multiply complexity