Repaint Houses Into Exactly Target Neighborhoods
A street of houses is being painted. Some are already painted (and cannot change); the rest are blank. Painting a blank house in colour c costs cost[i][c]. A 'neighborhood' is a maximal run of same-coloured adjacent houses. Repaint the blanks so the street forms exactly target neighborhoods at minimum cost.
Problem
Given m houses with colours houses[i] (0 = unpainted, else 1..n), an m x n cost matrix where cost[i][c-1] is the price to paint house i colour c, and an integer target, return the minimum cost to paint every unpainted house so the street has exactly target neighborhoods. Return -1 if impossible. Already-painted houses must keep their colour.
Input
Arrays houses (length m), cost (m x n), and integers m, n, target.
Output
The minimum total painting cost, or -1.
Constraints
- 1 ≤ m ≤ 100
- 1 ≤ n ≤ 20
- 1 ≤ target ≤ m
- 0 ≤ houses[i] ≤ n
- 0 ≤ cost[i][c] ≤ 1e4
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 1+1+1+1+5=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
The pre-painted colours already form 4 neighborhoods; cannot reduce to 3.