Remember the colour you just used
When a rule looks back one step, add that step's choice to the table and keep one answer per choice. About 13 minutes.
Painting a row of houses
You are painting a row of houses, each in red, green or blue, and each colour costs a different amount on each house. The rule: two neighbours must never get the same colour. You want the cheapest total.
Picking the cheapest colour for each house on its own fails, because it might match its neighbour. So for each house, ask three questions, one per colour: what is the cheapest total for this house and all before it if this house is that colour?
Each colour borrows from the other two
Suppose the current house is painted red. The house before it can be green or blue, but not red. So its cheapest total is this house's red price plus the cheaper of the other two colours' totals from the house before.
Do that for red, green and blue, and you have a fresh set of three totals. After the last house, the answer is the smallest of the three. Only the previous house's three numbers matter, so three variables are enough.
red = cr + min(green, blue) # not the same colour twice
The first house has no neighbour before it, so each total is just its price: red 17, green 2, blue 17.
House 1 costs red 17, green 2, blue 17. House 2 will be red, and red costs 16 there. What is the cheapest total for both houses?
- A18
- B33
- C16
Show the answer
18. House 1 can't be red, so pick green at 2, then house 2 in red at 16: 2 + 16 = 18.
Paint the houses
A row of houses is to be painted red, green or blue. You are given costs, where costs[i] holds the prices to paint house i red, green and blue. No two neighbouring houses may have the same colour. Return the smallest total cost.
costs = [[17, 2, 17], [16, 16, 5], [14, 3, 19]] → 10
1 ≤ houses ≤ 100 · 1 ≤ price ≤ 1,000