Paint House III
There is a row of m houses in a small city. Each house must be painted with one of the n colors labeled from 1 to n, and some houses that were painted last summer should not be painted again.
A neighborhood is a maximal group of continuous houses that are painted with the same color.
Given an array houses, an m x n matrix cost, and an integer target:
houses[i]is the color of housei, or0if the house is not painted yet.cost[i][j]is the cost to paint houseiwith colorj + 1.
Return the minimum cost of painting all the remaining houses so that there are exactly target neighborhoods. If it is not possible, return -1.
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 = 3Output
9Painting the houses as [1,2,2,1,1] creates 3 neighborhoods with total cost 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 = 3Output
11Painting the first and last houses to get [2,2,1,2,2] creates 3 neighborhoods with total cost 10 + 1 = 11.
Constraints
- m == houses.length == cost.length
- n == cost[i].length
- 1 <= m <= 100
- 1 <= n <= 20
- 1 <= target <= m
- 0 <= houses[i] <= n
- 1 <= cost[i][j] <= 10^4