当前位置：首页 > news >正文

数据结构与算法：状压dp

news 来源：原创 2025/7/2 3:53:25

前言

状压dp在整个动态规划专题里特别重要，用位信息表示元素的思想更是重中之重。

一、状态压缩

1.内容

对于一些带路径的递归，通常来讲没法改记忆化搜索和严格位置依赖的动态规划。但如果这个路径的数据量在一定范围内，就可以考虑使用一个整数status的位信息0和1来存路径。

2.限制

因为是用位信息存路径，所以当有k个元素时，所使用的这个整数的范围就是0~2^k。而当k=20时数据量就已经达到10^6了，所以一般只有当元素数量在20个以内才能考虑使用状态压缩。

3.技巧

当元素个数超出限制时，一般的状压是过不了的，这时候就要考虑使用双向广搜了，具体内容在数据结构与算法：双向广搜里。

二、题目

1.我能赢吗

会赢吗？

class Solution {
public:bool canIWin(int n, int sum) {//特例if(sum==0){return true;}if(n*(n+1)/2<sum)//加起来都不到sum -> 没人赢{return false;}//0：没算过//1：true//-1：falsevector<int>dp(1<<(n+1));return MS((1<<(n+1))-1,sum,n,dp);}//记忆化搜索//轮到当前玩家选择//status第0位不用！！//rest其实由status决定bool MS(int status,int rest,int n,vector<int>&dp){if(rest<=0)//到自己时累加和超了 -> 自己输{return false;}if(dp[status]!=0){return dp[status]==1;}bool ans=false;for(int i=1;i<=n;i++){if((status>>i)&1==1&&!MS(status^(1<<i),rest-i,n,dp))//能选且能让下一个人输{ans=true;break;//有一个是true即可}}dp[status]=ans?1:-1;return ans;}
};

首先观察数据范围，可以发现最多就20个数。又因为不能重复选，所以之前的决策会影响对后续决策，是带路径的递归，那就考虑对使用状态压缩进行dp。

方法就是，用一个status存位信息。这里由于可选的数是从1开始，所以status的第0位可以不用。初始时status所有位全是1表示全都可选，即1左移n+1位后减1。之后递归还需要带着一个rest记累加和离sum还剩多少，注意，虽然这里有status和rest两个可变参数，但rest其实是由status决定的，所以其实是一个一维动态规划，dp表就是一个一维数组。对于dp表，可以设置0为没来过，1和-1分别表示true和false。

之后，对于递归函数的定义就是轮到当前的人时是否能赢。若此时rest已经小于等于0了，那就直接输了。否则就枚举所有数字1到n，若没选过，即status该位为1，且这么选能让下个人输，那就说明自己能赢。而又因为有一种情况即可，所以直接break返回即可。

注意特例，若sum为0就返回true，若所有数加起来都不到sum就返回false。

2.火柴拼正方形

class Solution {
public:bool makesquare(vector<int>& matchsticks) {int sum=0;for(int num:matchsticks){sum+=num;}if(sum%4!=0)//特例：不能被四整除根本拼不了{return false;}int n=matchsticks.size();vector<int>dp(1<<n);return MS((1<<n)-1,sum/4,0,4,matchsticks,dp);}//记忆化搜索//过程：依次转一圈摆火柴//参数含义： 状态  每条边的长度  当前边长度 剩几条边没解决bool MS(int status,int limit,int cur,int rest,vector<int>&matchsticks,vector<int>&dp){if(rest==0)//都解决了{return status==0;//是否都用了}if(dp[status]!=0){return dp[status]==1;}bool ans=false;for(int i=0;i<matchsticks.size();i++){if((status>>i)&1==1&&cur+matchsticks[i]<=limit)//能用且不会超{if(cur+matchsticks[i]==limit)//正好拼成{ans=MS(status^(1<<i),limit,0,rest-1,matchsticks,dp);}else{ans=MS(status^(1<<i),limit,cur+matchsticks[i],rest,matchsticks,dp);}if(ans)//有就行{break;}}}dp[status]=ans?1:-1;return ans;}
};

因为最多就十五根火柴，且不能重复选，所以也考虑用状态压缩。

首先是个剪枝，统计一下累加和，若不能被4整除，那根本不可能拼成，就直接返回。之后的思路就是让火柴转着圈顺着拼，那么每条边的边长就是四分之累加和。所以递归函数除了status位信息存哪根火柴用了，还要带着每条边长limit，当前边已经凑出来了多少cur和还剩几条边没解决rest。

所以递归函数就是当rest等于0了，即四条边都解决了，那就判断一下status是否等于0，即是否都用过了。之后枚举每个火柴，若之前没用过且长度加上当前边的凑出来的长度没超，才能接着讨论。之后若相加正好等于边长ÿ

前言