Paint House

Problem

There is a row of n houses, and each must be painted one of three colors: red, green, or blue. Painting house i with each color has a given cost, provided as costs[i] = [red_cost, green_cost, blue_cost]. Neighboring houses must not share a color. Return the minimum total cost to paint every house.

• costs has up to a hundred houses, each with a cost between 1 and about 20 for every color.

Examples

• costs = [[8, 4, 15], [9, 12, 3], [6, 5, 18]] → 12. Paint house 0 green (4), house 1 blue (3), house 2 green (5).
• costs = [[5, 9, 1]] → 1. A single house takes its cheapest color.
• costs = [[2, 3, 4], [2, 3, 4]] → 5. Greedy would pick the 2 for both houses, which is illegal; the best legal option is 2 then 3.

Hints

1. Picking the cheapest color for each house independently fails because of the neighbor rule. What single piece of information about the previous house affects the current choice?
2. For each house, compute the best total for each of the three possible colors of that house, using the best totals of the other two colors on the previous house.
3. State machine DP with three states per house: best[i][c] = costs[i][c] + min(best[i-1][c'] for c' != c).