分析

状压的n的范围是（1,20),本质上就是对子集的划分和子集的枚举

一般状压优先考虑dp,dfs记忆化很可能记忆化漏掉,不推荐

状压的时间复杂度分析：

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

该时间复杂度为 3^n

当n = 8 时, 随便枚举

当n = 16 时,时间复杂度为4e7,在lc里java的时间复杂度为1e9,妥妥够用,而py则是4e7,需要做优化

常见位运算:

j&-j 取最低位的1

枚举子集即可

 int n = nums.length, u = 1 << n;
for(int i = 0; i < u ; i++){
   for(int j = 0; j < n ; j++){
     if(((1<<j)&i)==0) continue;
    }
}

时间复杂度O(2^n * n)

1255. 得分最高的单词集合

1601. 最多可达成的换楼请求数目

K次循环和状压

如果出现一个 0 < cnt < 100 和一个 0< n < 16的,考虑这种枚举

//可以考虑预处理

dp[0] = 0;

int n ;//n是被状压的对象

int u = 1<<n;//u是全集

for(int i = 0 ; i < k ; i++){
   for(int j = u - 1;  j > 0 ; j--){//这种是枚举非空真子集,如果涉及到空集合,需要 int j = 0 ; j < u ; j++
       for(int s = j ; s > 0; s = (s-1)&j){//枚举j的子集
         
        }
   }
}

时间复杂度为O(k * 3^n)

通过滚动数组,从j = u - 1 开始枚举可以节约空间

空间复杂度为O(1<<n)

• 题目

2305. 公平分发饼干

1434. 每个人戴不同帽子的方案数 变体,把帽子的枚举变成K

1125. 最小的必要团队 不一样的点在于,不是通过 j^s , j&~s,进行枚举子集

1681. 最小不兼容性

1349. 参加考试的最大学生数

1655. 分配重复整数

1986. 完成任务的最少工作时间段 k = 1的

枚举数组和arr数组匹配

存在俩数组,一个是枚举数组,一个是用于匹配的数组

无需考虑匹配数组的实际是怎么分布的,只需考虑Integer.bitCount(i) 表明它是多少,因为在枚举的过程中会把所有的都会 i - > 匹配数组 匹配一遍

考虑清楚哪个是枚举数组(状压谁)

   int[] arr ;//匹配数组
   int n ;//被状压的对象 
   int u = (1<<n) ;
   int[] dp = new int[u];
   for(int i = 0 ; i < u ; i++){
     int index = Integer.bitCount(i);
     for(int j = 0 ; j < n ; j++){
        if(((1<<j)&i)==0) continue;
        dp[i] = Math.(dp[i],dp[i^(1<<j)] + arr[index-1] and 题目具体的计算);
      }    
   }
    
   return dp[u-1];//有时候答案并非dp[u-1],需要引入一个ans

时间复杂度O(2^n * n) 空间复杂度O(n)

题目

2172. 数组的最大与和

1799. N 次操作后的最大分数和 加一个预处理

1947. 最大兼容性评分和

1879. 两个数组最小的异或值之和

• 折半状压

不是很懂,下次再说

805. 数组的均值分割