Paint House

Paint House

What is this problem about?

The Paint House problem gives you n houses in a row and 3 colors. Each house has a cost to paint with each color. No two adjacent houses can have the same color. Find the minimum total painting cost. This is the foundational house-painting DP problem that all subsequent variants build upon. The array and dynamic programming interview pattern is directly demonstrated.

Why is this asked in interviews?

Uber, Citadel, Microsoft, LinkedIn, and Google ask this as the gateway DP problem for sequence coloring. It validates understanding of state-transition DP where current choice depends on the previous choice's constraint (different color). It's often a warm-up before harder paint house variants.

Algorithmic pattern used

Linear DP with 3 states. dp[i][c] = minimum cost to paint houses 0..i with house i colored c (0=red, 1=blue, 2=green). Transition: dp[i][c] = costs[i][c] + min(dp[i-1][c'] for c' != c). Initialize dp[0][c] = costs[0][c]. Answer = min(dp[n-1]).

Example explanation

costs=[[17,2,17],[16,16,5],[14,3,19]]. dp[0]=[17,2,17]. dp[1][0]=costs[1][0]+min(dp[0][1],dp[0][2])=16+min(2,17)=18. dp[1][1]=costs[1][1]+min(dp[0][0],dp[0][2])=16+min(17,17)=33. dp[1][2]=costs[1][2]+min(dp[0][0],dp[0][1])=5+min(17,2)=7. dp[2][0]=14+min(33,7)=21. dp[2][1]=3+min(18,7)=10. dp[2][2]=19+min(18,33)=37. Answer = min(21,10,37) = 10.

Common mistakes candidates make

• Using the same color for dp[i] as dp[i-1] (must exclude current color from min).
• Not initializing base case for the first house.
• Using O(n) extra space when O(1) (just track prev row) suffices.
• Off-by-one in row indices.

Interview preparation tip

Paint House is the template for all "color n items with k colors, adjacent differ" DP problems. Memorize the transition: dp[i][c] = cost[i][c] + min(dp[i-1][c'] for c' ≠ c). Space optimization: only keep the previous row's DP values. After mastering Paint House I, the progression to II (k colors) and III (k colors with target groups) follows naturally.