Array
Dynamic Programming
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.length
n == cost[i].length
1 <= m <= 100
1 <= n <= 20
1 <= target <= m
0 <= houses[i] <= n
1 <= cost[i][j] <= 104
Solutions
Solution 1
Python3 Java C++ Go TypeScript
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 ;
}
GitHub