Paint House II

DESCRIPTION (inspired by Leetcode.com)

You are a renowned painter who is given a task to paint n houses in a row. This time, you have k colors available. The cost of painting each house with each color is different and given in a 2D array costs:

• costs[i][j] = cost of painting house i with color j

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

Constraints:

• 1 ≤ n ≤ 100
• 1 ≤ k ≤ 20
• costs[i].length == k
• 1 ≤ costs[i][j] ≤ 1000

Follow-up: Can you solve this in O(n × k) time instead of the naive O(n × k²)?

Example 1

Input:

costs = [[4, 2, 8], [7, 1, 5], [3, 9, 6]]

Output:

8

Explanation:

• House 0: Color 0 (cost = 4)
• House 1: Color 1 (cost = 1)
• House 2: Color 0 (cost = 3)
• Total = 4 + 1 + 3 = 8

Example 2

Input:

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

Output:

7

Explanation: Paint house 0 with color 1 (cost = 3), house 1 with color 2 (cost = 4). Total = 7.