Paint House Problem, in depth: choosing the state, the three-color DP, k colors in O(nk), reconstruction and variants

Why greedy fails

The obvious idea is to paint each house the cheapest color that differs from the previous one. Two houses and two colors are enough to break it. Take cost = [[1, 2], [1, 100]]. Greedy paints house 0 with color 0 for 1, which forces house 1 to color 1 for 100, a total of 101. Painting house 0 with color 1 for 2 and house 1 with color 0 for 1 costs 3.

Greedy fails because a cheap choice now can rule out a much cheaper choice next. Any correct method has to keep the options open: for each house, it must know the best cost of ending in each color, not just the best overall. That is exactly the state DP keeps.

Choosing the state

Try the state dp[i] = the cheapest way to paint houses 0 to i. It cannot be extended, because the cost of house i + 1 depends on which color house i got, and dp[i] has forgotten it. The rule for choosing a state is to include whatever the future transition needs to know about the past. Here that is the last color, so the state becomes:

dp[i][c] = the minimum cost to paint houses 0 to i with house i painted color c.

With that state the transition is local. dp[0][c] = cost[0][c], and for i of 1 or more, dp[i][c] = cost[i][c] + min over c' different from c of dp[i - 1][c']. The answer is the minimum of dp[n - 1][c] over c. Correctness follows from an exchange argument. An optimal painting that ends in color c at house i must use some other color c' at house i - 1, and its prefix must be an optimal painting ending in c'. Otherwise, swapping in a cheaper prefix would lower the total without breaking the adjacency rule.

Viewed as a graph, this is a shortest path through a trellis. There is one column per house and one node per color, and edges join only different colors between neighbouring columns. That view makes the variants later in this article easy to reason about.

The three-color solution

def min_cost_3(cost):
    if not cost:
        return 0
    r, g, b = cost[0]
    for cr, cg, cb in cost[1:]:
        r, g, b = cr + min(g, b), cg + min(r, b), cb + min(r, g)
    return min(r, g, b)

The tuple assignment updates all three values from the old values at once. Writing three separate statements, r = ... then g = ... using the new r, is a classic bug that passes many tests and fails on others. It runs in O(n) time and O(1) memory, and it does not modify the input. Many published solutions overwrite cost in place, which surprises callers who reuse the matrix.

In a fixed-width language, pick the accumulator type from the worst case, not the typical one. With n up to 100,000 houses and costs up to 10^5, a total can reach 10^10, which overflows a 32-bit int. If you use a large sentinel for "impossible" in the k-color version, make sure that sentinel plus a cost cannot overflow either. Half the maximum of a 64-bit integer is a safe choice, and it is clearer to test for it explicitly than to rely on wraparound.

Worked example

Take the standard example cost = [[17, 2, 17], [16, 16, 5], [14, 3, 19]]. Row 0 is copied: (17, 2, 17). For house 1, color 0 costs 16 + min(2, 17) = 18, color 1 costs 16 + min(17, 17) = 33 and color 2 costs 5 + min(17, 2) = 7, giving (18, 33, 7). For house 2, color 0 costs 14 + min(33, 7) = 21, color 1 costs 3 + min(18, 7) = 10 and color 2 costs 19 + min(18, 33) = 37, giving (21, 10, 37). The answer is 10.

Check it by hand. The colors are 1, 2, 1, the adjacent pairs differ, and the costs 2 + 5 + 3 sum to 10. Checking the answer against the actual painting is a habit worth keeping, because it catches transition bugs that a final number alone can hide.

Reconstructing the colors

Interviewers and real applications usually want the colors, not just the cost. Keep the full dp table, which is n by k, and walk backwards: pick the cheapest color at the last house, then at each earlier house pick the cheapest color that differs from the one chosen after it. Ties can be broken either way; both choices give the optimum.

def paint_with_colors(cost):
    n, k = len(cost), len(cost[0])
    dp = [list(cost[0])]
    for i in range(1, n):
        prev = dp[-1]
        dp.append([cost[i][c] + min(prev[d] for d in range(k) if d != c)
                   for c in range(k)])
    colors = [min(range(k), key=lambda c: dp[-1][c])]
    for i in range(n - 2, -1, -1):
        nxt = colors[-1]
        colors.append(min((c for c in range(k) if c != nxt), key=lambda c: dp[i][c]))
    colors.reverse()
    return min(dp[-1]), colors

The backward step is sound because dp[i][c] already contains the best prefix ending in c. The only constraint left to respect is the adjacency rule with the color chosen to the right. On the worked example this returns (10, [1, 2, 1]).

k colors in O(nk): min and second min

With k colors the direct transition takes O(k) time per cell and O(nk^2) overall, which is slow when k is in the hundreds. The trick is that "the minimum of the previous row excluding column c" has only two possible values. It is the row minimum, unless c is the column where that minimum sits, in which case it is the second smallest value. Find both in one pass and every cell becomes O(1).

import math

def min_cost_k(cost):
    if not cost:
        return 0
    prev = list(cost[0])               # seed with row 0, not with zeros
    for row in cost[1:]:
        m1 = m2 = math.inf; i1 = -1
        for j, v in enumerate(prev):
            if v < m1:
                m2, m1, i1 = m1, v, j
            elif v < m2:
                m2 = v
        prev = [row[j] + (m2 if j == i1 else m1) for j in range(len(row))]
    return min(prev)                   # inf means no valid painting (k = 1, n of 2 or more)

Two details matter. Ties are safe: if prev is (3, 3, 5) then m1 = 3 at index 0 and m2 = 3, so column 0 correctly reads 3 from column 1. With a new row of (4, 1, 2) the result is (7, 4, 5). The second detail cost real debugging time while this article was written. A version that starts from prev = [0] * k and loops over every row looks equivalent, and it passes most tests. With one color and one house, though, it returns infinity instead of the cost, because the zero row's second minimum does not exist. Seeding prev with row 0 fixes it, and a brute-force comparison over 3,000 random cases found the bug in seconds.

Variants

• Circular street. If house n - 1 also neighbours house 0, run the DP k times, once with house 0 fixed to each color, and forbid that color at the last house. That costs O(nk^2) with the trick inside each run. Alternatively, carry the first color in the state.
• Paint House III (LeetCode 1473). Some houses are already painted and you must form exactly t neighbourhoods, which are maximal runs of one color. The state grows to dp[i][c][j], meaning house i has color c and j neighbourhoods so far. A same-color step keeps j and a color change adds one. The same min and second-min idea applies per value of j.
• Forbidden or penalised pairs. If some color pairs are banned, or switching colors has a cost, the transition becomes dp[i][c] = cost[i][c] + min over c' of (dp[i - 1][c'] + switch[c'][c]). This is a min-plus matrix-vector product, and the trick no longer applies. If every row is identical, min-plus matrix exponentiation answers very long streets in O(k^3 log n).
• Paint fence. The rule is that no more than two adjacent posts share a color. The state is then "same as previous or different", not the color itself. It is a counting problem with a two-state machine, close to House Robber's.

Failure modes and testing

The single most effective test is a brute-force oracle. Enumerate all k^n colorings for n up to 6 and k up to 4, keep the valid ones, and compare the minimum with every fast version on thousands of random matrices with small costs, so ties are common.

import itertools, random, math

def brute(cost):
    n, k = len(cost), len(cost[0])
    best = math.inf
    for col in itertools.product(range(k), repeat=n):
        if all(col[i] != col[i + 1] for i in range(n - 1)):
            best = min(best, sum(cost[i][col[i]] for i in range(n)))
    return best

for _ in range(3000):
    n, k = random.randint(1, 6), random.randint(1, 4)
    cost = [[random.randint(0, 5) for _ in range(k)] for _ in range(n)]
    assert brute(cost) == min_cost_k(cost), cost

Trade-offs

The three-color loop is the right answer when k = 3: it is short, obviously correct and O(1) in memory. For general k, the O(nk) trick is worth its subtlety once k reaches a few dozen, but keep the O(nk^2) version as a test oracle. Keep the full table only when you need reconstruction, and otherwise roll a single row. When the cost of switching depends on the pair of colors, accept O(nk^2), or reach for min-plus algebra if rows repeat. The same "remember the last decision" pattern runs through the stock trading state machines and the table-filling discipline in Dynamic Programming, in depth.

It also helps to recognise the problem in disguise. Replace houses with time steps, colors with hidden states, paint costs with negative log emission probabilities, and the different-color rule with a transition matrix whose diagonal is forbidden. What you get is the Viterbi algorithm for the most likely state sequence of a hidden Markov model, and the reconstruction pass becomes Viterbi's backtrace. Production schedulers that charge for changeovers between machine setups, and sequence labellers in NLP, run exactly this trellis, usually with the O(nk^2) general transition because their switch costs differ per pair.

What to do next

1. Write min_cost_3 and trace the worked example by hand until you get rows (18, 33, 7) and (21, 10, 37).
2. Add reconstruction and assert that the returned colors are adjacent-distinct and sum to the returned cost.
3. Implement min_cost_k, then deliberately seed it with zeros and watch the brute-force harness catch the k = 1 case.
4. Solve the circular-street variant and check it against a brute force that also forbids the first and last houses from matching.
5. Extend the state with a neighbourhood count and solve Paint House III.
6. Rewrite one solution with a switch-cost matrix and note exactly which optimization stops applying.