Bit Manipulation
Array
Dynamic Programming
Bitmask
Matrix
Description
You are given two groups of points where the first group has size1
points, the second group has size2
points, and size1 >= size2
.
The cost
of the connection between any two points are given in an size1 x size2
matrix where cost[i][j]
is the cost of connecting point i
of the first group and point j
of the second group. The groups are connected if each point in both groups is connected to one or more points in the opposite group . In other words, each point in the first group must be connected to at least one point in the second group, and each point in the second group must be connected to at least one point in the first group.
Return the minimum cost it takes to connect the two groups .
Example 1:
Input: cost = [[15, 96], [36, 2]]
Output: 17
Explanation : The optimal way of connecting the groups is:
1--A
2--B
This results in a total cost of 17.
Example 2:
Input: cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
Output: 4
Explanation : The optimal way of connecting the groups is:
1--A
2--B
2--C
3--A
This results in a total cost of 4.
Note that there are multiple points connected to point 2 in the first group and point A in the second group. This does not matter as there is no limit to the number of points that can be connected. We only care about the minimum total cost.
Example 3:
Input: cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
Output: 10
Constraints:
size1 == cost.length
size2 == cost[i].length
1 <= size1 , size2 <= 12
size1 >= size2
0 <= cost[i][j] <= 100
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution :
def connectTwoGroups ( self , cost : List [ List [ int ]]) -> int :
m , n = len ( cost ), len ( cost [ 0 ])
f = [[ inf ] * ( 1 << n ) for _ in range ( m + 1 )]
f [ 0 ][ 0 ] = 0
for i in range ( 1 , m + 1 ):
for j in range ( 1 << n ):
for k in range ( n ):
if ( j >> k & 1 ) == 0 :
continue
c = cost [ i - 1 ][ k ]
x = min ( f [ i ][ j ^ ( 1 << k )], f [ i - 1 ][ j ], f [ i - 1 ][ j ^ ( 1 << k )]) + c
f [ i ][ j ] = min ( f [ i ][ j ], x )
return f [ m ][ - 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 class Solution {
public int connectTwoGroups ( List < List < Integer >> cost ) {
int m = cost . size (), n = cost . get ( 0 ). size ();
final int inf = 1 << 30 ;
int [][] f = new int [ m + 1 ][ 1 << n ] ;
for ( int [] g : f ) {
Arrays . fill ( g , inf );
}
f [ 0 ][ 0 ] = 0 ;
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = 0 ; j < 1 << n ; ++ j ) {
for ( int k = 0 ; k < n ; ++ k ) {
if (( j >> k & 1 ) == 1 ) {
int c = cost . get ( i - 1 ). get ( k );
f [ i ][ j ] = Math . min ( f [ i ][ j ] , f [ i ][ j ^ ( 1 << k ) ] + c );
f [ i ][ j ] = Math . min ( f [ i ][ j ] , f [ i - 1 ][ j ] + c );
f [ i ][ j ] = Math . min ( f [ i ][ j ] , f [ i - 1 ][ j ^ ( 1 << k ) ] + c );
}
}
}
}
return f [ m ][ ( 1 << n ) - 1 ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public :
int connectTwoGroups ( vector < vector < int >>& cost ) {
int m = cost . size (), n = cost [ 0 ]. size ();
int f [ m + 1 ][ 1 << n ];
memset ( f , 0x3f , sizeof ( f ));
f [ 0 ][ 0 ] = 0 ;
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = 0 ; j < 1 << n ; ++ j ) {
for ( int k = 0 ; k < n ; ++ k ) {
if ( j >> k & 1 ) {
int c = cost [ i - 1 ][ k ];
int x = min ({ f [ i ][ j ^ ( 1 << k )], f [ i - 1 ][ j ], f [ i - 1 ][ j ^ ( 1 << k )]}) + c ;
f [ i ][ j ] = min ( f [ i ][ j ], x );
}
}
}
}
return f [ m ][( 1 << n ) - 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 func connectTwoGroups ( cost [][] int ) int {
m , n := len ( cost ), len ( cost [ 0 ])
const inf = 1 << 30
f := make ([][] int , m + 1 )
for i := range f {
f [ i ] = make ([] int , 1 << n )
for j := range f [ i ] {
f [ i ][ j ] = inf
}
}
f [ 0 ][ 0 ] = 0
for i := 1 ; i <= m ; i ++ {
for j := 0 ; j < 1 << n ; j ++ {
for k := 0 ; k < n ; k ++ {
c := cost [ i - 1 ][ k ]
if j >> k & 1 == 1 {
f [ i ][ j ] = min ( f [ i ][ j ], f [ i ][ j ^( 1 << k )] + c )
f [ i ][ j ] = min ( f [ i ][ j ], f [ i - 1 ][ j ] + c )
f [ i ][ j ] = min ( f [ i ][ j ], f [ i - 1 ][ j ^( 1 << k )] + c )
}
}
}
}
return f [ m ][( 1 << n ) - 1 ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 function connectTwoGroups ( cost : number [][]) : number {
const m = cost . length ;
const n = cost [ 0 ]. length ;
const inf = 1 << 30 ;
const f : number [][] = Array ( m + 1 )
. fill ( 0 )
. map (() => Array ( 1 << n ). fill ( inf ));
f [ 0 ][ 0 ] = 0 ;
for ( let i = 1 ; i <= m ; ++ i ) {
for ( let j = 0 ; j < 1 << n ; ++ j ) {
for ( let k = 0 ; k < n ; ++ k ) {
if ((( j >> k ) & 1 ) === 1 ) {
const c = cost [ i - 1 ][ k ];
f [ i ][ j ] = Math . min ( f [ i ][ j ], f [ i ][ j ^ ( 1 << k )] + c );
f [ i ][ j ] = Math . min ( f [ i ][ j ], f [ i - 1 ][ j ] + c );
f [ i ][ j ] = Math . min ( f [ i ][ j ], f [ i - 1 ][ j ^ ( 1 << k )] + c );
}
}
}
}
return f [ m ][( 1 << n ) - 1 ];
}
Solution 2
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def connectTwoGroups ( self , cost : List [ List [ int ]]) -> int :
m , n = len ( cost ), len ( cost [ 0 ])
f = [ inf ] * ( 1 << n )
f [ 0 ] = 0
g = f [:]
for i in range ( 1 , m + 1 ):
for j in range ( 1 << n ):
g [ j ] = inf
for k in range ( n ):
if ( j >> k & 1 ) == 0 :
continue
c = cost [ i - 1 ][ k ]
x = min ( g [ j ^ ( 1 << k )], f [ j ], f [ j ^ ( 1 << k )]) + c
g [ j ] = min ( g [ j ], x )
f = g [:]
return f [ - 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 class Solution {
public int connectTwoGroups ( List < List < Integer >> cost ) {
int m = cost . size (), n = cost . get ( 0 ). size ();
final int inf = 1 << 30 ;
int [] f = new int [ 1 << n ] ;
Arrays . fill ( f , inf );
f [ 0 ] = 0 ;
int [] g = f . clone ();
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = 0 ; j < 1 << n ; ++ j ) {
g [ j ] = inf ;
for ( int k = 0 ; k < n ; ++ k ) {
if (( j >> k & 1 ) == 1 ) {
int c = cost . get ( i - 1 ). get ( k );
g [ j ] = Math . min ( g [ j ] , g [ j ^ ( 1 << k ) ] + c );
g [ j ] = Math . min ( g [ j ] , f [ j ] + c );
g [ j ] = Math . min ( g [ j ] , f [ j ^ ( 1 << k ) ] + c );
}
}
}
System . arraycopy ( g , 0 , f , 0 , 1 << n );
}
return f [ ( 1 << n ) - 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 class Solution {
public :
int connectTwoGroups ( vector < vector < int >>& cost ) {
int m = cost . size (), n = cost [ 0 ]. size ();
const int inf = 1 << 30 ;
vector < int > f ( 1 << n , inf );
f [ 0 ] = 0 ;
vector < int > g = f ;
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = 0 ; j < 1 << n ; ++ j ) {
g [ j ] = inf ;
for ( int k = 0 ; k < n ; ++ k ) {
if ( j >> k & 1 ) {
int c = cost [ i - 1 ][ k ];
int x = min ({ g [ j ^ ( 1 << k )], f [ j ], f [ j ^ ( 1 << k )]}) + c ;
g [ j ] = min ( g [ j ], x );
}
}
}
f . swap ( g );
}
return f [( 1 << n ) - 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 func connectTwoGroups ( cost [][] int ) int {
m , n := len ( cost ), len ( cost [ 0 ])
const inf = 1 << 30
f := make ([] int , 1 << n )
for i := range f {
f [ i ] = inf
}
f [ 0 ] = 0
g := make ([] int , 1 << n )
for i := 1 ; i <= m ; i ++ {
for j := 0 ; j < 1 << n ; j ++ {
g [ j ] = inf
for k := 0 ; k < n ; k ++ {
c := cost [ i - 1 ][ k ]
if j >> k & 1 == 1 {
g [ j ] = min ( g [ j ], g [ j ^ 1 << k ] + c )
g [ j ] = min ( g [ j ], f [ j ] + c )
g [ j ] = min ( g [ j ], f [ j ^ 1 << k ] + c )
}
}
}
copy ( f , g )
}
return f [ 1 << n - 1 ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 function connectTwoGroups ( cost : number [][]) : number {
const m = cost . length ;
const n = cost [ 0 ]. length ;
const inf = 1 << 30 ;
const f : number [] = new Array ( 1 << n ). fill ( inf );
f [ 0 ] = 0 ;
const g = new Array ( 1 << n ). fill ( 0 );
for ( let i = 1 ; i <= m ; ++ i ) {
for ( let j = 0 ; j < 1 << n ; ++ j ) {
g [ j ] = inf ;
for ( let k = 0 ; k < n ; ++ k ) {
if ((( j >> k ) & 1 ) === 1 ) {
const c = cost [ i - 1 ][ k ];
g [ j ] = Math . min ( g [ j ], g [ j ^ ( 1 << k )] + c );
g [ j ] = Math . min ( g [ j ], f [ j ] + c );
g [ j ] = Math . min ( g [ j ], f [ j ^ ( 1 << k )] + c );
}
}
}
f . splice ( 0 , f . length , ... g );
}
return f [( 1 << n ) - 1 ];
}
GitHub