写在前面

又是一次周赛题，这次周赛运气还不错，做出了3道题，最后这道开始以为是贪心，结果试了不行，没想到是状态压缩DP问题，以前也没有接触过，再加上一些细小的知识点，新学到了不少知识~ 感谢这两位大佬的题解帮助我理解 lucifer1004、AerysN

题目

核心思路

介绍解法之前要先记录一点会用到的知识点。

状态压缩

别看词说的很高大上，其实就是一种枚举所有状态的方式。对于可以用布尔量表示的状态(灯开或关、石子取或不取)，由于对每一个位置只有两种选择，所以所有可能总共有 2 ^ N 种情况，那么可以考虑用二进制来表示其中的每一种情况，如果一种情况的某一位是 1 表示这位所对应的位置为 true(开、取…)，反之为 false(关、不取…)。通过二进制数来表示状态的方法就称为状态压缩。这样的话，如果有N个位置，总共就有1 << N种情况，通过遍历就可以考虑每种情况。

位运算的作用

虽然很早就接触了位运算，但是一直也不清楚他能有什么用处，除了偶尔在/2的时候用>> 1替换基本就没使用过了，所以刚开始看到大佬们的代码就一脸懵逼。。。感谢慕飞大佬的学习笔记

& 与运算符

比较参与运算的两个数的每一位，均为1则结果的该位为1，反之为0.
作用：取出指定位的值。使用 (1 << k) & number 便可以取出number第k位的值，可以在纸上写出来，1 << k 即 00100000 1后共k个0，这样做与运算后，只有 number 第k位的数字才不会被置零，所以最后的结果就是第k位的值

| 或运算符

比较参与运算的两个数的每一位，有一个为1则结果的该位为1，反之为0.
作用：或运算最常用的就是置一了。因为两个数中有一个为1就会使得结果为1，所以只要使用 (1 << k) | number 便可以将 number 的第k位置一，同理通过自己设计数据可以将 number 的任意位置一。

^ 异或运算符

比较参与运算的两个数的每一位，若对应位的数字不同则结果的该位为1，反之为0.
作用：由于异或运算不同为1，相同为0，所以任意数与0异或将会保留原值，任意数与1异或将会翻转每一位(0 < -- > 1)。

枚举子集

假设我们有一个用二进制数 x 表示的集合（某一位为1代表集合含有对应元素，反之则代表集合中不含对应元素），我们应该如何来枚举它的子集？

朴素的想法是，枚举所有小于等于该数的二进制数，逐个检查当前枚举到的y是否是x的子集(是否满足x∣y=x)。由于 x 的子集必然是将 x 的某些位置零得到的，所以其子集和 x 的或运算不会改变 x 的值。

还可以做得更好吗？答案是肯定的。

for (int i = 1; i < (1 << n); ++i) {
    for (int j = i; j > 0; j = (j - 1) & i) {
        // ...
    }
}

这里最重要的代码就是 j = (j - 1) & i，首先将 j - 1，会使得 j 的最后一个1变为0，并将其后的所有0变为1，再与 i 做与运算，这样第一次运算时便是把 i 的最后一个1变成0，也就是不取最后一个位置。重复做此运算，就会依次将 i 中的某些1置位0，并且这样得到的 j 是所有小于 i 且是 i 子集的二进制数中最大的数。所以最终必然可以遍历 i 的所有子集。

解题思路

有了上边的知识储备，就可以来解决这道问题了。
题目中给出 size1 >= size2 ，所以通过状态压缩枚举 size2 效率会高一点。那么我们的dp数组的大小就可以是 dp = new int[n][1 << m]，其中n、m分别对应于 size1、size2。

状态定义

由于问题要求解的是第一组中的点与第二组的点全连通的最小费用，那么其子问题就是在第一组中的前i个点与第二组中的某j个点全连通的最小费用。这里要注意前和某的区别，由于最后求解的是两组中的所有点都要连通，所以只需要用一组的某些点来保证所有的可能，另一组取前i个点用来递推。这样既可以包含所求结果，又不至于计算过多无用的状态。
由此可以定义：dp[i][j] 表示 第一组中前 i 个点按取法j取第二组中的点所需的最小费用。这里的取法就是对应着状态压缩中的 1 << m 种方式。
既然要枚举所有可能，可以做一个预处理，计算第一组中第i个点按照取法j取第二组的点所需要的费用，这样在后边状态转移中就不需要重复计算了。

int n = cost.size(), m = cost.get(0).size();
int[][] costSum = new int[n][1 << m];//costSum[i][j]记录cost.get(i)这个点取另一组点所有取法的可能性对应的费用
for(int i = 0; i < n; i++){//遍历每个点
    for(int j = 1; j < 1 << m; j++){//遍历每个点对应的所有取法
        for(int k = 0; k < m; k++){
            if(((1 << k) & j) != 0){
                //表示取到第k列
                costSum[i][j] += cost.get(i).get(k);
            }
        }
    }
}

状态转移

先上一段代码

int[][] dp = new int[n][1 << m];//dp[i][j] 表示取到第i个点，另一组点的取法为j的情况下最小费用
for(int i = 1; i < n; i++)
    Arrays.fill(dp[i], Integer.MAX_VALUE);
dp[0] = costSum[0];

for(int i = 1; i < n; i++){
    for(int j = 1; j < 1 << m; j++){
        for(int k = 1; k < 1 << m; k++){
            //dp[i][j | k] 意味着在取法j的基础上再取若干个点所对应的最小费用
            //其值表示要么在前i行选取了 j | k 取法的点，要么在前i - 1行按取法k取点并在第i行按取法j取点
            //这样相当于遍历所有的可能，得到的结果集>=所求问题
            dp[i][j | k] = Math.min(dp[i][j | k], dp[i - 1][k] + costSum[i][j]);
        }
    }
}

实话说这个转移方程我现在也没有理解的很透彻。
其中的j 和 k 都是遍历所有的取法，而 j | k 是遍历到的取法j 和 取法k 的并集，这个并集对应的费用要么是第一组这前i个点满足取法j | k，要么在前i - 1个点中按照取法k取点并且第i个点按取法j取点。
这样取确实保证了对于每一个i，前i个点的所有可能取法都计算进去了，所考虑的结果集大于等于所求解的问题，所以也可以计算出最终的结果。不过转移公式我到现在也觉得讲不通。。。

我们看另外一种大佬的优化代码。

for (int i = 1; i < n; i++) {
    for (int j = 1; j < 1 << m; j++) {
        // 找到第i行取法j所有取到的第k列中，最小的那一列，加上dp[i - 1][j]，保证前i行能按取法j取到所有的点
        for (int k = 0; k < m; k++) {
            if (((1 << k) & j) != 0) {
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + cost.get(i).get(k));
            }
        }

        // (1 << m) - 1 得到一个1111111... 在异或运算相当于1变0，0变1，也就是取法j中所有没取到的点
        int restPoint = j ^ ((1 << m) - 1);
        // x = (x - 1) & restPoint子集枚举
        for (int x = restPoint; x > 0; x = (x - 1) & restPoint) {
            // j | x 表示取到 取法j 和 取法x的并集
            // dp[i][j | x] 的值 要么取法j | x之前就计算过的费用值; 要么是上一行按取法j，本行按取法x得到的费用值
            dp[i][j | x] = Math.min(dp[i][j | x], dp[i - 1][j] + costSum[i][x]);
        }
    }
}

每一部分代码的含义我都写在注释中了，这样分部分来计算就感觉更加有理有据了。

完整代码

class Solution {
    public int connectTwoGroups(List<List<Integer>> cost) {
        int n = cost.size(), m = cost.get(0).size();
        int[][] costSum = new int[n][1 << m];// costSum[i][j]记录cost.get(i)这个点取另一组点所有取法的可能性对应的费用
        for (int i = 0; i < n; i++) {// 遍历每个点
            for (int j = 1; j < 1 << m; j++) {// 遍历每个点对应的所有取法
                for (int k = 0; k < m; k++) {
                    if (((1 << k) & j) != 0) {
                        // 表示取到第k列
                        costSum[i][j] += cost.get(i).get(k);
                    }
                }
            }
        }

        int[][] dp = new int[n][1 << m];// dp[i][j] 表示第一组点取到前i个点，另一组点的取法为j的情况下最小费用
        for (int i = 1; i < n; i++)
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        dp[0] = costSum[0];

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < 1 << m; j++) {
                // 找到第i行取法j所有取到的第k列中，最小的那一列，加上dp[i - 1][j]，保证前i行能按取法j取到所有的点
                for (int k = 0; k < m; k++) {
                    if (((1 << k) & j) != 0) {
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + cost.get(i).get(k));
                    }
                }

                // (1 << m) - 1 得到一个1111111... 在异或运算相当于1变0，0变1，也就是取法j中所有没取到的点
                int restPoint = j ^ ((1 << m) - 1);
                // x = (x - 1) & restPoint子集枚举
                for (int x = restPoint; x > 0; x = (x - 1) & restPoint) {
                    // j | x 表示取到 取法j 和 取法x的并集
                    // dp[i][j | x] 的值 要么取法j | x之前就计算过的费用值; 要么是上一行按取法j，本行按取法x得到的费用值
                    dp[i][j | x] = Math.min(dp[i][j | x], dp[i - 1][j] + costSum[i][x]);
                }
            }
        }

        return dp[n - 1][(1 << m) - 1];
    }
}

总结

初遇状态压缩DP问题，真的是很难，看了小半天总算是看的差不多看懂了，感觉再遇到也还是写不出来，过些天多复习复习看看了。
如果文章有任何写的不正确的地方还请指出，感恩相遇~