枚举一个集合(通过二进制标记的集合)的所有的二进制子集
方式一
for(int i=1;i<m;i++){
//对于i的所有的二进制子集
for(int j=i;j>=0;j=(j-1)&i){
// j即是i的所有的二进制子集
}
}
对应的剪枝策略,
(1)如果计算的时候需要计算对应的补集 j^i 对应的子集可以不需要枚举i 如果j=i 补集i^i==0无意义
(2)对于j的补集最高位为1,对应的补集最高位为0 所以将i右移一位 int split=i>>1;
for(int i=1;i<m;i++){
int split=i>>1;
for(int j=(i-1)&i;j>split;j=(j-1)&i){
//对于二进制子集j进行计算
}
}
方式二
for(int i=1;i<m;i++){
for(int j=0;j<i;j++){
if((i|j)==i){
// j即是i的所有的二进制真子集
}
}
}
如果j是i的一个二进制子集,对应的补集为j^i j^i^j==i
两个不相交的回文子序列的最大长度乘积
public int maxProduct(String s){
//如果对应的子集是回文串,取max
int n=s.length();int m=(1<<n);
int[] count=new int[m];
for(int i=1;i<m;i++){
//判断该字符串是否是回文串
if(check(s,i)){
//保存该回文串
count[i]=Integer.bitCount(i);
}
}
int res=0;
for(int i=1;i<m;i++){
//对于所有的子集
int split=i>>1;
for(int j=(i-1)&i;j>split;j=(j-1)&i){
res=Math.max(res,count[j]*count[i^j]);
}
}
return res;
}
public boolean check(String s,int state){
int left=0;int right=s.length()-1;//判断是否是回文串,双指针
while(left<right){
while(left<right&&(state>>left&1)==0){
left++;
}
while(left<right&&(state>>right&1)==0){
right--;
}
if(s.charAt(left)!=s.charAt(right)){
return false;
}
left++;right--;
}
return true;
}
方式二,直接暴力枚举
将所有的回文子序列存储
public int maxProduct(String s){
//将所有的回文字符串存储
List<int[]> nums=new ArrayList<int[]>();
int n=s.length();int m=(1<<n);
for(int i=1;i<m;i++){
if(check(s,i)){
nums.add(new int[]{i,Integer.bitCount(i)});
}
}
int res=0;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
int x=nums.get(i)[0];int y=nums.get(i)[1];
int z=nums.get(j)[0];int w=nums.get(j)[1];
if((x&z)==0){
res=Math.max(res,y*w);
}
}
}
return res;
}
public boolean check(String s,int state){
int left=0;int right=s.length()-1;
while(left<right){
while(left<right&&((state>>left)&1)==0){
left++;
}
while(left<right&&(state>>right&1)==0){
right--;
}
if(s.charAt(left)!=s.charAt(right)){
return false;
}
left++;right--;
}
return true;
}
完成任务的最少工作时段
class Solution {
public int minSessions(int[] tasks,int sessionTime){
//对于所有的一个时间段完成的任务状态
int n = tasks.length, m = 1 << n;
int[] dp = new int[m];
Arrays.fill(dp, 20);
for(int i=1;i<m;i++){
//对于状态i需要的时间
int time=0;int pos=n-1;
int state=i;
while(state!=0){
if((state&1)==1){
time+=tasks[pos];
}
pos--;
state>>=1;
}
if(time<=sessionTime){
dp[i]=1;//一个时间段
}
}
for(int i=1;i<m;i++){
if(dp[i]==1){
continue;
}
for(int j=i;j>0;j=(j-1)&i){
dp[i]=Math.min(dp[i],dp[j]+dp[i^j]);
}
}
return dp[m-1];
}
}
最小不兼容性
最小不兼容性
先预处理所有的满足分配的子集,分配数量为n/k,并且所有的相等元素只分配一个集合一次,所有不满足的状态初始化-1
状态转移,所有的元素个数为 可以整除n/k
class Solution {
public int minimumIncompatibility(int[] nums, int k) {
//对数组nums进行状态枚举
int n=nums.length;
int[] value=new int[1<<n];
//初始化,所有的不合法值为-1
Arrays.fill(value,-1);
//统计频率
int[] freq=new int[n+1];
for(int i=0;i<(1<<n);i++){
//所有元素个数为n/k的子集进行统计不兼容分数
if(Integer.bitCount(i)==n/k){
//每一个子集元素个数满足
//元素个数是否相等
for(int j=0;j<n;j++){
if((i&(1<<j))!=0){
freq[nums[j]]++;
}
}
boolean flag=true;
for(int j=1;j<=n;j++){
if(freq[j]>1){
flag=false;
break;
}
}
if(flag){
//计算不兼容分数
int maxv=Integer.MIN_VALUE;int minv=Integer.MAX_VALUE;
for(int j=1;j<=n;j++){
if(freq[j]>0){
maxv=Math.max(maxv,j);
minv=Math.min(minv,j);
}
}
value[i]=maxv-minv;
}
//将数组清空
Arrays.fill(freq,0);
}
}
int[] dp=new int[1<<n];
//将所有元素置为-1
Arrays.fill(dp,-1);
dp[0]=0;
for(int i=0;i<(1<<n);i++){
if (Integer.bitCount(i) % (n / k) == 0) {
//该状态所有的子集
for(int j=i;j>0;j=(j-1)&i){
//如果子集是长度为n/k子集
if(value[j]!=-1&&dp[i^j]!=-1){
if(dp[i]==-1){
dp[i]=dp[i^j]+value[j];
}else{
dp[i]=Math.min(dp[i],dp[i^j]+value[j]);
}
}
}
}
}
return dp[(1<<n)-1];
}
}
分配重复整数
分配重复整数
定义dp[n][1<<m]:dp[i][j]:表示前i个元素满足状态为j的分配方式
class Solution {
public boolean canDistribute(int[] nums,int[] quantity){
//每一个元素出现次数
Map<Integer,Integer> cnt=new HashMap<Integer,Integer>();
for (int num : nums) {
cnt.put(num,cnt.getOrDefault(num,0)+1);
}
Set<Integer> keys=cnt.keySet();
int[] count=new int[keys.size()];
int index=0;
for (Integer key : keys) {
int value=cnt.get(key);
count[index++]=value;
}
int n=count.length;int m=quantity.length;
//定义dp[n][m]
boolean[][] dp=new boolean[n][1<<m];
//预处理
int[] sum=new int[1<<m];
for(int i=0;i<(1<<m);i++){
//通过递推方式进行预处理
for(int j=0;j<m;j++){
if((i&(1<<j))!=0){
//对应的位为1
sum[i]=sum[i-(1<<j)]+quantity[j];
break;
}
}
}
//初始化
for(int i=0;i<n;i++){
//满足0个元素分配,true
dp[i][0]=true;
}
//转移
for(int i=0;i<n;i++){
//对于每一种状态
for(int j=0;j<(1<<m);j++){
if(i>0&&dp[i-1][j]){//表示第i个数不选,下面表示第i个元素选择,所以子集不需要枚举0 s>0
dp[i][j]=true;
continue;
}
//转移方式:对于第i个元素满足的人的自己进行枚举
//第i个数满足自己s对应的人
for(int s=j;s>0;s=(s-1)&j){
//前i-1个元素满足人对应的状态
int prev=j-s;
boolean last=i==0? prev==0:dp[i-1][prev];
//当前第i个元素满足状态s,可以预处理需要的最少人数
boolean cur=sum[s]<=count[i];
if(last&&cur){
dp[i][j]=true;//有一种方式满足,则可以满足分配
break;
}
}
}
}
return dp[n-1][(1<<m)-1];
}
}
完成所有工作的最少时间
完成所有工作最少时间
定义dp[i][j]:标识给前i个人分配任务,分配的任务对应的为j 所有最大时间的最小值
二进制枚举分配的任务
class Solution {
public int minimumTimeRequired(int[] jobs, int k) {
//通过状态压缩标识分配的工作
int n=jobs.length;
int[][] dp=new int[k+1][(1<<n)];
for(int i=0;i<=k;i++){
Arrays.fill(dp[i],Integer.MAX_VALUE);
}
//预处理
int[] sum=new int[1<<n];
for(int i=0;i<(1<<n);i++){
int res=0;
for(int j=0;j<n;j++){
if(((i>>j)&1)==1){
res+=jobs[n-1-j];
}
}
sum[i]=res;
}
for(int i=0;i<(1<<n);i++){
dp[1][i]=sum[i];
}
for(int i=1;i<=k;i++){
for(int j=0;j<(1<<n);j++){
//对于j进行二进制枚举
for(int s=j;s>0;s=(s-1)&j){
dp[i][j]=Math.min(dp[i][j],Math.max(dp[i-1][j^s],sum[s]));//sum[s]标识将s工作分配给第i个人
}
}
}
return dp[k][(1<<n)-1];
}
}
方法二:回溯二分
public int minimumTimeRequired(int[] jobs, int k) {
//先分配更大的任务
Arrays.sort(jobs);
//从大到小排序
int n=jobs.length;
int left=0;int right=n-1;
while (left < right) {
swap(jobs,left,right);
left++;right--;
}
//二分答案
int sum=0;
for(int i=0;i<n;i++){sum+=jobs[i];}
int l=jobs[0];int r=sum;
while (l < r) {
int mid=l+r>>1;
int[] loads=new int[k];
if(check(jobs,loads,0,mid)){
r=mid;
}else{
l=mid+1;
}
}
return l;
}
public boolean check(int[] jobs,int[] loads,int start,int mid){
if (start >= jobs.length) {
return true;
}
//对第start个任务进行分配
int cur=jobs[start];
for(int i=0;i<loads.length;i++){
if(loads[i]+cur<=mid){
loads[i]+=cur;
if(check(jobs, loads, start+1, mid)){
return true;
}
loads[i]-=cur;
}
//如果当前工人没有分配工作,分配给任何一个人都是一样的
if (loads[i] == 0 || loads[i] + cur == mid) {
break;
}
}
return false;
}
public void swap(int[] nums,int i,int j){
int t=nums[i];
nums[i]=nums[j];
nums[j]=t;
}
联通两组点的最小成本
联通两组点的最小成本
对点数比较小的一组进行状态压缩,枚举点数比较多的
对于每一种状态,当前枚举第i个点,有两种转移的方式
(1)集合二中未选点的子集
(2)集合二中已选点最多一个
class Solution {
public int connectTwoGroups(List<List<Integer>> cost){
int n=cost.size();
int m=cost.get(0).size();
int[][] dp=new int[n+1][1<<m];
//初始化
for(int i=0;i<=n;i++){
Arrays.fill(dp[i],-1);
}
dp[0][0]=0;
int state=1<<m;
for(int i=1;i<=n;i++){
for(int j=0;j<state;j++){
if (dp[i-1][j] == -1) {
continue;
}
int s=(~j)&(state-1);
for(int k=s;k>0;k=(k-1)&s){
int cur=0;
for(int t=0;t<m;t++){
if(((k>>t)&1)==1){
cur+=cost.get(i-1).get(t);
}
}
//新状态
int next=j|k;
if(dp[i][next]==-1||dp[i][next]>dp[i-1][j]+cur){
dp[i][next]=dp[i-1][j]+cur;
}
}
for(int t=0;t<m;t++){
// if(((j>>t)&1)==1){
int next=j|(1<<t);
int cur=dp[i-1][j]+cost.get(i-1).get(t);
if(dp[i][next]==-1||dp[i][next]>cur){
dp[i][next]=cur;
}
// }
}
}
}
return dp[n][(1<<m)-1];
}
}
数组的最大与和
数组最大与和
通过三进制进行状态压缩,每一位表示对应的桶元素个数,约定元素个数与数组nums一一对应
class Solution {
public int maximumANDSum(int[] nums,int numSlots){
int state=1;
for(int i=0;i<numSlots;i++){
state*=3;
}
int n=nums.length;
int[] dp=new int[state];
for(int i=1;i<state;i++){
int cnt=0;//对于每一种状态,统计已经放的个数
int dummy=i;
while(dummy!=0){
cnt+=dummy%3;
dummy/=3;
}
if(cnt>n){
continue;
}
for(int j=0,s=i,weight=1;j<numSlots;j++,s/=3,weight*=3){
if(s%3!=0){
dp[i]=Math.max(dp[i],dp[i-weight]+(nums[cnt-1]&(numSlots-j)));
}
}
}
int res=Integer.MIN_VALUE;
for(int i=0;i<state;i++){
res=Math.max(res,dp[i]);
}
return res;
}
}
访问所有节点最短路径
访问所有节点最短路径
所有的节点可以重复到达,不能通过dp,通过最短路径BFS(权值为1)进行状态更新与转移
class Solution {
public int shortestPathLength(int[][] graph) {
//通过BFS进行状态转移
int n=graph.length;
int[][] dp=new int[1<<n][n];//dp[i][j]表示对于状态i,当前在点j最短路径
//初始化
Queue<int[]> queue=new LinkedList<int[]>();
//起点
for(int i=0;i<(1<<n);i++){
Arrays.fill(dp[i],Integer.MAX_VALUE);
}
for(int i=0;i<n;i++){
dp[1<<i][i]=0;
queue.offer(new int[]{1<<i,i});
}
while (!queue.isEmpty()) {
int[] node=queue.poll();
for (int i : graph[node[1]]) {
//将相邻节点加入状态
int next=node[0]|(1<<i);
if(dp[next][i]>dp[node[0]][node[1]]+1){
dp[next][i]=dp[node[0]][node[1]]+1;
//新节点加入队列
queue.offer(new int[]{next,i});
}
}
}
//所有最短路径
int res=Integer.MAX_VALUE;
for(int i=0;i<n;i++){
res=Math.min(res,dp[(1<<n)-1][i]);
}
return res;
}
}
最小的必要团队
class Solution {
public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
//将所有的技能编号
int id=0;
Map<String,Integer> skillToIndex=new HashMap<String,Integer>();
for (String req_skill : req_skills) {
if(!skillToIndex.containsKey(req_skill)){
skillToIndex.put(req_skill,id++);
}
}
int n=people.size();
int[] peo=new int[n];
for(int i=0;i<n;i++){
for(int j=0;j<people.get(i).size();j++){
String skill=people.get(i).get(j);
int skill_id=skillToIndex.get(skill);
peo[i]|=(1<<skill_id);
}
}
//定义状态转移
int[] dp=new int[1<<id];
Arrays.fill(dp,0x3f3f3f);
Map<Integer,int[]> map=new HashMap<Integer,int[]>();
dp[0]=0;
map.put(0,new int[]{-1,-1});
//对于每一个人
for(int i=0;i<n;i++){
for(int j=(1<<id)-1;j>=0;j--){
int next=j|peo[i];
if(dp[next]>dp[j]+1){
dp[next]=dp[j]+1;
//将转移过程保存
map.put(next,new int[]{i,j});
}
}
}
List<Integer> res=new ArrayList<Integer>();
for(int i=(1<<id)-1;i>0;i=map.get(i)[1]){
res.add(map.get(i)[0]);
}
int[] re=new int[res.size()];
for(int i=0;i<res.size();i++){
re[i]=res.get(i);
}
return re;
}
}
N次操作后的最大分数
class Solution {
public int maxScore(int[] nums) {
//定义状压
int n=nums.length;
int[][] dp=new int[n/2+2][1<<n];//dp[i][j]表示第i次操作,状态为j
// for(int i=0;i<n/2+2;i++){
// Arrays.fill(dp[i],-0x3f3f3f);
// }//所有操作初始化为0
for(int i=1;i<=n/2;i++){
for(int j=0;j<(1<<n);j++){
//对于可以选择两位
for(int k=0;k<n-1;k++){
if(((j>>k)&1)==1){
continue;
}
for(int w=k+1;w<n;w++){
if(((j>>w)&1)==1){
continue;
}
dp[i][j|(1<<k)|(1<<w)]=Math.max(dp[i][j|(1<<k)|(1<<w)],dp[i-1][j]+(i)*gcd(nums[k],nums[w]));
}
}
}
}
int res=Integer.MIN_VALUE;
for(int i=0;i<(1<<n);i++){
res=Math.max(res,dp[n/2][i]);
}
return res;
}
public int gcd(int a,int b){
if(a<b){
return gcd(b,a);
}
return a%b==0? b:gcd(b,a%b);
}
}
每个人戴不同帽子的方案
每个人戴不同帽子方案
对于分配帽子的人进行状态压缩,对于所有的帽子进行分配 最后结果为dp[maxHats][(1<<n)-1]
对于每一个改变状态的帽子有两种选择转移
(1)第i个帽子不进行分配dp[i][j]只能通过dp[i-1][j]进行转移
(2)如果第i个帽子进行分配,只能从dp[i-1][j^(1<<person)]没有分配的情况转移
public int numberWays(List<List<Integer>> hats){
int MOD=1000000007;
//对人进行状态压缩
int n=hats.size();
//对于所有人喜爱的帽子进行分配
int maxHats=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
for(int j=0;j<hats.get(i).size();j++){
maxHats=Math.max(maxHats,hats.get(i).get(j));
}
}
List<List<Integer>> hatToPerson=new ArrayList<List<Integer>>();
for(int i=0;i<=maxHats;i++){
hatToPerson.add(new ArrayList<>());
}
for(int i=0;i<n;i++){
for(int j=0;j<hats.get(i).size();j++){
int hat=hats.get(i).get(j);
hatToPerson.get(hat).add(i);
}
}
//定义dp数组
int[][] dp=new int[maxHats+1][1<<n];
dp[0][0]=1;
for(int i=1;i<=maxHats;i++){
for(int j=0;j<(1<<n);j++){
//如果当前i帽子不进行分配
dp[i][j]=dp[i-1][j];//表示前i个帽子分配状态与前i-1帽子分配状态一致
//如果帽子i进行分配,一定是分配给喜欢的人
//对于所有的喜欢的人
for(int k=0;k<hatToPerson.get(i).size();k++){
int person=hatToPerson.get(i).get(k);
// if((j&(1<<person))!=0){//对于第person个人已经分配,如果当前帽子i是分配给person人
if(((j>>person)&1)==1){
dp[i][j]+=dp[i-1][j^(1<<person)];
dp[i][j]%=MOD;
}
}
}
}
return dp[maxHats][(1<<n)-1];
}
参加考试的最大学生数
class Solution {
public int maxStudents(char[][] seats){
int n=seats.length;int m=seats[0].length;
int[][] dp=new int[n+1][1<<m];
for(int i=1;i<=n;i++){
//初始状态
int start=0;
for(int j=0;j<m;j++){
if(seats[i-1][j]=='#'){
start|=(1<<j);
}
}
//每一种状态
for(int j=0;j<(1<<m);j++){
int next=j<<1;
if((start&j)!=0||(next&j)!=0){
dp[i][j]=-1;
continue;
}
//上一行的合法状态
int prev=(j>>1);
for(int s=0;s<(1<<m);s++){
if(dp[i-1][s]==-1){
continue;
}
if((next&s)!=0||(prev&s)!=0){
continue;
}
dp[i][j]=Math.max(dp[i][j],dp[i-1][s]+Integer.bitCount(j));
}
}
}
//所有的行
int res=0;
for(int j=0;j<(1<<m);j++){
res=Math.max(res,dp[n][j]);
}
return res;
}
}