Formatted question description: https://leetcode.ca/all/1473.html

# 1473. Paint House III (Hard)

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 = 3Output:9Explanation: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 = 3Output:11Explanation: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 = 5Output: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 = 3Output:-1Explanation: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`

**Related Topics**:

Dynamic Programming

## Solution 1. DP Top-down

This looks like a DP problem because:

- it involves searching
- it only cares about the optimal solution – Optimal substructure
- During searching, we might go into the same state from different paths – Overlapping sub-problems.

The first task we need to do is to design the state of the sub-problem. I identified three:

- the index of the current house (we scan them one by one from left to right). Denote it as
`i`

,`0 <= i < M`

. - The color of the previous house. Denote it as
`last`

,`0 <= last <= N`

. - Lastly, the count of the neighbors. Denote it as
`cnt`

,`0 <= cnt <= target + 1`

.

So we can represent the state using `dp[i][last][cnt]`

Now we need to think about the transition between the states. It’s quite straight forward:

- If
`house[i]`

is already painted, we just skip it so`dp[i][last][cnt] = dp[i + 1][H[i]][H[i] == last ? cnt : (cnt + 1)]`

. - Otherwise, we just try colors from
`1`

to`N`

, and store the best option in`dp[i][last][cnt]`

.

```
dp[i][last][cnt] = dp[i + 1][H[i]][H[i] == last ? cnt : (cnt + 1)] // If house[i] > 0
= min( cost[i][j] + dp[i + 1][j + 1][j + 1 == last ? cnt : (cnt + 1)] | 0 <= j < N ) // If house[i] == 0
```

We initialize `dp`

array using `-1`

which means unvisited.

For invalid states, like `cnt > T`

or `i == M && cnt != T`

, we mark the corresponding `dp`

value as `Infinity`

.

The answer is `dp[0][0][0]`

.

```
// OJ: https://leetcode.com/problems/paint-house-iii/
// Time: O(N^2 * MT)
// Space: O(MNT)
class Solution {
vector<int> H;
vector<vector<int>> C;
int M, N, T, INF = 1e6;
vector<vector<vector<int>>> memo;
int dp(int i, int last, int cnt) {
if (cnt > T) return INF;
if (i == M) return cnt == T ? 0 : INF;
if (memo[i][last][cnt] != -1) return memo[i][last][cnt];
if (H[i]) return memo[i][last][cnt] = dp(i + 1, H[i], H[i] == last ? cnt : (cnt + 1));
int ans = INF;
for (int j = 0; j < N; ++j) ans = min(ans, C[i][j] + dp(i + 1, j + 1, j + 1 == last ? cnt : (cnt + 1)));
return memo[i][last][cnt] = ans;
}
public:
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
H = houses, C = cost, M = m, N = n, T = target;
memo.assign(M, vector<vector<int>>(N + 1, vector<int>(T + 1, -1)));
int ans = dp(0, 0, 0);
return ans == INF ? -1 : ans;
}
};
```

## Solution 2. Bottom-up DP

Let `dp[i][last][cnt]`

be the answer to the sub-problem on the houses in range `[i, M)`

and `last`

is the color of the `i - 1`

-th house, and `cnt`

is the number of neighbors existed before `i - 1`

-th house. `0 <= i < M`

, `1 <= last <= N`

, `0 <= cnt <= M`

.

For `dp[i][last][cnt]`

, we have the following options:

- If
`houses[i] > 0`

,`dp[i][last][cnt] = dp[i + 1][houses[i]][ houses[i] == last ? cnt : (cnt + 1) ]`

. - Otherwise, we try different colors for the
`i`

-th house,`dp[i][last][cnt] = min( dp[i + 1][j][ j == last ? cnt : (cnt + 1) ] + cost[i][j - 1] | 1 <= j <= N )`

.

```
dp[i][last][cnt] = dp[i + 1][houses[i]][ houses[i] == last ? cnt : (cnt + 1) ] // If houses[i] > 0
= min( dp[i + 1][j][ j == last ? cnt : (cnt + 1) ] + cost[i][j - 1] | 1 <= j <= N ) // If houses[i] == 0
dp[M][last][target] = 0 where 0 < last <= N
```

The `dp`

array are initialized with value `Infinity`

.

```
// OJ: https://leetcode.com/problems/paint-house-iii/
// Time: O(N^2 * MT)
// Space: O(MNT)
class Solution {
public:
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
int INF = 1e6;
vector<vector<vector<int>>> dp(m + 1, vector<vector<int>>(n + 1, vector<int>(target + 2, INF)));
for (int last = 0; last <= n; ++last) dp[m][last][target] = 0;
for (int i = m - 1; i >= 0; --i) {
for (int last = 0; last <= n; ++last) {
for (int cnt = 0; cnt <= target; ++cnt) {
if (houses[i]) dp[i][last][cnt] = dp[i + 1][houses[i]][houses[i] == last ? cnt : (cnt + 1)];
else {
for (int j = 1; j <= n; ++j) dp[i][last][cnt] = min(dp[i][last][cnt], dp[i + 1][j][j == last ? cnt : (cnt + 1)] + cost[i][j - 1]);
}
}
}
}
return dp[0][0][0] == INF ? -1 : dp[0][0][0];
}
};
```

Java

```
class Solution {
public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
final int INFINITY = 1000000000;
int[][][] dp = new int[m + 1][target + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= target; j++) {
for (int k = 0; k <= n; k++)
dp[i][j][k] = INFINITY;
}
}
if (houses[0] > 0)
dp[0][1][houses[0]] = 0;
else {
for (int i = 1; i <= n; i++)
dp[0][1][i] = cost[0][i - 1];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j <= target; j++) {
if (houses[i] > 0) {
int temp = houses[i];
for (int k = 1; k <= n; k++) {
if (temp == k)
dp[i][j][temp] = Math.min(dp[i][j][temp], dp[i - 1][j][k]);
else
dp[i][j][temp] = Math.min(dp[i][j][temp], dp[i - 1][j - 1][k]);
}
} else {
for (int k = 1; k <= n; k++) {
for (int s = 1; s <= n; s++) {
if (k == s)
dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j][s] + cost[i][k - 1]);
else
dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j - 1][s] + cost[i][k - 1]);
}
}
}
}
}
int minCost = INFINITY;
for (int i = 1; i <= n; i++)
minCost = Math.min(minCost, dp[m - 1][target][i]);
return minCost == INFINITY ? -1 : minCost;
}
}
```