Paint House LeetCode 256 — State Machine DP

LeetCode 256 Paint House presents you with n houses arranged in a row and a cost matrix costs where costs[i][0], costs[i][1], and costs[i][2] represent the cost to paint house i red, blue, or green respectively. The constraint is that no two adjacent houses may be painted the same color — house i and house i+1 must differ. Your goal is to find the minimum total cost to paint all n houses under this constraint.

The problem is deceptively simple: at each house you have three color choices, but one is forbidden based on the color chosen for the previous house. This creates a small, fixed set of state transitions — a classic state-machine structure. The optimal cost at house i with color c depends only on the optimal costs at house i-1 for the other two colors, giving us a clean DP recurrence with just three states per step.

Because the number of colors is fixed at 3, we can exploit the constant state count to reduce space from O(n) to O(1) by maintaining only three rolling values. This is the kind of optimization interviewers expect you to identify and implement in a follow-up discussion.

The brute force approach tries every possible coloring of the n houses. Since each house can be painted one of 3 colors (subject to the adjacency constraint), the number of valid colorings is at most 3 × 2^(n-1) — for each house after the first, two of the three colors are still available. For n=100 this is astronomically large, making exhaustive search completely infeasible for any practical input size.

However, the brute force analysis reveals something valuable: the optimal substructure. The minimum cost to paint houses 0 through i with house i colored c does not depend on which specific colors were chosen for houses 0 through i-2 — it only depends on the color chosen for house i-1. This means we have overlapping subproblems and optimal substructure, the two hallmarks of a DP problem.

The state-machine pattern emerges naturally: we have exactly 3 states (the color of the most recently painted house), and we transition between them with a fixed rule (you cannot transition from color c to color c). Each transition adds a known cost from the cost matrix. Recognizing this structure is the key conceptual step before writing any DP code.

Define dp[i][c] as the minimum cost to paint houses 0 through i, with house i painted color c (0=red, 1=blue, 2=green). The recurrence follows directly from the adjacency constraint: to paint house i red, the previous house must be either blue or green, so we take the cheaper of those two options. Similarly for blue and green.

The recurrence is: dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]); dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2]); dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1]). The base case initializes dp[0][c] = costs[0][c] for each color — the first house has no previous house, so its cost is simply the painting cost itself.

After filling the table, the answer is min(dp[n-1][0], dp[n-1][1], dp[n-1][2]) — the minimum over all three possible colors for the last house. The full table is O(n) space, but since each row only depends on the previous row, we can reduce to O(1) space with rolling variables.

Since dp[i] depends only on dp[i-1], we do not need to store the entire n×3 table. Instead, maintain three scalar variables prevRed, prevBlue, prevGreen that hold the minimum costs for the previous house under each color. At each step, compute three new values using only the three previous values, then overwrite the previous variables with the new ones.

The critical implementation detail is to compute all three new values before overwriting any of the previous values. If you update prevRed in place before computing currBlue, then currBlue's computation of min(prevRed, prevGreen) will inadvertently use the already-updated prevRed from this step rather than the original value from the previous house. Using three temporary variables (currRed, currBlue, currGreen) or computing them simultaneously avoids this pitfall.

This rolling-variable technique is one of the most common DP space optimizations and appears in dozens of problems. Paint House is an ideal teaching example because the state count is small (3) and the "use temps before overwrite" rule is clearly necessary and easy to demonstrate.

LeetCode 265 Paint House II generalizes the problem to n houses and k colors. The naive O(nk^2) approach applies the same recurrence: for each house and each color, find the minimum over all other (k-1) colors from the previous row. This becomes O(nk^2) total, which is acceptable for small k but inefficient when k is large.

The key insight for the O(nk) optimization is that when computing the minimum over all colors except c for the previous row, you only need the global minimum and the second minimum. For every color c, if c was not the color achieving the global minimum, then min over all other colors is simply the global minimum. If c was the color achieving the global minimum, then min over all other colors is the second minimum. Thus, you can precompute (min1, min1_color, min2) for the previous row in O(k) and use these to fill all k cells of the current row in O(k), giving O(nk) total.

This min/second-min trick is a recurring optimization in DP problems with a "can't use the same state twice in a row" constraint. Beyond Paint House II, it appears in stock trading problems with multiple states and grid path problems with forbidden same-step choices.

Python O(n) time O(1) space: def minCost(costs): if not costs: return 0; prevR, prevB, prevG = costs[0]; for i in range(1, len(costs)): r, b, g = costs[i]; currR = r + min(prevB, prevG); currB = b + min(prevR, prevG); currG = g + min(prevR, prevB); prevR, prevB, prevG = currR, currB, currG; return min(prevR, prevB, prevG). Destructuring assignment in Python makes the simultaneous update clean and free of temporary variable clutter.

Java O(n) time O(1) space: public int minCost(int[][] costs) { int r = costs[0][0], b = costs[0][1], g = costs[0][2]; for (int i = 1; i < costs.length; i++) { int nr = costs[i][0] + Math.min(b, g); int nb = costs[i][1] + Math.min(r, g); int ng = costs[i][2] + Math.min(r, b); r = nr; b = nb; g = ng; } return Math.min(r, Math.min(b, g)); } In Java, explicitly computing nr, nb, ng before assigning back to r, b, g is required to avoid using updated values mid-iteration.

Both solutions are interview-ready: linear time, constant space, and O(1) extra variables. Edge cases to mention: n=1 (return min of first row directly — the loop does not execute), all same costs (any valid coloring works), and the guarantee from the constraints that costs are non-negative (so the greedy intuition of "always pick the cheapest available color" does not work — DP is required).

House Robber (LeetCode 198) is the simplest state-machine DP: two states (rob or skip), one forbidden transition (cannot rob two consecutive houses). Like Paint House, the state count is constant (2) and space reduces to O(1) with two rolling variables. House Robber II (LeetCode 213) adds a circular constraint, solved by running the linear DP twice on different subsets of houses.

Best Time to Buy and Sell Stock with Cooldown (LeetCode 309) has three states: holding, sold, cooldown. The transitions between states form a directed graph, and the DP tracks the maximum profit in each state after each day. It is a direct generalization of Paint House's state-machine structure to a problem with asymmetric transitions and a profit objective instead of a cost objective.

Decode Ways (LeetCode 91) can be viewed as a state-machine DP where each step either consumes one digit or two digits, with validity rules governing which transitions are allowed. The number of states is small (1 or 2 digits consumed at each step), and the O(1) space optimization via rolling variables applies directly. Together, House Robber, Paint House, Stock with Cooldown, and Decode Ways form the canonical quartet for learning state-machine DP at increasing complexity.