核心思想
状压dp 设计一个整型可变参数status，利用status的位信息，来表示： 某个样本是否还能使用，然后利用这个信息进行尝试 写出尝试的递归函数 -> 记忆化搜索 -> 严格位置依赖的动态规划 -> 空间压缩等优化
如果有k个样本，那么表示这些样本的状态，数量是2^k 所以可变参数status的范围： 0 ~ (2^k)-1
样本每增加一个，状态的数量是指数级增长的，所以状压dp能解决的问题往往样本数据量都不大 一般样本数量在20个以内 (10^6)，如果超过这个数量，计算量 (指令条数) 会超过 10^7 ~ 10^8 讲解043 - 根据数据量猜解法的技巧，天字第一号重要技巧
如果样本数量大到状压dp解决不了，或者任何动态规划都不可行，那么双向广搜是一个备选思路
上一节讲述了状压dp的原理和一些经典题目
本节继续状压dp问题，以及重要技巧：如何在位状态上，枚举所有子集的状态（题目3）
例题
1、每个人戴不同帽子的方案数
题目描述： 总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40 。
给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表。
请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。
由于答案可能很大，请返回它对 10^9 + 7 取余后的结果。
示例 1：
输入：hats = [[3,4],[4,5],[5]] 输出：1 解释：给定条件下只有一种方法选择帽子。 第一个人选择帽子 3，第二个人选择帽子 4，最后一个人选择帽子 5。
示例 2：
输入：hats = [[3,5,1],[3,5]] 输出：4 解释：总共有 4 种安排帽子的方法： (3,5)，(5,3)，(1,3) 和 (1,5)
示例 3：
输入：hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]] 输出：24 解释：每个人都可以从编号为 1 到 4 的帽子中选。 (1,2,3,4) 4 个帽子的排列方案数为 24 。
提示：
n == hats.length1 <= n <= 101 <= hats[i].length <= 401 <= hats[i][j] <= 40hats[i]包含一个数字互不相同的整数列表。
解题思路：
状压dp，仔细观察这个题，人的数量相比帽子数量更低，且帽子数量大于20，因此更适合以人的状态来做状压dp
这个题的尝试与以往的01背包很类似，对于一个帽子使用或者不使用，使用时给那个人使用
这个题有一段值得记住的代码，求解位运算的最右位的1-->
cur=num & (-num), 原数去除最右位的1num^cur本题我在第一次写的时候出错
一是使用的是一维dp，忽略了帽子数与人的状态是不相互依赖的关系，应该用二维dp
而是，在每一次对于每顶帽子可以给那些人使用的时候，我直接拿的帽子与人的转换数组进行操作，导致进入后续的递归中这个数组很多元素为0，应该用一个局部变量进行尝试的
代码如下：
package main.java.class081;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code01_NumberOfWaysWearDifferentHats
* @description: 每个人戴不同帽子的方案数
* // 总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40
* // 给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表
* // 请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数
* // 由于答案可能很大，答案对 1000000007 取模
* // 测试链接 : https://leetcode.cn/problems/number-of-ways-to-wear-different-hats-to-each-other
* @author: zs宝
* @create: 2025-09-30 09:08
* @Version 1.0
**/public class Code01_NumberOfWaysWearDifferentHats {
class Solution {
public static int MOD=1000000007;
public static int numberWays(List<List<Integer>> hats) {
return numberWays1(hats);
}
public static int numberWays1(List<List<Integer>> arr) {
int n=arr.size();
int m=0;
//开始计算帽子的最大序号
for(List<Integer>hats:arr){
for(int hat:hats){
m=Math.max(m,hat);
}
}
//计算每顶帽子有哪些人可带，下标为帽子
int []hats=new int[m+1];
for(int i=0;i<n;i++){
for(int hat:arr.get(i)){
hats[hat]|=(1<<i);
}
}
int[][]dp=new int[m+1][1<<n];
for(int i=0;i<=m;i++){
Arrays.fill(dp[i],-1);
}
return f1(m,n,1,0,dp,hats);
}
//i:第几顶帽子
//status：当前人戴帽子的状况，0未戴帽子，1戴过帽子
//hats_people:每顶帽子对应那些人
public static int f1(int m,int n,int i,int status,int[][]dp,int[]hats_people){
if(status==(1<<n)-1){
return 1;
}
//还有人没满足，但是帽子已经用光
if(i==m+1){
return 0;
}
if(dp[i][status]!=-1){
return dp[i][status];
}
//不用第i顶帽子
int ans=f1(m,n,i+1,status,dp,hats_people);
//接下来考虑用第i顶帽子的情况
int cur;
int hats=hats_people[i];
while(hats!=0){
//得到最右的1：拿到如 00001000 cur=hats &(-hats);
if((status & cur)==0){
ans=(ans+f1(m,n,i+1,status|cur,dp,hats_people))%MOD;
}
//去掉最右侧的1
hats^=cur;
}
dp[i][status]=ans;
return ans;
}
}
}2、好子集的数目
题目描述： 给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积，那么我们称它为 好子集 。
比方说，如果
nums = [1, 2, 3, 4]：[2, 3]，[1, 2, 3]和[1, 3]是 好 子集，乘积分别为6 = 2*3，6 = 2*3和3 = 3。[1, 4]和[4]不是 好 子集，因为乘积分别为4 = 2*2和4 = 2*2。
请你返回 nums 中不同的 好 子集的数目对 109 + 7 取余 的结果。
nums 中的 子集 是通过删除 nums 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。
示例 1：
输入：nums = [1,2,3,4] 输出：6 解释：好子集为：
[1,2]：乘积为 2 ，可以表示为质数 2 的乘积。
[1,2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
[1,3]：乘积为 3 ，可以表示为质数 3 的乘积。
[2]：乘积为 2 ，可以表示为质数 2 的乘积。
[2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
[3]：乘积为 3 ，可以表示为质数 3 的乘积。
示例 2：
输入：nums = [4,2,3,15] 输出：5 解释：好子集为：
[2]：乘积为 2 ，可以表示为质数 2 的乘积。
[2,3]：乘积为 6 ，可以表示为互不相同质数 2 和 3 的乘积。
[2,15]：乘积为 30 ，可以表示为互不相同质数 2，3 和 5 的乘积。
[3]：乘积为 3 ，可以表示为质数 3 的乘积。
[15]：乘积为 15 ，可以表示为互不相同质数 3 和 5 的乘积。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 30
解题思路：
换个想法，既然要求子数组累乘积可以质因数分解，且每个质因数只能出现一次
而题目给的的数据范围子啊1-30以内，其中的质因数只有10个，
那么要质因数分解，每个质因数只出现那一次，那么30以内的质因数只出现一次的组合状况有多少种是可以算出来的，1<<10
因此这里求符合条件的子数组个数，可以转为求解每种质因数只出现一次的组合状况的数组个数
每种质因数只出现一次的组合status的数组如何判定呢？
数组也只能含有质因数，且其中的质因数要包含在status中，即status中的位运算1包含质因数的位运算1
代码如下：
package main.java.class081;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code03_TheNumberOfGoodSubsets
* @description: 好子集的数目
* // 给你一个整数数组 nums，好子集的定义如下：
* // nums的某个子集，所有元素的乘积可以表示为一个或多个互不相同质数的乘积
* // 比如nums = [1, 2, 3, 4]
* // [2, 3]，[1, 2, 3]，[1, 3] 是好子集
* // 乘积分别为6=2*3，6=2*3，3=3
* // [1, 4]和[4]不是好子集，因为乘积分别为4=2*2和4=2*2
* // 返回nums中不同的好子集的数目，答案对 1000000007 取模
* // 如果两个子集删除的下标不同，那么它们被视为不同的子集
* // 测试链接 : https://leetcode.cn/problems/the-number-of-good-subsets/
* @author: zs宝
* @create: 2025-09-30 10:17
* @Version 1.0
**/public class Code03_TheNumberOfGoodSubsets {
class Solution {
//由于数字的范围是1-30，质数因子只有10个，那么纯粹有质数因子组成的子数组和的状态有Limit个
public static int Limit=(1<<10);
public static int MAXV=30;
public static int MOD=1000000007;
// 打个表来加速判断
// 如果一个数字拥有某一种质数因子不只1个
// 那么认为这个数字无效，状态全是0，0b0000000000
// 如果一个数字拥有任何一种质数因子都不超过1个
// 那么认为这个数字有效，用位信息表示这个数字拥有质数因子的状态
// 比如12，拥有2这种质数因子不只1个，所以无效，用0b0000000000表示
// 比如14，拥有2这种质数因子不超过1个，拥有7这种质数因子不超过1个，有效
// 从高位到低位依次表示：...13 11 7 5 3 2
// 所以用0b0000001001表示14拥有质数因子的状态
// 质数: 29 23 19 17 13 11 7 5 3 2
// 位置: 9 8 7 6 5 4 3 2 1 0
public static int[] own = { 0b0000000000, // 0
0b0000000000, // 1
0b0000000001, // 2
0b0000000010, // 3
0b0000000000, // 4
0b0000000100, // 5
0b0000000011, // 6
0b0000001000, // 7
0b0000000000, // 8
0b0000000000, // 9
0b0000000101, // 10
0b0000010000, // 11
0b0000000000, // 12
0b0000100000, // 13
0b0000001001, // 14
0b0000000110, // 15
0b0000000000, // 16
0b0001000000, // 17
0b0000000000, // 18
0b0010000000, // 19
0b0000000000, // 20
0b0000001010, // 21
0b0000010001, // 22
0b0100000000, // 23
0b0000000000, // 24
0b0000000000, // 25
0b0000100001, // 26
0b0000000000, // 27
0b0000000000, // 28
0b1000000000, // 29
0b0000000111 // 30
};
public int numberOfGoodSubsets(int[] nums) {
//1-30的数字的个数
int[]cnt=new int[MAXV+1];
for(int num:nums){
cnt[num]++;
}
int [][]dp=new int[MAXV+1][Limit];
for(int i=0;i<=MAXV;i++){
Arrays.fill(dp[i],-1);
}
//这里我们转化一下
//原题目是想要求nums 中不同的 好 子集的数目
//我们根据好子集的定义，将其转化为
//求解所有质数状态组合的集合数量
int ans=0;
for(int s=1;s<Limit;s++){
ans=(ans+f(MAXV,s,cnt,dp))%MOD;
}
return ans;
}
/**
在1-i的数字范围内要求能够达到status状态的数组有哪些
就是1-i数字范围组成的数组的乘积，这个乘积的质数分解状态为status中的质数
*/
public static int f(int i,int status,int[]cnt,int[][]dp){
if(dp[i][status]!=-1){
return dp[i][status];
}
int ans=0;
//所有数字已经用完
if(i==1){
if(status==0){
ans=1;
for(int j=0;j<cnt[1];j++){
ans=(ans<<1)%MOD;
}
}
}else{
//数字还未用完
//不用当前数字
ans=f(i-1,status,cnt,dp);
//用当前数字
int cur=own[i];
int times=cnt[i];
//判断当前数字是否可用
//现实cur是质数且给的数组中有这个数，并且这个数有status中要的质数状态
if(cur!=0 && times!=0 && (status & cur)==cur){
ans=(int)((ans+(long)f(i-1,status^cur,cnt,dp)*times)%MOD);
}
}
dp[i][status]=ans;
return ans;
}
}
}3、分配重复整数
题目描述： 给你一个长度为 n 的整数数组 nums ，这个数组中至多有 50 个不同的值。同时你有 m 个顾客的订单 quantity ，其中，整数 quantity[i] 是第 i 位顾客订单的数目。请你判断是否能将 nums 中的整数分配给这些顾客，且满足：
第
i位顾客 恰好 有quantity[i]个整数。第
i位顾客拿到的整数都是 相同的 。每位顾客都满足上述两个要求。
如果你可以分配 nums 中的整数满足上面的要求，那么请返回 true ，否则返回 false 。
示例 1：
输入：nums = [1,2,3,4], quantity = [2] 输出：false 解释：第 0 位顾客没办法得到两个相同的整数。
示例 2：
输入：nums = [1,2,3,3], quantity = [2] 输出：true 解释：第 0 位顾客得到 [3,3] 。整数 [1,2] 都没有被使用。
示例 3：
输入：nums = [1,1,2,2], quantity = [2,2] 输出：true 解释：第 0 位顾客得到 [1,1] ，第 1 位顾客得到 [2,2] 。
提示：
n == nums.length1 <= n <= 1051 <= nums[i] <= 1000m == quantity.length1 <= m <= 101 <= quantity[i] <= 105nums中至多有50个不同的数字。
解题思路
这道题容易用贪心的思路去解决，但是贪心的思路就很容易一个数值的个数解决一个人的需求，忽略一种数值的个数可以解决多个人的需求（自己写的最后几个测试用例就错在这里）
那么这里就考虑一个数值解决多种需求的可能
就有一个问题，多个人的需求组合起来要多少个数的相同数值，如下代码
for(int i=0,v,h;i<m;i++){
v=quantity[i];
h=1<<i;
//所有比h小的状态和h状态组合
for(int k=0;k<h;k++){
sum[h|k]=sum[k]+v;
}
} 而后在后续递归调用的时候，如何判定当前数值的个数可以解决那些人的雪球组合，这里就需要我们依次遍历当前状态的所有子集，如1111100的子集1100100这种，代码如下，需牢牢记住
for(int j=status;j>0;j=(status & (j-1))){
if(sum[j]<=k && f(cnts,sum,i+1,status^j,dp)){
ans=true;
break;
}
}代码如下：
package main.java.class081;
import java.util.Arrays;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code04_DistributeRepeatingIntegers
* @description: 分配重复整数
* // 给你一个长度为n的整数数组nums，这个数组中至多有50个不同的值
* // 同时你有m个顾客的订单quantity，其中整数quantity[i]是第i位顾客订单的数目
* // 请你判断是否能将nums中的整数分配给这些顾客，且满足：
* // 第i位顾客恰好有quantity[i]个整数、第i位顾客拿到的整数都是相同的
* // 每位顾客都要满足上述两个要求，返回是否能都满足
* // 测试链接 : https://leetcode.cn/problems/distribute-repeating-integers/
* @author: zs宝
* @create: 2025-09-30 13:44
* @Version 1.0
**/public class Code04_DistributeRepeatingIntegers {
class Solution {
public boolean canDistribute(int[] nums, int[] quantity) {
Arrays.sort(nums);
//统计有多少种数值
int n=1;
for(int i=1;i<nums.length;i++){
if(nums[i]!=nums[i-1]){
n++;
}
}
//统计每种数值的个数
int[]cnts=new int[n];
int indx=0;
int j=0;
while(j<nums.length){
int cur=nums[j];
int len=0;
while(j<nums.length && nums[j]==cur){
len++;
j++;
}
cnts[indx++]=len;
}
//枚举生成quanlity中的每个子集需要的数字个数
int m=quantity.length;
int[]sum=new int[1<<m];
for(int i=0,v,h;i<m;i++){
v=quantity[i];
h=1<<i;
//所有比h小的状态和h状态组合
for(int k=0;k<h;k++){
sum[h|k]=sum[k]+v;
}
}
int[][]dp=new int[n][1<<m];
return f(cnts,sum,0,(1<<m)-1,dp);
}
public boolean f(int[]cnts,int[] sum,int i,int status,int[][]dp){
if(status==0){
return true;
}
if(i==cnts.length){
return false;
}
if(dp[i][status]!=0){
return dp[i][status]==1;
}
boolean ans=false;
//当前位置的数值个数
int k=cnts[i];
//开始判定当前数值可以解决那些sum需求组合
//当前位运算如11111的子集
for(int j=status;j>0;j=(status & (j-1))){
if(sum[j]<=k && f(cnts,sum,i+1,status^j,dp)){
ans=true;
break;
}
}
//当前i位置的数值个数无论如何都解决不了
if(!ans){
//则不考虑当前位置数值
ans=f(cnts,sum,i+1,status,dp);
}
dp[i][status]=ans?1:-1;
return ans;
}
}
}