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#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| 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;
}
|
