题目

给你两组点，其中第一组中有 size1 个点，第二组中有 size2 个点，且 size1 >= size2 。

任意两点间的连接成本 cost 由大小为 size1 x size2 矩阵给出，其中 cost[i][j] 是第一组中的点 i 和第二组中的点 j 的连接成本。如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。

返回连通两组点所需的最小成本。

输入：cost = [[15, 96], [36, 2]]
输出：17
解释：连通两组点的最佳方法是：
1--A
2--B
总成本为 17 。

输入：cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
输出：4
解释：连通两组点的最佳方法是：
1--A
2--B
2--C
3--A
最小成本为 4 。
请注意，虽然有多个点连接到第一组中的点 2 和第二组中的点 A ，但由于题目并不限制连接点的数目，所以只需要关心最低总成本。

输入：cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
输出：10

提示：

size1 == cost.length
size2 == cost[i].length
1 <= size1, size2 <= 12
size1 >= size2
0 <= cost[i][j] <= 100

解题思路

位集合+记忆化搜索：考虑枚举两组之间的匹配取最小值,由于数据范围比较小,可以用位集合表示第二组的子集,使用记忆化搜索减少重复计算。

位集合+记忆化搜索

class Solution {
    List<List<Integer>> cost;
    int size1,size2;
    int[] minCost;
    int[][] memo;
    public int connectTwoGroups(List<List<Integer>> cost) {
        //数据范围小: dp/记忆化搜索 + 位集合(状态压缩)
        this.cost = cost;
        size1 = cost.size();
        size2 = cost.get(0).size();
        //dfs(i,j)表示第一组i个点和第二组j个点连通的最小代价
        minCost = new int[size2];
        for(int j = 0; j < size2; j++) {
            int min = Integer.MAX_VALUE;
            for(List<Integer> list : cost) {
                min = Math.min(min,list.get(j));
            }
            minCost[j] = min;
        }
        memo = new int[size1][1<<size2]; //状态个数 size1 * 2^size2
        for(int i = 0; i < size1; i++) Arrays.fill(memo[i],-1);
        return dfs(size1 - 1, (1<<size2) - 1);
    }

    int dfs(int i, int j){
        //此时第一组i连接完毕 但是第二组j可能还有未连接的点,找minCost连上
        if(i < 0) {
            int res = 0;
            for(int k = 0; k < size2; k++) {
                //集合j的第k位=1则未连接,在第一组i中连上最小cost的点 minCost可预处理
                if(((j>>k) & 1) == 1) res += minCost[k];
            }
            return res;
        }
        if(memo[i][j] != -1) return memo[i][j];
        int res = Integer.MAX_VALUE;
        //枚举点i和每个第二组的点k相连
        //dfs(i,j)=min(dfs(去除点i,去除k)+ 点i和点k连接)
        for(int k = 0; k < size2; k++) {
            //j和1<<k的反相与 去除k
            res = Math.min(res,dfs(i-1,j&~(1<<k))+cost.get(i).get(k));
        }
        return memo[i][j] = res;
    }
}