Paint Houses Cheaply
Problem
A row of houses must each be painted in one of three colours, and painting a given house a given colour has its own price. Neighbouring houses may not share a colour. Return the cheapest total price for painting the whole row.
Examples
Input: costs = [[17, 2, 17],
[16, 16, 5],
[14, 3, 19]]
Output: 10
Why: paint the houses in the second, third and second colour for 2 + 5 + 3Input: costs = [[7, 6, 2]]
Output: 2
Why: a single house simply takes its cheapest colourInput: costs = []
Output: 0
Why: edge case, an empty row costs nothingHints
0 / 3
Choosing the cheapest colour for each house independently can fail, because a cheap choice may force an expensive one next door. The decision has to account for what comes after it.
Walk the row once and carry three running answers, one per colour: the cheapest way to paint everything up to here given that this house ended in that colour.
Each new house takes its own price for a colour and adds the cheaper of the two running answers for the other two colours. Compute all three new values from the three old ones at once, then move on, and take the smallest of the final three.
Solution
The only thing the rest of the row cares about is the colour of the house just painted, so three running totals, one per colour, capture the whole history. Each house rebuilds those three from the previous three by adding its own price to the cheaper of the two conflicting options. Computing all three simultaneously matters, because using a freshly updated value would let a house borrow from itself. Time is O(n) and space is O(1), since only three numbers are kept.
def cheapest_painting(costs):
first = second = third = 0 # cheapest total ending in each of the colours
for a, b, c in costs:
# each colour pays its own price plus the better of the other two histories
first, second, third = (a + min(second, third),
b + min(first, third),
c + min(first, second))
return min(first, second, third)
print(cheapest_painting([[17, 2, 17], [16, 16, 5], [14, 3, 19]])) # -> 10
print(cheapest_painting([[7, 6, 2]])) # -> 2
print(cheapest_painting([])) # -> 0Stuck on the idea rather than the code? What Is Dynamic Programming? covers it.