A terrace of houses is being repainted with three tints: sand, sage and slate. costs[i] is a list of three integers, the price of painting house i in each tint. Neighbouring houses must not share a tint. Return the cheapest way to paint every house.
Examples
Input: costs = [[17, 2, 17], [16, 16, 5], [14, 3, 19]]
Output: 10
Explanation: sage (2), slate (5), sage (3).
Input: costs = [[7, 6, 2]]
Output: 2
Constraints
0 <= len(costs) <= 10**5, each entry has exactly 3 prices0 <= costs[i][j] <= 10**4- Target complexity: O(n) time.
Goals
- Keep one best-cost value per colour for the previous house
- Combine 'different from the neighbour' with a running minimum