连通两组点的最小成本【LC1595】
给你两组点，其中第一组中有
size1个点，第二组中有size2个点，且size1 >= size2。任意两点间的连接成本
cost由大小为size1 x size2矩阵给出，其中cost[i][j]是第一组中的点i和第二组中的点j的连接成本。**如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。**换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。返回连通两组点所需的最小成本。
猛练状态压缩dp
dfs+回溯
- 思路
每个点都需要跟另一个组的至少一个点连接，计算最小成本。那么我们可以枚举第一组第i 个点与第2组哪个点连接。【先只保证第一组跟第二组中一个点连接，如果第二组有点没有连接，再将其和最小成本的点连接】。记录第二组点的连接状态，使用状态压缩dp解决。
实现
class Solution { int n, m; int[][] memo; int[] minCost; List<List<Integer>> cost; public int connectTwoGroups(List<List<Integer>> cost) { this.n = cost.size(); this.m = cost.get(0).size(); this.memo = new int[n][1 << m]; this.minCost = new int[m]; this.cost = cost; Arrays.fill(minCost, Integer.MAX_VALUE); for (int i = 0; i < n; i++){ Arrays.fill(memo[i], -1); } for (List<Integer> c : cost){ for (int i = 0; i < m; i++){ minCost[i] = Math.min(minCost[i], c.get(i)); } } return dfs(n - 1, 0); } public int dfs(int i, int mask){ if (i < 0){// 寻找第二组未连接的点，将其与第一组中最小成本的点连接 int res = 0; for (int j = 0; j < m; j++){ if (((mask >> j) & 1) == 0){ res += minCost[j]; } } return res; } if (memo[i][mask] != -1) return memo[i][mask]; int res = Integer.MAX_VALUE; // 枚举第一组第i个点与第2组哪个点连接【先只保证第一组跟第二组中一个点连接，如果第二组有点没有连接，再将其和最小成本的点连接】 for (int j = 0; j < m; j++){ res = Math.min(res, dfs(i - 1, mask | (1 << j)) + cost.get(i).get(j)) ; } return memo[i][mask] = res; } }
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]; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/minimum-cost-to-connect-two-groups-of-points/solutions/2314687/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-djxq/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
