Paint Zones Into Exactly K Neighborhoods
A row of zones must be painted; some are already painted and cannot change. A 'neighborhood' is a maximal run of same-colored adjacent zones. Paint the rest at minimum cost so the row forms exactly target neighborhoods.
Problem
There is a row of m houses; houses[i] is the color of house i (0 = unpainted). Painting house i with color j costs cost[i][j-1]. A neighborhood is a maximal group of adjacent houses with the same color. Return the minimum total cost to paint all unpainted houses so that there are exactly target neighborhoods, or -1 if impossible.
Input
Arrays houses (length m, values 0..n), cost (m x n), integers m, n, target.
Output
An integer: minimum painting cost, or -1.
Constraints
- 1 <= m <= 100, 1 <= n <= 20, 1 <= target <= m
- 0 <= houses[i] <= n (0 means unpainted)
- 1 <= cost[i][j] <= 10^4
Examples
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
Paint [1,2,2,1,1] → neighborhoods {1},{2,2},{1,1} = 3, cost 9.
Example 2
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
Pre-painted houses already form 4 neighborhoods; cannot reduce to 3.