Paint House II
Hard · Dynamic Programming · Array · Dynamic Programming
Problem
There are n houses in a row and k colors. Painting house i with color j costs costs[i][j], given as an n x k matrix.
No two adjacent houses may have the same color. Return the minimum total cost to paint every house.
Can you do it in O(n * k) time?
Examples
Input: costs = [[4,2,7,1],[1,6,3,1],[5,8,2,9]] Output: 4
Colors 3, 0, 2 cost 1 + 1 + 2 = 4.
Input: costs = [[2,9],[3,1]] Output: 3
Color 0 then color 1: 2 + 1 = 3.
Input: costs = [[1,3,8],[1,4,8]] Output: 4
Both houses are cheapest in color 0. Giving it to the second house (3 + 1 = 4) beats giving it to the first (1 + 4 = 5).
Constraints
- costs.length == n
- costs[i].length == k
- 1 <= n <= 100
- 2 <= k <= 20
- 1 <= costs[i][j] <= 20
Approaches
- Check every previous color — time O(n * k^2), space O(k)
Follow-up
The "best and second best" trick works whenever a row must exclude exactly one entry of the previous row. The use cases close the row into a ring (fix the first color) and replace the ban with a fee for changing colors.
Related problems
Start free on Cariara · Coding problems · System design studio
