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. Some houses are already painted — houses[i] is the color of house i (0 means unpainted).
A neighborhood is a maximal group of consecutive houses with the same color. You want exactly target neighborhoods.
Return the minimum cost to paint all houses to achieve exactly target neighborhoods. Return -1 if it is not possible.
Colors are 1-indexed (1 to n). Cost to paint house i with color j is cost[i][j-1].
Examples
Input: [[0,0,0,0,0],[[1,10],[10,1],[10,1],[1,10],[5,1]],5,2,3]
Output: 9
Input: [[0,2,1,2,0],[[1,10],[10,1],[10,1],[1,10],[5,1]],5,2,3]
Output: 11
Hints
**First Hint**: Start by considering the problem as a dynamic programming (DP) problem where `dp[i][j][k]` represents the minimum cost to paint the first `i` houses, ending with color `j`, and having exactly `k` neighborhoods.
**Second Hint**: For each house `i`, if it's already painted (`houses[i] != 0`), you can only use that color. If it's unpainted, iterate over all possible colors `j` (1 to `n`) and calculate the cost of painting it with color `j`. Update the DP state accordingly, ensuring that the number of neighborhoods is tracked correctly.
**Third Hint**: To handle the neighborhoods correctly, when transitioning from house `i-1` to house `i`, check if the color of house `i` is the same as house `i-1`. If they are the same, the number of neighborhoods remains unchanged. If they are different, increment the neighborhood count. Ensure that the neighborhood count does not exceed `target` at any point.
Related Problems
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. Some houses are already painted — `houses[i]` is the color of house `i` (0 means unpainted).