Paint House III

I had this on a Stripe systems-onsite as the second-round DP, and the trick that took me three takes to nail was naming the right state. Two-dimensional (house, color) is paint-house; three-dimensional (house, color, neighborhoodsFormed) is this problem. Once you write the third axis explicitly, the recurrence is mechanical. The catalog covered paint-house and paint-fence, but it skipped this neighborhoods-constrained variant where the answer requires EXACTLY target runs.

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 that have been painted last summer should not be painted again.

A NEIGHBORHOOD is a maximal group of CONTIGUOUS houses that are painted with the same color.

Given an array houses (where houses[i] != 0 means house i is already painted with color houses[i], and houses[i] == 0 means it needs to be painted), an m x n cost matrix cost (where cost[i][j] is the cost of painting house i with color j + 1), and an integer target, return the minimum cost of painting all the unpainted houses such that there are exactly target neighborhoods. If it is not possible, return -1.

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
• Explanation: Paint as [1, 2, 2, 1, 1]: cost 1 + 1 + 1 + 1 + 5 = 9. Three neighborhoods: {1}, {2, 2}, {1, 1}.

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: Paint house 0 color 2 and house 4 color 2: [2, 2, 1, 2, 2], cost 10 + 1 = 11. Three neighborhoods: {2, 2}, {1}, {2, 2}.

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: All houses are already painted to a configuration with 4 neighborhoods, but target is 3. We cannot repaint, so it's impossible.

Example 4:

• Input: houses = [0], cost = [[1, 2, 3]], m = 1, n = 3, target = 1
• Output: 1
• Explanation: Paint the one house with the cheapest color (1).

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.

Follow-up

Why is the state (i, prevColor, k)? Because the cost of painting house i and the question "does this start a new neighborhood?" both depend ONLY on the house index, the color of the IMMEDIATELY PRECEDING house, and how many neighborhoods we've formed so far. Adding more state (the full color sequence, for instance) is redundant; subtracting state breaks the recurrence.