Paint House

DESCRIPTION (inspired by Leetcode.com)

You are a renowned painter who is given a task to paint n houses in a row. You can paint each house with one of three colors: Red, Blue, or Green. The cost of painting each house with each color is different and given in a 2D array costs:

• costs[i][0] = cost of painting house i Red
• costs[i][1] = cost of painting house i Blue
• costs[i][2] = cost of painting house i Green

No two neighboring houses can have the same color. Return the minimum cost to paint all houses.

Constraints:

• 1 ≤ n ≤ 100
• costs[i].length == 3
• 0 ≤ costs[i][j] ≤ 1000

Example 1

Input:

costs = [[8, 4, 15], [10, 7, 3], [6, 9, 12]]

Output:

13

Explanation:

• House 0: Blue (cost = 4)
• House 1: Green (cost = 3)
• House 2: Red (cost = 6)
• Total = 4 + 3 + 6 = 13

Example 2

Input:

costs = [[5, 8, 6], [19, 14, 13], [7, 5, 12], [14, 5, 9]]

Output:

30

Explanation: Red(5) → Green(13) → Red(7) → Blue(5) = 30