• 动态规划随着阶段增长，在每个状态维度上会不断扩展；任意时刻已求解状态和尚未求解的状态在各个维度上的分界点组成DP扩展的轮廓。对于某些问题，我们需要在动态规划的“状态”中记录一个集合，保存这个“轮廓”的详细信息，以便进行状态转移。 若集合大小不超过N，集合中每个元素都是小于K的自然数，则我们可以把这个集合看作一个N位K进制数，以一个$[O,K^{N-1}]$之间的十进制整数的形式作为DP状态的一维。
• 状态压缩DP：将集合转化为整数记录在DP状态中的一类算法。
• 使用条件：一般能够采用状态压缩dp的题目数据规模都不大（<30），这是判断是否能够采用状态压缩dp的一个重要条件。

博客中大部分例题测试数据均为笔者生成的随机数据，若数据太弱或有错请留言评论；另外本博客参考了李煜东的《算法竞赛进阶指南》课本和周伟的《状态压缩》论文。

我不生产知识，我只是个知识的搬运工！！！

一. 棋盘类状压DP

引例

在n*n(n≤20)的方格棋盘上放置n个车(可以攻击所在行、列)，求使它们不能互相攻击的方案总数。

组合数学：一行一行的放，则第一行有n种选择，第二行n-1，……，最后一行只有1种选择，根据乘法原理，答案就是n!
状态压缩：一行一行的放，并取每列是否放置了棋子作为状态；某一列如果已经放置棋子则为1，否则为0。这样，一个状态就可以用一个最多20位的二进制数表示。例如n=5，且第1、3、4列已经放置，则这个状态可以表示为01101(从右到左)。设fs为达到状态s的方案数，则可以尝试建立f的递推关系。
考虑n=5，s=01101；状态中有3个1，即有3行放置了棋子，因为是一行一行放置的，所以达到s时已经放到了第三行。一行只能放一个车，则第三行的车只有三种情况（第1列、第3列或第4列）：

根据上面的讨论思路推广之，得到引例的解决办法：
$f_0=1$
$f_s=\sum f_{s-2^i}$，其中s从右往左数（从0开始）第i位二进制位为1
核心代码如下：

dp[0]=1;//其他值均为0 
for(int s=1;s<(1<<n);s++)//枚举所有可能的状态0--2^n-1 
	for(int i=0;i<n;i++)//枚举s的每个二进制位 
		if((s>>i)&1)//如果s的第i个位置是1则转移 
			dp[s]+=dp[s-(1<<i)]; 
cout<<dp[(1<<n)-1];

反思这个算法，其正确性毋庸置疑(可以和$n!$对比验证)
但是算法的时间复杂度为O($n\ast 2^n$)，空间复杂度O($2^n$)，是个指数级的算法，比用循环O(n)时间复杂度计算n!差的多，它有什么优势？

答案是：可扩展性，具体的可以看看以下的例题

例1

【题目描述】
在$n\ast n(n\le 20)$的方格棋盘上放置n个车，某些格子不能放，求使它们不能互相攻击的方案总数。
【输入描述】
一个$n\ast n$的矩阵maze， 如果maze[x][y]为0表示该位置不能放，如果为1则能放

• 组合数学+容斥原理——复杂。
• 状态压缩：和引例一样，逐行放置，不同点在于有些格子不能放；引例的实质是枚举状态s中的1进行转移，因此对于此题只要枚举的同时判断该位置是否可放即可。
• 算法优化：
  (1). 将棋盘的第i行是否能放的二进制数（能1不能0），压缩为一个十进制数，得到状态g[i]。设ts=s & g[i]，枚举ts中的1即可，g[i]会将s中不能放的位置中的1消除。例如：$s=(100110{)}_2，g[i]=(100011{)}_2则ts=(100010{)}_2$
  (2).应用lowbit寻找二进制中的1，加快转移速度

例2

【题目描述】U204450
在$n\ast m(n,m\le 20)$的方格棋盘上放置k个车，有的位置不能放，求使它们不能互相攻击的方案总数。
【输入描述】
一个$n\ast m$的矩阵maze ，如果maze[x][y]为0表示该位置不能放，如果为1则能放

和例1类似，不同点在于这里是$n\ast m$的棋盘，只放k个车；$k>min(n,m)$时方案数一定为0。将i行能放或不能放压缩为一个整数can[i]；逐行考虑，每行可能放0个或1个车，状态将和放置车的个数有关

• 状态定义：f[i][j][s]表示前i行放j个车，且它们的放置状态为s时的方案数
• 状态转移：
  若第i行不放，f[i][j][s]=f[i-1][j][s]
  若第i行放1个，枚举t=s&can[i]二进制位中的1，t中的每个1都有可能是第i行放的；$f[i][j][s]=\sum f[i-1][j-1][t-2^x]$其中t的第x位为1
• 边界条件：前i行放0个车，则状态一定为0，此时方案数为1，即f[i][0][0]=1
• 目标状态：f[n][k][含有k个1的所有s]
• 时空优化：空间上可以数组滚动优化，预处理包含j个1的s有哪些

#include<bits/stdc++.h>
using namespace std;
const int N=21;
int n,m,k,ans,can[N],f[2][N][1<<N];
int lowbit(int x){
   
    return x&(-x);}
int calOne(int x){
   
    //计算状态x的二进制位中有多少个1
	int cnt=0;
	while(x)cnt++,x-=lowbit(x);
	return cnt;
}
vector<int>sta[N];
int main(){
   
    
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
		for(int j=1,x;j<=m;j++){
   
    
			scanf("%1d",&x);
			can[i]|=(x<<(j-1));
		}
	for(int s=0,ms=1<<m;s<ms;s++)
		sta[calOne(s)].push_back(s);
	f[1][0][0]=f[0][0][0]=1;//前i行放0个状态为0时的方案数为1
	for(int i=1;i<=n;i++){
   
    
		for(int j=1;j<=min(i,k);j++){
   
    
			for(int x=0;x<sta[j].size();x++){
   
    
				int s=sta[j][x];
				f[i%2][j][s]=f[(i-1)%2][j][s];
				int t=s&can[i];
				while(t)
					f[i%2][j][s]+=f[(i-1)%2][j-1][s-lowbit(t)],t-=lowbit(t);
			}
		} 
	}
	for(int x=0;x<sta[k].size();x++)ans+=f[n%2][k][sta[k][x]];
	printf("%d",ans);
	return 0;
} 

例3

【题目描述】U204630
有一个$n\ast m$的棋盘($n,m\le 80,n\ast m\le 80$)要在棋盘上放k(k<80)个棋子，使得任意两个棋子不相邻；且有些格子不能放，求合法的方案总数。
【输入描述】
输入n,m,k
【输出描述】
合法的方案总数

• 数据规模：n×m≤80，似乎不适合状态压缩求解，$2^{80}$时间和空间都无法承受
• 隐含条件：9*9=81>80，则n，m不可能同时大于9；因此，min(n,m)≤8。若m>n，交换m和n（相当于棋盘旋转90°）；每行的状态可以用m位的二进制数表示，然后逐行放置。（状态总数为$2^m$，所以要让m尽量小）
• 行限制：每行可以放0到$m/2$ 个棋子，只要棋子放定则第i行状态$S_i$便确定；
• 列限制：放第i行时需要与第i-1行比较，若$S_i$ & $S_{i-1}==0$则该组合是可行的，对于确定的$S_i$需要枚举其对应的组合$S_{i-1}$，然后采用加法原理相加。因此$S_i$应该设计到状态中去。
• 棋子放置个数不得超过k，因此放置棋子的个数也应该设计到状态中去。
• 状态设计：$f[i][j][S_i]$表示前i行共放置j个棋子，且第i行棋子状态为$S_i$时的方案数。
• 目标状态： f [ n ] [ k ] [ 所 有 满 足 条 件 的 S ] f[n][k][所有满足条件的S]