1473. Paint House III

https://leetcode.com/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 (labeled from 1 to n), some houses that has been painted last summer should not be painted again.

A neighborhood is a maximal group of continuous houses that are painted with the same color. (For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods [{1}, {2,2}, {3,3}, {2}, {1,1}]).

Given an array houses, an m * n matrix cost and an integer target where:

• houses[i]: is the color of the house i, 0 if the house is not painted yet.

• cost[i][j]: is the cost of paint the house i with the color j+1.

Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods, if 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 = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (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 = 3
Output: 11
Explanation: Some houses are already painted, Paint the houses of this way [2,2,1,2,2]
This array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}]. 
Cost of paint the first and last house (10 + 1) = 11.

Example 3:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
Output: 5

Example 4:

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: Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.

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

houses的每个元素值表示对应house的颜色，颜色取值为[1, n]，0代表该house需要上色，cost[i][j]表示i房上j色所需cost，问argmin(将houses划分成target个相同颜色的子数组的cost)。优化 + 划分=> DP。对i房的action为它独立形成新的划分，还是和前面的并在一起；这又取决于i房用什么颜色。因此需要i，划分数和颜色表状态，dp[i][j][c]表前i个house组成j个划分且i房颜色为c时的min cost。遍历i, j，对dp[i][j]检查house[i]有没有颜色，有就遍历它前面元素所有可能的颜色并找min(dp[i - 1][j][c], dp[i-1][j-1][c2])；没有颜色则额外加上cost[i][c]。

class Solution:
    def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
        dp = [[[math.inf] * n for _ in range(target)] for _ in range(m)]
        if houses[0] != 0:
            dp[0][0][houses[0] - 1] = 0
        else:
            for c in range(n):
                dp[0][0][c] = cost[0][c] 
        for i in range(1, m):
            for j in range(min(target, i + 1)):
                if houses[i] != 0:
                    c = houses[i] - 1
                    for c2 in range(n):
                        if c == c2:
                            dp[i][j][c] = min(dp[i][j][c], dp[i - 1][j][c])
                        else:
                            if j > 0 and dp[i - 1][j - 1][c2] != math.inf: 
                                dp[i][j][c] = min(dp[i][j][c], dp[i - 1][j - 1][c2])
                    continue
                for c in range(n):
                    for c2 in range(n):
                        if c == c2:
                            if dp[i - 1][j][c2] != math.inf:
                                dp[i][j][c] = min(dp[i][j][c], dp[i - 1][j][c2] + cost[i][c])
                        else:
                            if j > 0 and dp[i - 1][j - 1][c2] != math.inf: 
                                dp[i][j][c] = min(dp[i][j][c], dp[i - 1][j - 1][c2] + cost[i][c])
        res = min(dp[-1][-1])
        return -1 if res == math.inf else res