状压型
状压型
状态压缩DP，State Compression DP，又称Bitmask DP。
排列类问题，往往可以用状压型DP解决
通常的dp是用一个变量（如dp[i], dp[j]）表示一个状态，而Bitmask DP使用一个bitmask变量（dp[bitmask]），来表示一个集合的状态。bitmask是一个二进制或多进制数，是一个整数，状态压缩也就是将集合的状态压缩为一个整数来表示。
技巧：
如果用二进制表示子集并进行动态规划，集合中的元素就隐含了阶段信息。例如，
- 可以把集合中的最大元素当作“阶段”
- 可以把集合中的一的个数当作阶段
位集合操作
「二进制」中的「子集枚举」，具体表示为对给定的一个整数 xxx，不重复地枚举 mask 的「二进制」表示的非空子集 sub，其中 y 满足 y&mask=y。
二进制
子集
// 降序遍历 mask 的非空子集
for (int sub = mask; sub != 0; sub = (sub - 1) & mask) {
// sub 是 mask 的一个非空子集
}遍历
// 升序遍历 mask 的每一位1
for (int j = 0; j < n; j++) {
if ((s & (1 << j)) != 0) {}
// 更快的升序遍历 mask 的每一位1
for (; mask != 0; mask &= (mask - 1);) {
// 取出最后一位1
int position = mask & (-mask);
// 去掉最后一位1
}多进制
// R 是 radix 进制的简称
int R = 3;
// 遍历R进制mask的所有位
for (int j = 0, dummy = mask, w = 1; j < n; j++, dummy /= R, w *= R) {}
for (int j = 0, dummy = mask, w = 1; dummy > 0; j++, dummy /= R, w *= R) {}
// 遍历R进制mask的所有非零位
for (int dummy = mask, w = 1; dummy > 0; dummy /= R, w *= R) {
if (dummy % R != 0) {}
}排列
优美的排列
状态：f[s]表示用集合s中的i个元素的方案数
转移：f[s]=sum{f[s^(1<<j)]|(j+1)%i!=0 && i%(j+1)!=0}
边界：f[0]=1
答案：sum{f[(1<<n)-1]}
特殊的排列
状态：f[s][i]表示用集合s中的元素生成以num[i]结尾的序列的方案数（状压+状态
转移：f[s][i]=sum{f[s^i][j]}
边界：f[1 << i][i]=1
答案：sum{f[i][(1<<n)-1]}
状态：f[i][s]表示用集合s中的元素生成以num[i]结尾的序列的方案数（状压+状态
转移：f[i][s]=sum{f[j][s^j]}
边界：f[i][0]=1
答案：sum{f[i][((1<<n)-1)^(1<<i)]}
匹配
一对一
2进制，0表示位置没装，1表示位置装了1个
两个数组最小的异或之和
状态：f[s]表示用集合s是nums2的i个元素与nums1的前i位匹配生成的最小异或和
转移：f[s]=min{f[s^j]+nums[i-1]^nums[j]}
边界：f[s]=Inf, f[0]=0
答案：f[(1<<n)-1]
两个数组最小的距离之和
状态：f[s]表示用集合s是nums2的i个元素与nums1的前i位匹配生成的最小距离和
转移：f[s]=min{f[s^j]+abs(nums[i-1]-nums[j])}
边界：f[s]=Inf, f[0]=0
答案：f[(1<<n)-1]
多对多
2进制，0表示位置没装，1表示位置装了1个或多个
连通两组点的最小成本
状态：f[i][s]表示用nums1的前i个元素匹配nums2的集合s的元素的最小成本
转移：f[i][s]=min{min{f[i][s^j],f[i-1][s^j],f[i-1][s]}+cost[i-1][j]}
边界：f[0][s]=Inf, f[0][0]=0
答案：f[n][(1<<n)-1]
多对多（带最大个数限制）
n进制，表示每个位置装的个数，n是最大的对应个数
数组的最大与和
每个篮子可以装0-2个元素，求最大的 元素值与篮子编号的与 和
3进制，表示每个位置装的个数
注意到题目的数据范围并不大，因此我们可以考虑使用状态压缩。可供压缩的有两种，即数和篮子：
最多有 18 个数，每个数被放入篮子或不放入篮子总计 2 种情况，因此状态的数量为 2^18=262144
最多有 9 个篮子，每个篮子可以被放入 0,1,2 个数，总计 3 种情况，因此状态的数量为 3^9 = 196833
第二种压缩方法的状态数量明显较小，因此我们考虑对篮子进行压缩。
状态：f[s]表示用集合s是篮子的元素各位和为i与nums1的前i位匹配生成的最大与和
转移：f[s]=max{f[sub] + (nums[i - 1] & (j + 1))}
边界：f[0]=0
答案：max{f[s]|i==n}
DAG
并行课程II
状态：f[s]表示完成s中的元素至少需要多少学期
转移：f[s]=min{f[s-{k}]}+1
边界：
最小的必要团队
0-1背包+状压DP lc1125.
状态：f[s]表示完成s中的元素至少需要多少学期
转移：
https://leetcode.cn/problems/closest-subsequence-sum/solutions/1369378/by-mountain-ocean-1s0v/
转化为经典哈密顿通路问题，使用状压DP转移
首先，我们要想到把数列转为一张图去做，对于两个数字，如果满足条件（nums[i]%nums[j]==0||nums[j]%nums[i]==0），我们对他们连一条边，那么我们符合条件的一个排列就相当于图上的一个哈密顿通路。