Paint House

You are a house painter tasked with painting a row of houses. Each house can be painted with one of three colors: red, blue, or green. The cost of painting each house a certain color varies. Your goal is to paint all houses such that no two adjacent houses have the same color, and the total cost of painting is minimized. This problem is a classic example of dynamic programming, where you make optimal choices at each step to achieve a global optimum.

Problem Description

Given a list of costs, where costs[i][j] is the cost of painting house i with color j (0 for red, 1 for blue, 2 for green), determine the minimum cost to paint all houses such that no two adjacent houses have the same color.

Key Requirements:

• You must paint every house in the row.
• No two adjacent houses can have the same color.

Expected Behavior:

The function should return a single integer representing the minimum total cost to paint all houses according to the given constraints.

Edge Cases:

• A single house: If there's only one house, the minimum cost is simply the minimum cost of painting that single house with any of the three colors.
• Empty input: If there are no houses to paint, the cost should be 0.

Examples

Example 1:

Input: [[17, 2, 17], [16, 16, 5], [14, 3, 19]]
Output: 10
Explanation:
The houses are indexed from 0 to 2.
- House 0 can be painted red (cost 17), blue (cost 2), or green (cost 17).
- House 1 can be painted red (cost 16), blue (cost 16), or green (cost 5).
- House 2 can be painted red (cost 14), blue (cost 3), or green (cost 19).

The minimum cost painting sequence is:
- Paint house 0 blue (cost 2).
- Paint house 1 green (cost 5).
- Paint house 2 blue (cost 3).
Total cost = 2 + 5 + 3 = 10.

Example 2:

Input: [[7, 6, 2]]
Output: 2
Explanation:
There is only one house. The minimum cost is to paint it green (cost 2).

Example 3:

Input: [[1, 5, 3], [2, 9, 4]]
Output: 5
Explanation:
- House 0 red (1), House 1 blue (9) -> Total 10
- House 0 red (1), House 1 green (4) -> Total 5
- House 0 blue (5), House 1 red (2) -> Total 7
- House 0 blue (5), House 1 green (4) -> Total 9
- House 0 green (3), House 1 red (2) -> Total 5
- House 0 green (3), House 1 blue (9) -> Total 12
The minimum cost is 5.

Constraints

• 1 <= costs.length <= 100 (Number of houses)
• costs[i].length == 3 (Three colors available for each house)
• 0 <= costs[i][j] <= 1000 (Cost to paint a house a specific color)
• The input costs will be a list of lists (or equivalent 2D array/matrix).
• The solution should aim for an efficient time complexity, ideally linear with respect to the number of houses.

Notes

• Consider how the choice of color for the current house affects the choices for the next house.
• This problem can be approached using dynamic programming, where you build up the solution by considering the minimum cost to paint up to a certain house with a specific color.
• Think about the state you need to maintain at each step.