状压DP入门详解：从思路到实战

一、什么是状压DP？

状态压缩动态规划（简称状压DP）是一种利用二进制位运算来表示和处理状态的动态规划方法。它主要解决的是状态过多但规模较小的问题，通常适用于数据范围在 n ≤ 25 的情况。

为什么需要状压？

在传统的DP中，如果状态是某个集合，我们很难直接用一个数组维度来表示。而二进制恰好可以很自然地表示"选"或"不选"两种状态，多个二进制位组合就能表示一个集合。

二、状压DP的核心——位运算

必备的位运算操作

操作	代码	含义
判断第i位是否为1	`(j>>i)&1`	检查状态j中第i个元素是否被选中
将第i位设为1	`S	=(1<<i)`
检查相邻1	`j&(j>>1)`	检查状态j中是否有相邻的1
取交集	`S&T`	两个状态取交集
取并集	$S或T$	两个状态取并集

三、状压DP的通用解题框架

解题四步法：

状态设计
- 定义 $dp[j]$ 或 $dp[i][j]$ ，其中 $j$ 是二进制状态
- 明确状态含义： $dp[j]$ 表示达到状态S的答案（方案数/最小代价等）
状态转移
- 考虑如何从已知状态推导到未知状态
- 通常形式： $dp[新状态]=min/max(dp[新状态], dp[原状态]+代价)$
- 或者： $dp[新状态]+=dp[原状态]$
初始化
- 确定起点状态的初始值
- 通常： $dp[0]=0$ 或 $dp[初始状态]=1$
结果提取
- 从最终状态中提取答案
- 可能是 $dp[全集]$ 、 $min(dp[所有状态])$ 等

四、经典例题详解

例题1：P1879 Corn Fields G

题目大意：在

m×n

的土地上种草，有些格子不能种，相邻格子不能同时种草，求方案数。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[2005],mod=1e8,dp[25][1<<13];
signed main()
{
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int x;
			cin>>x;
			a[i]=(a[i]<<1)+x;
		}
	}
	dp[0][0]=1;
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<(1<<n);j++)
		{
			if((j&(j<<1))==0)
			{
				if((j&a[i])==j)
				{
					for(int k=0;k<(1<<n);k++)
					{
						if((j&k)==0)
						{
							dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
						}
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<(1<<n);i++)
		ans=(ans+dp[m][i])%mod;
	cout<<ans;
	return 0;
}

关键点：

用 $a[i]$ 存储每行的土地状态，1表示肥沃
预处理所有行内不相邻的状态
转移时检查：①状态与土地匹配 ②上下行不相邻

五、状压DP的常见题型总结

题型	特征	解题关键
棋盘放置	棋盘上有放置限制	预处理行内合法状态，检查行间兼容性
最短路径	需要访问所有点一次	状态表示已访问的点集，维度记录当前位置
集合划分	将集合划分成若干子集	状态表示已分配的元素集合

六、实战技巧与注意事项

1. 空间优化

当 $n=20$ 时，状态数可达 $2^20≈1e6$ ，要注意数组开不下时使用滚动数组

2. 时间优化

预处理合法状态和状态间关系
使用剪枝减少不必要的状态转移

3. 调试技巧

CPP

// 打印二进制状态（调试用）
void print(int s,int n) {
    for(int i=n-1;i>=0;i--)
    {
        cout<<((s>>i)&1);
    }
    cout<<endl;
}

4. 常见错误

位运算优先级问题：多用括号，如(s >> i) & 1
数组越界：注意状态范围是0到(1<<n)-1
初始化不完整：确保所有起点状态正确初始化

七、推荐练习顺序

P1879 Corn Fields G - 最基础的棋盘状压DP
P1171 售货员难题 - 经典的旅行商问题
P1433 吃奶酪 - 二维平面上的最短路径

状压DP总结

文章操作