> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/partition/1473.-paint-house-iii.md).

# 1473. 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]。

```python
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
        
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/partition/1473.-paint-house-iii.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.