Paint House IV

Paint House IV

What is this problem about?

The Paint House IV problem gives you 2n houses and 3 colors. Each color has costs for houses 1..n and separately for houses n+1..2n (symmetric pairs). Adjacent houses (i and i+1) cannot share the same color. Find the minimum cost to paint all 2n houses. This is a 2-row variant of the standard paint house DP problem.

Why is this asked in interviews?

Chargebee, Amazon, and Bloomberg ask this because the two-row symmetric structure requires carefully linking the left and right halves of the house sequence. DP must handle the pairing constraint between symmetric house positions.

Algorithmic pattern used

DP on paired positions. Process positions 1..n: for position i, house i has color c1 and house (2n-i+1) has color c2. Both c1 and c2 must differ from their respective neighbors, and the pair (c1,c2) must use different colors from each other. Track dp[i][c1][c2] = min cost for first i pairs. Transition: new pair (c1',c2') must have c1' ≠ prev c1 and c2' ≠ prev c2 and c1' ≠ c2'.

Example explanation

n=2, costs for positions (1,4)=(1,5), (2,3)=(2,3). 3 colors. Color constraints. Enumerate valid (c1,c2) pairs (where c1≠c2) for each position. Minimize total cost across all valid sequences.

Common mistakes candidates make

• Not enforcing c1 ≠ c2 for symmetric pairs.
• Not considering that position i's color affects both house i and house 2n-i+1.
• Using linear DP without the paired structure.
• Missing adjacency constraints between consecutive positions.

Interview preparation tip

Paint House variants test DP state design adaptability. When the problem adds structural constraints (pairs, symmetric positions, target neighborhoods), add the appropriate dimension to the DP state. Practice identifying what "additional history" each constraint requires and encoding it as an extra dimension. Paint House I→II→III→IV progressively adds dimensions, building strong DP design intuition.