写在前面
又是一次周赛题，这次周赛运气还不错，做出了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，相当于集合运算中的取交集运算。
| 或运算符
比较参与运算的两个数的每一位，有一个为1则结果的该位为1，反之为0.
作用：或运算最常用的就是置一了。因为两个数中有一个为1就会使得结果为1，所以只要使用 (1 << k) | number 便可以将 number 的第k位置一，同理通过自己设计数据可以将 number 的任意位置一。
集合中：或运算相当于集合中取并集运算。
^ 异或运算符
比较参与运算的两个数的每一位，若对应位的数字不同则结果的该位为1，反之为0.
作用：由于异或运算不同为1，相同为0，所以任意数与0异或将会保留原值，任意数与1异或将会翻转每一位(0 < -- > 1)。
集合中：a ^ b相当于取a - b，即b在a中的补集。
枚举子集
假设我们有一个用二进制数 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问题，真的是很难，看了小半天总算是看的差不多看懂了，感觉再遇到也还是写不出来，过些天多复习复习看看了。
如果文章有任何写的不正确的地方还请指出，感恩相遇~
