状态压缩DP：位运算优化动态规划的实战指南

1. 状态压缩DP的本质与核心思想

状态压缩动态规划（State Compression DP）是动态规划中一种特殊的优化技巧，它通过位运算将复杂的状态表示压缩为整数形式，从而大幅降低空间复杂度。我第一次接触这个概念是在解决棋盘覆盖问题时，当时传统DP方法的内存消耗已经达到了GB级别，而状态压缩版本仅需几MB。

状态压缩的核心在于"状态表示"的转化。举个例子，当我们处理一个4x4棋盘时，每个格子有"已覆盖/未覆盖"两种状态。传统方法会用二维数组dp[i][j]来记录每个格子的状态，这需要O(n²)的空间。而状态压缩版本可以用一个16位二进制数表示整个棋盘状态，每一位对应一个格子（1表示覆盖，0表示未覆盖），这样状态空间瞬间压缩到O(1)。

关键认知：状态压缩不是独立的算法，而是DP的一种实现技巧。它特别适合状态具有以下特征的问题：

1. 每个状态元素只有有限几种取值（通常是二值）
2. 状态元素之间存在强约束关系
3. 状态总数会随规模指数级增长

2. 位运算在状态压缩中的关键作用

2.1 基础位操作技巧

状态压缩DP的实现严重依赖位运算，以下是五个必须掌握的位操作：

// 设置第i位为1 mask |= (1 << i); // 设置第i位为0 mask &= ~(1 << i); // 检查第i位是否为1 if (mask & (1 << i)) {...} // 切换第i位状态 mask ^= (1 << i); // 获取最低位的1所在位置 int pos = __builtin_ctz(mask); // GCC内置函数

在实际编码中，我习惯用宏定义这些操作：

#define SET(mask, i) ((mask) |= (1<<(i))) #define CLR(mask, i) ((mask) &= ~(1<<(i))) #define TEST(mask, i) ((mask) & (1<<(i)))

2.2 状态转移中的位运算

考虑经典的旅行商问题(TSP)，我们需要记录已经访问过的城市。假设有5个城市，状态mask=10110表示已经访问过城市1、2、4（从右往左数）。

从城市3出发的转移可以这样实现：

int new_mask = mask | (1 << 3); dp[new_mask][3] = min(dp[new_mask][3], dp[mask][current] + dist[current][3]);

这里有个易错点：位序的方向性。有些问题约定最低位（最右边）表示第一个元素，有些则相反。我在第一次实现TSP时就因为这个细节调试了整整两小时。

3. 经典问题解析：棋盘覆盖问题

3.1 问题描述与状态设计

在一个M×N的棋盘上，用1×2或2×1的骨牌完全覆盖，求方案数。这是状态压缩DP最经典的入门问题。

状态设计：

• dp[i][mask]：表示处理到第i行时，该行的覆盖状态为mask的方案数
• mask的每一位表示该列是否被当前行的骨牌占据（1表示被占据）

3.2 状态转移实现

关键点在于预处理所有合法的相邻行状态转移对。以下是核心代码片段：

void preprocess() { for (int prev = 0; prev < (1<<n); ++prev) { for (int curr = 0; curr < (1<<n); ++curr) { if (valid_transition(prev, curr)) { trans[prev].push_back(curr); } } } } int solve() { dp[0][0] = 1; for (int i = 1; i <= m; ++i) { for (int prev_mask = 0; prev_mask < (1<<n); ++prev_mask) { for (int curr_mask : trans[prev_mask]) { dp[i][curr_mask] += dp[i-1][prev_mask]; } } } return dp[m][0]; // 最后一行不能有任何突出 }

实战经验：预处理合法转移状态可以提速10倍以上。我在POJ 2411这道题上，预处理版本仅需15ms，而实时检查的版本需要200ms。

4. 状态压缩DP的优化技巧

4.1 滚动数组优化

由于状态转移通常只依赖前一层状态，可以用滚动数组将空间复杂度从O(M*2^N)降到O(2^N)：

int dp[2][1<<N]; int now = 0, prev = 1; for (int i = 1; i <= m; ++i) { swap(now, prev); memset(dp[now], 0, sizeof(dp[now])); for (int mask = 0; mask < (1<<n); ++mask) { for (int new_mask : trans[mask]) { dp[now][new_mask] += dp[prev][mask]; } } }

4.2 对称性剪枝

很多问题具有行列对称性。例如在棋盘问题中，旋转对称的状态可以合并处理。我曾在UVA 11210中通过对称性剪枝将状态数减少了75%。

4.3 按状态中1的个数分组处理

当状态转移只与mask中1的个数相关时，可以按popcount（二进制中1的个数）分组：

vector<int> group[N+1]; for (int mask = 0; mask < (1<<N); ++mask) { group[__builtin_popcount(mask)].push_back(mask); } for (int cnt = 0; cnt <= N; ++cnt) { for (int mask : group[cnt]) { // 处理状态转移 } }

5. 从经典问题到变种实战

5.1 带障碍的棋盘覆盖

当棋盘中某些格子被禁止覆盖时，需要额外检查障碍位置。状态mask中对应障碍位必须为0：

bool no_conflict(int mask, int row) { return (mask & forbidden[row]) == 0; }

5.2 三进制状态压缩

当每个位置有三种状态（如红/绿/蓝染色问题），可以用两个二进制位表示一个状态，或者用三进制编码：

int encode(int* color) { int res = 0; for (int i = 0; i < n; ++i) { res = res * 3 + color[i]; } return res; } void decode(int mask, int* color) { for (int i = n-1; i >= 0; --i) { color[i] = mask % 3; mask /= 3; } }

5.3 高维状态压缩

有些问题需要同时压缩多个维度的状态。比如在炮兵阵地问题中，需要同时记录当前行和前一行的状态：

dp[i][mask_prev][mask_curr] = ... // 空间复杂度O(M*2^(2N))，此时滚动数组优化更为关键

6. 调试与性能调优经验

6.1 状态可视化调试

当N较大时，打印二进制mask可读性差。我习惯用以下调试函数：

void print_mask(int mask, int n) { for (int i = n-1; i >= 0; --i) { cout << ((mask >> i) & 1); } cout << endl; }

6.2 时间复杂度估算

状态压缩DP的时间复杂度通常是O(M2^NT)，其中T是每个状态的转移代价。当N>20时，2^N将达到百万级别，这时需要考虑：

1. 是否能用meet-in-the-middle技巧
2. 是否有对称性可以优化
3. 能否转化为稀疏状态转移

6.3 内存访问优化

由于要频繁访问dp[mask]，让mask作为连续内存访问可以提升cache命中率。例如在TSP中：

// 不好的方式：dp[current][mask] - 不连续 // 好的方式：dp[mask][current] - mask变化时内存连续

7. 与其他DP技术的结合

7.1 状态压缩+数位DP

处理数字相关问题时，可以结合数位DP的思想。例如求[L,R]区间内满足某种二进制特性的数字个数：

int dfs(int pos, int mask, bool limit) { // pos: 当前处理位 // mask: 压缩的状态 // limit: 是否受到上限限制 ... }

7.2 状态压缩+概率DP

在马尔可夫决策过程中，可以用状态压缩表示当前系统状态：

double dp[1<<N]; for (int mask = (1<<n)-1; mask >= 0; --mask) { for (int i = 0; i < n; ++i) { if (!(mask & (1<<i))) continue; // 根据概率转移方程更新dp[mask] } }

7.3 状态压缩+双队列优化

当状态转移具有单调性时，可以用双队列将时间复杂度降一个数量级。我在解决一道资源分配问题时，通过这个技巧将运行时间从2秒降到了0.2秒。

8. 实战建议与学习路径

1. 入门路线：

   • POJ 2411 (骨牌覆盖)
   • HDU 1400 (类似POJ 2411)
   • UVA 10651 (状态压缩+记忆化搜索)

2. 进阶挑战：

   • POJ 1185 (炮兵阵地)
   • HDU 3001 (三进制状态压缩TSP)
   • Codeforces 8C (特殊的状态设计)

3. 避坑指南：

   • 始终用unsigned类型处理位运算，避免符号位问题
   • 对于N>20的问题，考虑折半枚举或剪枝
   • 预处理合法转移状态表能大幅提升性能
   • 使用__builtin_popcount等编译器内置函数

状态压缩DP的学习曲线较为陡峭，我建议从简单的棋盘覆盖问题入手，逐步增加难度。在实现时，先写一个暴力版本验证状态设计的正确性，再逐步优化。记住，好的状态设计往往能减少50%以上的编码复杂度。