Painting Houses Cheaply
n houses stand in a row and must each be painted one of k colours. Painting
house i in colour j costs a given amount, and no two ADJACENT houses may share a
colour. Print the least total cost.
17 2 17
16 16 5 -> 10 colours 2, 3, 2
14 3 19
Choosing the cheapest colour for each house independently is wrong whenever two neighbours agree on their cheapest, which the sample is built to do.
The state must record what the previous house was painted, because that is the only thing constraining this one:
dp[i][j] = cost[i][j] + min over t != j of dp[i-1][t]
The first row is the cost row itself, and the answer is the smallest entry of the last row.
As written this is O(n * k^2), which is fine at the stated bounds. It reduces to
O(n * k) with one observation: the min over t != j is the smallest entry of the
previous row unless j is where that smallest sits, in which case it is the SECOND
smallest. Tracking the best two values of each row therefore removes the inner
scan entirely.
That reduction is worth knowing because it generalises: whenever a transition excludes exactly one predecessor, keeping the best two candidates replaces a scan over all of them.