Paint House Colors

Minimize the total painting cost with no two adjacent houses sharing a color.

dynamic-programming optimization arrays

You are given a list of houses to paint, each with a cost for painting it in one of three colors: Red, Green, and Blue. The costs are provided as a list of lists `costs`, where `costs[i] = [r, g, b]` gives the cost of painting house `i` red, green, or blue respectively.

Write a function `paint(costs)` that returns the minimum total cost to paint all houses such that no two adjacent houses have the same color.

- If there are no houses, return `0`.
- Each house has exactly three costs.
- The function must handle lists of length 0 to 10^5.

Example:
```python
paint([[1,2,3],[1,2,3]]) == 3
# Options: house0 red (1) + house1 green (2) = 3, or house0 red + house1 blue (3) = 4, etc.
```

Constraints

0 <= len(costs) <= 10^5
len(costs[i]) == 3
0 <= costs[i][j] <= 10^4
Time complexity O(n), space O(1).

Example

>>> paint([])
0
>>> paint([[1,2,3],[1,2,3]])
3
>>> paint([[5,10,20],[10,20,30],[20,30,40]])
45

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of the minimum cost for each house assuming it is painted a specific color.

Use the recurrence: for each house, the cost of choosing a color is its own cost plus the minimum of the previous house's other two colors.

Track only the previous house's three costs to achieve O(1) extra space.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.