Paint House - Video Solutions

Problem Overview: You are given a costs matrix where costs[i][j] is the cost of painting house i with color j. Adjacent houses cannot have the same color. The task is to compute the minimum total cost to paint all houses while respecting this constraint.

Approach 1: Brute Force Recursion (Time: O(3^n), Space: O(n))

Try every possible color choice for each house using recursion. For house i, choose any color different from the previous house and recursively compute the remaining cost. Each step branches into up to three choices, which leads to an exponential search space. The recursion stack can grow to O(n). This approach demonstrates the core constraint clearly but becomes impractical once the number of houses grows.

Approach 2: Top-Down Dynamic Programming with Memoization (Time: O(n), Space: O(n))

The repeated subproblems in the brute force approach make this ideal for dynamic programming. Define a state dp(i, color) representing the minimum cost to paint houses from i onward when house i uses color. For each state, compute the cost plus the minimum of the two allowed colors for the next house. Store results in a memo table to avoid recomputation. Since there are only n * 3 states, the total runtime becomes linear.

Approach 3: Bottom-Up Dynamic Programming (Time: O(n), Space: O(1))

Iterate through the array of houses while keeping track of the minimum cost for each color from the previous house. For house i, update three values: paint red using cost[i][0] + min(prevBlue, prevGreen), paint blue using cost[i][1] + min(prevRed, prevGreen), and paint green using cost[i][2] + min(prevRed, prevBlue). Only the previous row is required, so you can store three running variables instead of a full DP table. This produces the optimal result in linear time and constant extra memory.

Recommended for interviews: The bottom-up dynamic programming solution is the expected answer. Interviewers want to see that you identify overlapping subproblems and convert the exponential recursion into an O(n) DP transition. Explaining the brute force recursion first shows understanding of the constraint, then optimizing it with dynamic programming demonstrates strong problem-solving skills.