This page uses the site's newer layout, so only the problem statement and the section outline survive in the public payload — open the original for the rest.
Dynamic Programming
Paint House II
hard
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:
-
0 ≤ 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.