> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/paint-house-iii.md).

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

```java
class Solution {
    Integer[][][] dp;

    public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        dp = new Integer[m][n][target + 1];
        return helper(houses, cost, 0, -1, target);
    }

    public int helper(int[] house, int[][] cost, int index, int colorOfPrevHouse, int target) {
        if (index == house.length) {
            if (target == 0)
                return 0;
            return -1;
        }
        if (target < 0)
            return -1;
        if (colorOfPrevHouse != -1)
            if (dp[index][colorOfPrevHouse][target] != null)
                return dp[index][colorOfPrevHouse][target];
        int ans = Integer.MAX_VALUE;
        // If current house is already colored
        if (house[index] != 0) {
            // If current house has same color as previous house
            if (house[index] == colorOfPrevHouse + 1)
                ans = helper(house, cost, index + 1, colorOfPrevHouse, target);
            else if (target > 0)
                ans = helper(house, cost, index + 1, house[index] - 1, target - 1);
        }
        // Else
        else {
            if (colorOfPrevHouse != -1) {
                // If we paint same color as previous house
                int ans2 = helper(house, cost, index + 1, colorOfPrevHouse, target);
                if (ans2 != -1)
                    ans = Math.min(ans, ans2 + cost[index][colorOfPrevHouse]);
                // Else if we want it in a different color
                if (target > 0) {
                    for (int j = 0; j < cost[index].length; j++) {
                        if (j == colorOfPrevHouse)
                            continue;
                        int res = helper(house, cost, index + 1, j, target - 1);
                        if (res != -1)
                            ans = Math.min(ans, cost[index][j] + res);
                    }
                }
            } else
                for (int j = 0; j < cost[index].length; j++) {
                    int res = helper(house, cost, index + 1, j, target - 1);
                    if (res != -1)
                        ans = Math.min(cost[index][j] + res, ans);
                }
        }
        if (colorOfPrevHouse != -1)
            dp[index][colorOfPrevHouse][target] = ans == Integer.MAX_VALUE ? -1 : ans;
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
```