【算法日记】Day 21 动态规划专题——状态压缩DP（四）

Abstract#动态规划#状压DP#位运算#Brian Kernighan算法1. 题目题目LeetCode 1434. 每个人带不同帽子的方案数核心思路帽子数量最多40远大于人数最多10故以帽子为阶段状压表示人的分配情况。定义dp[i][status]表示考虑了前i种帽子当前已分配的人集合为status的方案数。对于第i种帽子可以选择不分配给任何人或分配给喜欢该帽子且尚未分配的人用status的二进制位表示人。使用记忆化搜索转移时枚举该帽子对应的喜欢者集合中的每个人即可。复杂度时间复杂度O ( m × 2 n × n ) O(m\times2^n\times n)O(m×2n×n)空间复杂度O ( m × 2 n ) O(m\ \times 2^n)O(m×2n)。2. 代码constintMOD1000000007;classSolution{public:intf(vectorintliked,intn,intm,inti,intstatus,vectorvectorintdp){if(status(1n)-1)return1;if(im1)return0;if(dp[i][status]!-1)returndp[i][status];intcurliked[i],rightone,ansf(liked,n,m,i1,status,dp);while(cur!0){rightonecur-cur;if((statusrightone)0)ans(ansf(liked,n,m,i1,status|rightone,dp))%MOD;cur^rightone;}dp[i][status]ans;returnans;}intnumberWays(vectorvectorinthats){intnhats.size(),m-1;vectorintliked(41,0);for(inti0;in;i){for(intj0;jhats[i].size();j){liked[hats[i][j]]|(1i);mmax(m,hats[i][j]);}}vectorvectorintdp(m1,vectorint((1n),-1));returnf(liked,n,m,1,0,dp);}};3. 心得状态选择我做题时先考虑用40顶帽子被选的情况来表示状态但很快发现帽子数量过多2 40 2^{40}240明显超出类型范围所以我转而考虑了用数量上限更小的人来标注状态。尽管后面没有想出状态应该结合帽子阶段1~40转移但至少状态选择的直觉正确。信息转存既然已经选择了将人的状态压缩那么对于已知的每个人喜欢哪几顶帽子的信息也就可以反过来给每顶帽子设置一个“被喜欢”状态存储人的信息后续转移到任何一顶帽子时都能够利用被压缩的“被喜欢”状态迅速判断。子集枚举技巧——Brian Kernighan算法使用一个小算法可以高效遍历cur的所有1位无需逐位检查是否为零while(cur){intlowbitcur-cur;cur^lowbit;}4. 相关题目LeetCode 1994. 好子集的数目