所谓的状压dp指的是状态压缩dp。具体来说就是借助二进制数来对保存状态时的空间复杂度进行优化。举个简单的例子，对于一个n行m列的棋盘，如果用1表示有棋子放置，用0表示没有棋子放置，则我们可以用n个m位的二进制数来表示当前棋盘的整体状态。与常规的使用数组保存状态相比，对于一个n行m列的棋盘，至少需要一个n × m的int型数组来进行保存，也就是n × m × 32 byte。而使用二进制数表示则只需要n × 32 byte（一般而言）。由此可见，空间复杂度得到了很大的优化。而在状压dp中，我们可以使用各种位运算来操作二进制数，这使得时间复杂度也很优良。
首先上一道题目感受一下吧。
题目大意是说，有一块m行n列的牧场，每一格都是一块正方形的土地。现在要在这些土地上种草，规则是只能在肥沃的土地上种草，且不能选择两块相邻的土地。问一共有多少种可行的种植方案。（完全不种草也是一种方案）
如果不使用状压dp而是直接暴力dfs的话，当n和m取到最大值时，很有可能跑几个小时都跑不出结果......
考虑使用状压dp。大致思路为，首先使用m个n位的二进制数保存土地的肥沃情况，然后预处理出所有不存在相邻列的行状态。dp[i][j]表示的是对于牧场的第i行，在状态j下一共有多少种放置方法。对于第i行，我们可以由第k-1行转移过来。状态转移方程为: \[ dp[i][j]=(dp[i][j]+dp[i-1][k])\ mod\ p\\ p = 100000000, 0\lt j\lt (1<<n),0\lt k\lt (1<<n) \] 在最后计算答案的时候，根据dp[][]的定义，我们只需要讲dp[n][]里面的内容全部加起来，然后取个模就是题目要求的答案。
代码如下:
（由于个人习惯，代码中是n行m列，而非题目所述的m行n列）
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=20005;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int map_[15];
int arr[1<<12+5];
int dp[15][1<<12+5];
int mod=100000000;
int main()
{
IOS;
int n,m;
cin>>n>>m; //n行m列
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int tmp;cin>>tmp;
map_[i]=(map_[i]<<1)+tmp; //用二进制数保存
}
}
for(int i=0;i<(1<<m);i++){
arr[i]=((i&(i<<1))==0)&&((i&(i>>1))==0); //检查该状态是否有相邻列
}
mst(dp,0);
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<(1<<m);j++){
if(arr[j]&&((j&map_[i])==j)){ //当前状态没有相邻列，且都是在肥沃土地上种草
for(int k=0;k<(1<<m);k++){ //枚举上一行的状态
if((k&j)==0) //同一列上没有相邻
dp[i][j]=(dp[i][j]+dp[i-1][k])%mod; //当前行的状态由上一行转移而来
}
}
}
}
int ans=0;
for(int i=0;i<(1<<m);i++)
ans=(ans+dp[n][i])%mod;
cout<<ans<<endl;
return 0;
}通过这道题目，有没有一种感觉，状压dp其实是一种高效的暴力，也就是说，其本质还是暴力？确实如此，状压dp其实可以说是经过了很好的优化的暴力(至少目前我是这么认为的OTZ)。抓住这一点，有利于我们建立状压dp的思考方法。
再看一道题
题目大意是说，在一个n × n的棋盘中放k个国王，使他们互不攻击，问有多少种摆放的方案。国王可以攻击到它的上下左右，以及左上左下右上右下八个方向。
这道题与上一道题有点像，但多了个k个国王的约束条件。大致思路为：首先预处理出所有不存在列相邻情况的行状态，也就是那些无法让国王横向攻击的行状态。通过上一行的状态，可以转移得到当前行的状态。状态转移方程为： \[ dp[i][j][kings[i]+cnt]+=dp[i-1][p][cnt]\ \] 该方程的第一维表示的是当前所处行的行号，第二维表示的是状态j，第三维表示的是在这一行以及这一行上面的行中一个放置了的国王的个数(kings[i]表示的是状态j的国王个数，也就是有多少个1)。
具体代码如下:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=20005;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll ok[1<<9+5];
ll kings[1<<9+5];
ll dp[10][1<<9+2][100];
int main()
{
IOS;
int n,k;
cin>>n>>k;
mst(ok,0);mst(kings,0);
mst(dp,0);
int maxi_state=(1<<n);
int idx=0;
for(int i=0;i<maxi_state;i++){ //预处理所有不存在列相邻情况的行状态
if((i&(i<<1))==0){
ok[idx++]=i;
}
}
for(int i=0;i<idx;i++){ //数一下状态i有多少个国王，也就是有多少个1
int tmp=ok[i];
while(tmp){
kings[i]+=(tmp&1); //等价于kings[i]+=tmp%2;
tmp>>=1; //等价于tmp/=2;
}
}
for(int i=0;i<idx;i++){
if(kings[i]<=k) //如果第一行的国王个数不大于k
dp[1][i][kings[i]]=1; //先处理第一行，以便根据第一行推出第二行
}
for(int row=2;row<=n;row++){ //处理每一行
for(int i=0;i<idx;i++){ //枚举当前行的状态
for(int j=0;j<idx;j++){ //枚举上一行的状态
if(ok[i]&ok[j]) //如果行相邻
continue;
if((ok[j]<<1)&(ok[i])) //如果对角线上有国王
continue;
if((ok[j]>>1)&(ok[i])) //同上
continue;
for(int cnt=1;cnt<=k;cnt++){
if(kings[i]+cnt<=k){ //国王数不能超过k
dp[row][i][kings[i]+cnt]+=dp[row-1][j][cnt];
}
}
}
}
}
ll ans=0; //注意要用long long，否则会WA
//因为不知道到底是在哪一行用完k个国王，所以要把所有行上的方案数都加起来
for(int i=1;i<=n;i++)
for(int j=0;j<idx;j++)
ans+=dp[i][j][k];
cout<<ans<<endl;
return 0;
}最后再来一题
大致题意是说，现在要交作业了，一共有n项作业要做，每一项作业都对应一个ddl和完成所需要的时间，如果超过了ddl，则会得到一定的惩罚，每超过1天则惩罚加1分。问如何安排做作业的次序才能使得到的惩罚最少。
一开始看到这道题目时我没有想到要用状压，因为那时我还没学......我想到的是，这题感觉可以通过DAG来解决，但又似乎不是正解.....所以正确做法应该是，用二进制数表示某一科目是否已经完成，0表示未完成，1表示已完成。故011表示第1和第2项作业已经完成，而第3项则未完成。一个表示作业完成情况的二进制数是可以由其他二进制数转移而来的，如011就可以有001和010转移而来，而001和010都是由000转移而来。这就是这道题dp的基本思路。而对于这道题的输出，因为要输出做作业的次序，所以需要输出路径。这只需要记录下当前作业的前驱，输出时递归一下即可。具体见代码注释。
代码如下：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
using namespace std;
struct hw{
string name;
int cost;
int ddl;
};
hw hws[20];
int dp[(1<<15)+5];
int pre[(1<<15)+5];
int n;
void show(int state)
{
if(state==0) return ;
int tt=0;
for(int i=0;i<n;i++){
if(((1<<i)&state)&&(((1<<i)&pre[state])==0)){
//如果在状态state下，作业i已经完成，而state的前驱没有完成作业i，那就说明state相较于其
//前驱，多完成了作业i
tt=i;
break;
}
}
show(pre[state]);
cout<<hws[tt].name<<endl;
}
int main()
{
IOS;
int t;cin>>t;
while(t--){
mst(pre,0);
cin>>n;
for(int i=0;i<n;i++)
cin>>hws[i].name>>hws[i].ddl>>hws[i].cost;
int maxi_state=(1<<n);
for(int i=0;i<maxi_state;i++)
dp[i]=INF; //因为是求最小值，所以初始化为INF
dp[0]=0; //所有作业都没做时，惩罚自然也是0
int kase=0;int t1=0;int t2=0;
for(int i=0;i<maxi_state;i++){ //枚举完成作业的情况
for(int j=0;j<n;j++){ //枚举作业
if(i&(1<<j)) //如果当前作业已经完成了，就continue
continue;
int tot=0;
for(int k=0;k<n;k++){
if(i&(1<<k))
tot+=hws[k].cost; //将已经完成的作业所花费的时间加起来
}
tot+=hws[j].cost; //再加上当前作业
int penalty=0;
if(tot>hws[j].ddl) //计算惩罚
penalty=tot-hws[j].ddl;
else
penalty=0;
int tmp=dp[i|(1<<j)];
dp[i|(1<<j)]=min(dp[i|(1<<j)],dp[i]+penalty);
if(dp[i|(1<<j)]!=tmp) //小于时才去记录
pre[i|(1<<j)]=i; //pre[]保存前驱状态
}
}
cout<<dp[(1<<n)-1]<<endl;
show((1<<n)-1);
}
return 0;
}所以，经过这三道题目，可以得出结论，状压dp其实本质就是暴力(大概)