#1473
Paint House III
expert · 1160 · lc hard +32 · verified · 61.2% accepted · 2,131 likes · top 61%
Description
A row of m houses must each be assigned one of n colors (numbered 1 to n). Houses pre-painted from last season (non-zero in houses[i]) cannot be repainted. A neighborhood is a maximal consecutive run of identically colored houses.
Given the current coloring houses, painting cost matrix cost (where cost[i][j] is the price to paint house i with color j+1), and a desired neighborhood count target, return the minimum total painting cost that yields exactly target neighborhoods. Return -1 if it is impossible.
Example 1:
Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.
Example 2:
Input: houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 11
Explanation: Some houses are already painted, Paint the houses of this way [2,2,1,2,2]
This array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}].
Cost of paint the first and last house (10 + 1) = 11.
Example 3:
Input: houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
Output: -1
Explanation: Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.
Code
1
2
3