There is a row of n houses and k colours. costs[i][c] is the cost of painting house i with colour c. No two neighbouring houses may have the same colour. Return the minimum total cost.
- Return
0 for an empty row - The obvious solution scans all other colours for each colour, O(n · k²); aim for O(n · k)
- Hint for the speed-up: the best previous total excluding your own colour is either the smallest total, or the second smallest when you are the colour that owns the smallest
- Assume
k ≥ 2 whenever there is more than one house