Paint House IV - Solution & Explanation

Problem Overview: You are given painting costs for n houses and three colors. Adjacent houses cannot share the same color, and houses that are symmetric from the start and end of the street must also have different colors. The goal is to minimize the total painting cost while satisfying both constraints.

Approach 1: Brute Force Backtracking (Exponential Time)

Try every possible color assignment for each house while enforcing the constraints during recursion. For each position, iterate through the three colors and skip any that match the previous house or its mirrored counterpart. This generates up to 3^n combinations, making it impractical for large inputs. Time complexity is O(3^n) and space complexity is O(n) from the recursion stack. This approach mainly helps validate the constraints before designing a dynamic programming solution.

Approach 2: Memoized Dynamic Programming (Top-Down)

Convert the brute force recursion into a DP by caching states. A useful state is the pair of houses processed from both ends. Track the color used for the previous pair and recursively compute the minimum cost for the next pair. Each state represents combinations of left and right colors, which is at most 3 × 3. Memoization prevents recomputation and reduces the complexity dramatically. Time complexity becomes roughly O(n × 9 × 9) and space complexity is O(n × 9) for memo storage. This approach demonstrates how dynamic programming eliminates exponential branching.

Approach 3: Bottom-Up Pair DP (Optimal)

Process houses from both ends simultaneously. At step i, consider the pair (i, n-1-i). Try all color combinations (c1, c2) for the pair where c1 != c2 to satisfy the mirror constraint. Also ensure c1 differs from the previous left color and c2 differs from the previous right color to satisfy adjacency. Maintain a DP table of size 3 × 3 representing the last chosen colors for the previous pair. For each new pair, iterate over all valid transitions and update the minimum cost. Because the color space is constant, each step performs a fixed number of operations.

The algorithm runs in O(n) time with O(1) extra space (only a small DP table). The input is handled as an array of costs, while the transitions rely on classic DP state transitions. The key insight is reducing the global mirror constraint into pairwise decisions processed from both ends.

Recommended for interviews: The bottom-up dynamic programming solution. Interviewers expect you to recognize the repeating structure and compress the state to color pairs. Mentioning the brute force first shows you understand the constraints, while the optimized DP demonstrates the ability to convert exponential recursion into a linear-time solution.