func connectTwoGroups(cost [][]int) int {
m := len(cost[0])
f := make([]int, 1<<m)
for j := 0; j < m; j++ {
mn := math.MaxInt
for _, c := range cost {
mn = min(mn, c[j])
}
bit := 1 << j
for mask := 0; mask < bit; mask++ {
f[bit|mask] = f[mask] + mn
}
}
for _, row := range cost {
for j := 1<<m - 1; j >= 0; j-- {
res := math.MaxInt
for k, c := range row { // 第一组的点 i 与第二组的点 k
res = min(res, f[j&^(1<<k)]+c)
}
f[j] = res
}
}
return f[1<<m-1]
}
func min(a, b int) int { if b < a { return b }; return a }
class Solution {
public int connectTwoGroups(List<List<Integer>> cost) {
int m = cost.get(0).size();
var f = new int[1 << m];
for (int j = 0; j < m; j++) {
int mn = Integer.MAX_VALUE;
for (var c : cost)
mn = Math.min(mn, c.get(j));
int bit = 1 << j;
for (int mask = 0; mask < bit; mask++)
f[bit | mask] = f[mask] + mn;
}
for (var row : cost) {
var r = row.toArray(); // 转成数组效率更高
for (int j = (1 << m) - 1; j >= 0; j--) {
int res = Integer.MAX_VALUE;
for (int k = 0; k < m; k++) // 第一组的点 i 与第二组的点 k
res = Math.min(res, f[j & ~(1 << k)] + (int) r[k]);
f[j] = res;
}
}
return f[(1 << m) - 1];
}
}
# 递推优化
class Solution:
def connectTwoGroups(self, cost: List[List[int]]) -> int:
f = [0] * (1 << len(cost[0]))
for j, mn in enumerate(map(min, zip(*cost))):
bit = 1 << j
for mask in range(bit):
f[bit | mask] = f[mask] + mn
for row in cost:
for j in range(len(f) - 1, -1, -1):
f[j] = min(f[j & ~(1 << k)] + c for k, c in enumerate(row))
return f[-1]
func connectTwoGroups(cost [][]int) int {
n, m := len(cost), len(cost[0])
minCost := make([]int, m)
for j := 0; j < m; j++ {
minCost[j] = math.MaxInt
for _, c := range cost {
minCost[j] = min(minCost[j], c[j])
}
}
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, 1<<m)
}
for j := 0; j < 1<<m; j++ {
for k, c := range minCost {
if j>>k&1 == 1 { // 第二组的点 k 未连接
f[0][j] += c // 去第一组找个成本最小的点连接
}
}
}
for i, row := range cost {
for j := 0; j < 1<<m; j++ {
res := math.MaxInt
for k, c := range row { // 第一组的点 i 与第二组的点 k
res = min(res, f[i][j&^(1<<k)]+c)
}
f[i+1][j] = res
}
}
return f[n][1<<m-1]
}
func min(a, b int) int { if b < a { return b }; return a }
class Solution {
public int connectTwoGroups(List<List<Integer>> cost) {
int n = cost.size(), m = cost.get(0).size();
var minCost = new int[m];
Arrays.fill(minCost, Integer.MAX_VALUE);
for (int j = 0; j < m; j++)
for (var c : cost)
minCost[j] = Math.min(minCost[j], c.get(j));
var f = new int[n + 1][1 << m];
for (int j = 0; j < 1 << m; j++)
for (int k = 0; k < m; k++)
if ((j >> k & 1) == 1) // 第二组的点 k 未连接
f[0][j] += minCost[k]; // 去第一组找个成本最小的点连接
for (int i = 0; i < n; i++) {
for (int j = 0; j < 1 << m; j++) {
int res = Integer.MAX_VALUE;
for (int k = 0; k < m; k++) // 第一组的点 i 与第二组的点 k
res = Math.min(res, f[i][j & ~(1 << k)] + cost.get(i).get(k));
f[i + 1][j] = res;
}
}
return f[n][(1 << m) - 1];
}
}
# 1:1递推
class Solution:
def connectTwoGroups(self, cost: List[List[int]]) -> int:
n, m = len(cost), len(cost[0])
min_cost = [min(col) for col in zip(*cost)] # 每一列的最小值
f = [[0] * (1 << m) for _ in range(n + 1)]
for j in range(1 << m):
f[0][j] = sum(c for k, c in enumerate(min_cost) if j >> k & 1)
for i, row in enumerate(cost):
for j in range(1 << m):
f[i + 1][j] = min(f[i][j & ~(1 << k)] + c
for k, c in enumerate(row)) # 第一组的点 i 与第二组的点 k
return f[n][-1]
func connectTwoGroups(cost [][]int) int {
n, m := len(cost), len(cost[0])
minCost := make([]int, m)
for j := 0; j < m; j++ {
minCost[j] = math.MaxInt
for _, c := range cost {
minCost[j] = min(minCost[j], c[j])
}
}
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, 1<<m)
for j := range memo[i] {
memo[i][j] = -1 // -1 表示没有计算过
}
}
var dfs func(int, int) int
dfs = func(i, j int) (res int) {
if i < 0 {
for k, c := range minCost {
if j>>k&1 == 1 { // 第二组的点 k 未连接
res += c // 去第一组找个成本最小的点连接
}
}
return
}
p := &memo[i][j]
if *p != -1 { // 之前算过了
return *p
}
res = math.MaxInt
for k, c := range cost[i] { // 第一组的点 i 与第二组的点 k
res = min(res, dfs(i-1, j&^(1<<k))+c)
}
*p = res // 记忆化
return *p
}
return dfs(n-1, 1<<m-1)
}
func min(a, b int) int { if b < a { return b }; return a }
class Solution {
private List<List<Integer>> cost;
private int[] minCost;
private int[][] memo;
public int connectTwoGroups(List<List<Integer>> cost) {
this.cost = cost;
int n = cost.size(), m = cost.get(0).size();
minCost = new int[m];
Arrays.fill(minCost, Integer.MAX_VALUE);
for (int j = 0; j < m; j++)
for (var c : cost)
minCost[j] = Math.min(minCost[j], c.get(j));
memo = new int[n][1 << m];
for (int i = 0; i < n; i++)
Arrays.fill(memo[i], -1); // -1 表示没有计算过
return dfs(n - 1, (1 << m) - 1);
}
private int dfs(int i, int j) {
if (i < 0) {
int res = 0;
for (int k = 0; k < minCost.length; k++)
if ((j >> k & 1) == 1) // 第二组的点 k 未连接
res += minCost[k]; // 去第一组找个成本最小的点连接
return res;
}
if (memo[i][j] != -1) return memo[i][j]; // 之前算过了
int res = Integer.MAX_VALUE;
for (int k = 0; k < minCost.length; k++) // 第一组的点 i 与第二组的点 k
res = Math.min(res, dfs(i - 1, j & ~(1 << k)) + cost.get(i).get(k));
return memo[i][j] = res; // 记忆化
}
}
# 动态规划
# dfs(i, j) 第一组0..i与第二组0..m-1相连，且第二组集合j未被连接，最小成本
class Solution:
def connectTwoGroups(self, cost: List[List[int]]) -> int:
n, m = len(cost), len(cost[0])
min_cost = [min(col) for col in zip(*cost)] # 每一列的最小值
@cache # 记忆化搜索
def dfs(i: int, j: int) -> int:
if i < 0:
return sum(c for k, c in enumerate(min_cost) if j >> k & 1)
return min(dfs(i - 1, j & ~(1 << k)) + c
for k, c in enumerate(cost[i])) # 第一组的点 i 与第二组的点 k
return dfs(n - 1, (1 << m) - 1)
