Description
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 have 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 x n matrix cost and an integer target where:
houses[i]: is the color of the house i, and 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 it is 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 = [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.lengthn == cost[i].length1 <= m <= 1001 <= n <= 201 <= target <= m0 <= houses[i] <= n1 <= cost[i][j] <= 104
Solutions
Solution 1: Dynamic Programming
We define f[i][j][k] to represent the minimum cost to paint houses from index 0 to i, with the last house painted in color j, and exactly forming k blocks. The answer is f[m-1][j][target], where j ranges from 1 to n. Initially, we check if the house at index 0 is already painted. If it is not painted, then f[0][j][1] = cost[0][j - 1], where j ∈ [1,..n]. If it is already painted, then f[0][houses[0]][1] = 0. All other values of f[i][j][k] are initialized to ∞.
Next, we start iterating from index i=1. For each i, we check if the house at index i is already painted:
If it is not painted, we can paint the house at index i with color j. We enumerate the number of blocks k, where k ∈ [1,..min(target, i + 1)], and enumerate the color of the previous house j0, where j0 ∈ [1,..n]. Then we can derive the state transition equation:
f[i][j][k] = min_{j0 ∈ [1,..n]} { f[i - 1][j0][k - (j ≠ j0)] + cost[i][j - 1] }
If it is already painted, we can paint the house at index i with color j. We enumerate the number of blocks k, where k ∈ [1,..min(target, i + 1)], and enumerate the color of the previous house j0, where j0 ∈ [1,..n]. Then we can derive the state transition equation:
f[i][j][k] = min_{j0 ∈ [1,..n]} { f[i - 1][j0][k - (j ≠ j0)] }
Finally, we return f[m - 1][j][target], where j ∈ [1,..n]. If all values of f[m - 1][j][target] are ∞, then return -1.
The time complexity is O(m × n2 × target), and the space complexity is O(m × n × target). Here, m, n, and target represent the number of houses, the number of colors, and the number of blocks, respectively.
PythonJavaC++GoTypeScript
class Solution:
def minCost(
self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int
) -> int:
f = [[[inf] * (target + 1) for _ in range(n + 1)] for _ in range(m)]
if houses[0] == 0:
for j, c in enumerate(cost[0], 1):
f[0][j][1] = c
else:
f[0][houses[0]][1] = 0
for i in range(1, m):
if houses[i] == 0:
for j in range(1, n + 1):
for k in range(1, min(target + 1, i + 2)):
for j0 in range(1, n + 1):
if j == j0:
f[i][j][k] = min(
f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]
)
else:
f[i][j][k] = min(
f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]
)
else:
j = houses[i]
for k in range(1, min(target + 1, i + 2)):
for j0 in range(1, n + 1):
if j == j0:
f[i][j][k] = min(f[i][j][k], f[i - 1][j][k])
else:
f[i][j][k] = min(f[i][j][k], f[i - 1][j0][k - 1])
ans = min(f[-1][j][target] for j in range(1, n + 1))
return -1 if ans >= inf else ans(code-box)
class Solution {
public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
int[][][] f = new int[m][n + 1][target + 1];
final int inf = 1 << 30;
for (int[][] g : f) {
for (int[] e : g) {
Arrays.fill(e, inf);
}
}
if (houses[0] == 0) {
for (int j = 1; j <= n; ++j) {
f[0][j][1] = cost[0][j - 1];
}
} else {
f[0][houses[0]][1] = 0;
}
for (int i = 1; i < m; ++i) {
if (houses[i] == 0) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= Math.min(target, i + 1); ++k) {
for (int j0 = 1; j0 <= n; ++j0) {
if (j == j0) {
f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]);
} else {
f[i][j][k]
= Math.min(f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]);
}
}
}
}
} else {
int j = houses[i];
for (int k = 1; k <= Math.min(target, i + 1); ++k) {
for (int j0 = 1; j0 <= n; ++j0) {
if (j == j0) {
f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k]);
} else {
f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j0][k - 1]);
}
}
}
}
}
int ans = inf;
for (int j = 1; j <= n; ++j) {
ans = Math.min(ans, f[m - 1][j][target]);
}
return ans >= inf ? -1 : ans;
}
}(code-box)
class Solution {
public:
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
int f[m][n + 1][target + 1];
memset(f, 0x3f, sizeof(f));
if (houses[0] == 0) {
for (int j = 1; j <= n; ++j) {
f[0][j][1] = cost[0][j - 1];
}
} else {
f[0][houses[0]][1] = 0;
}
for (int i = 1; i < m; ++i) {
if (houses[i] == 0) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= min(target, i + 1); ++k) {
for (int j0 = 1; j0 <= n; ++j0) {
if (j == j0) {
f[i][j][k] = min(f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]);
} else {
f[i][j][k] = min(f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]);
}
}
}
}
} else {
int j = houses[i];
for (int k = 1; k <= min(target, i + 1); ++k) {
for (int j0 = 1; j0 <= n; ++j0) {
if (j == j0) {
f[i][j][k] = min(f[i][j][k], f[i - 1][j][k]);
} else {
f[i][j][k] = min(f[i][j][k], f[i - 1][j0][k - 1]);
}
}
}
}
}
int ans = 0x3f3f3f3f;
for (int j = 1; j <= n; ++j) {
ans = min(ans, f[m - 1][j][target]);
}
return ans == 0x3f3f3f3f ? -1 : ans;
}
};(code-box)
func minCost(houses []int, cost [][]int, m int, n int, target int) int {
f := make([][][]int, m)
const inf = 1 << 30
for i := range f {
f[i] = make([][]int, n+1)
for j := range f[i] {
f[i][j] = make([]int, target+1)
for k := range f[i][j] {
f[i][j][k] = inf
}
}
}
if houses[0] == 0 {
for j := 1; j <= n; j++ {
f[0][j][1] = cost[0][j-1]
}
} else {
f[0][houses[0]][1] = 0
}
for i := 1; i < m; i++ {
if houses[i] == 0 {
for j := 1; j <= n; j++ {
for k := 1; k <= target && k <= i+1; k++ {
for j0 := 1; j0 <= n; j0++ {
if j == j0 {
f[i][j][k] = min(f[i][j][k], f[i-1][j][k]+cost[i][j-1])
} else {
f[i][j][k] = min(f[i][j][k], f[i-1][j0][k-1]+cost[i][j-1])
}
}
}
}
} else {
j := houses[i]
for k := 1; k <= target && k <= i+1; k++ {
for j0 := 1; j0 <= n; j0++ {
if j == j0 {
f[i][j][k] = min(f[i][j][k], f[i-1][j][k])
} else {
f[i][j][k] = min(f[i][j][k], f[i-1][j0][k-1])
}
}
}
}
}
ans := inf
for j := 1; j <= n; j++ {
ans = min(ans, f[m-1][j][target])
}
if ans == inf {
return -1
}
return ans
}(code-box)
function minCost(houses: number[], cost: number[][], m: number, n: number, target: number): number {
const inf = 1 << 30;
const f: number[][][] = new Array(m)
.fill(0)
.map(() => new Array(n + 1).fill(0).map(() => new Array(target + 1).fill(inf)));
if (houses[0] === 0) {
for (let j = 1; j <= n; ++j) {
f[0][j][1] = cost[0][j - 1];
}
} else {
f[0][houses[0]][1] = 0;
}
for (let i = 1; i < m; ++i) {
if (houses[i] === 0) {
for (let j = 1; j <= n; ++j) {
for (let k = 1; k <= Math.min(target, i + 1); ++k) {
for (let j0 = 1; j0 <= n; ++j0) {
if (j0 === j) {
f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k] + cost[i][j - 1]);
} else {
f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j0][k - 1] + cost[i][j - 1]);
}
}
}
}
} else {
const j = houses[i];
for (let k = 1; k <= Math.min(target, i + 1); ++k) {
for (let j0 = 1; j0 <= n; ++j0) {
if (j0 === j) {
f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j][k]);
} else {
f[i][j][k] = Math.min(f[i][j][k], f[i - 1][j0][k - 1]);
}
}
}
}
}
let ans = inf;
for (let j = 1; j <= n; ++j) {
ans = Math.min(ans, f[m - 1][j][target]);
}
return ans >= inf ? -1 : ans;
}(code-box)
