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 = 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

Related Topics:
Dynamic Programming

## Solution 1. DP Top-down

This looks like a DP problem because:

1. it involves searching
2. it only cares about the optimal solution – Optimal substructure
3. 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.

// 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 == INF ? -1 : dp;
}
};


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)
dp[houses] = 0;
else {
for (int i = 1; i <= n; i++)
dp[i] = cost[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;
}
}