专题：数据结构与算法系统学习
关键词：数据结构, 算法, 状态压缩, 状压DP, 位运算, TSP, 旅行商, 插头DP, 子集枚举
一、概述
状态压缩动态规划（State Compression Dynamic Programming，简称状压DP）是一类特殊的动态规划方法，其核心思想是将一个集合的状态用一个二进制整数来表示，从而将状态转移转化为位运算操作。状压DP适用于状态数量可控（通常是 2^n 级别，其中 n 不超过 20-25）且状态之间存在子集或顺序依赖关系的场景。
状压DP在实际算法竞赛和面试中非常常见，经典的应用场景包括：旅行商问题（TSP）、图着色问题、棋盘覆盖问题、任务调度问题、子集枚举类问题等。通过将状态压缩为整数，我们可以用 dp[mask] 或 dp[mask][i] 的方式来表示"当前已经访问过的元素集合为 mask，且当前位于位置 i"这样的状态，从而大幅降低状态设计的复杂度。
核心思想：一个整数的二进制表示中的每一位（bit）代表某一个元素是否被选中（1 表示选中，0 表示未选中）。这样，一个 int 类型的整数（32位）就可以表示最多 32 个元素的子集状态。
适用条件
- 状态维度小：需要压缩的状态维度 n 一般 ≤ 20，个别情况可到 25（2^25 = 33,554,432，仍在内存可接受范围）
- 状态可枚举：所有可能的子集状态可以被枚举且状态数不超过千万级别
- 转移依赖子集：状态转移依赖于子集或超集的关系，且可以通过位运算高效实现
- 无后效性：满足动态规划的无后效性要求，子问题的解独立于后续决策
二、状态压缩的核心思想
2.1 用二进制位表示集合
假设我们有 n 个元素，编号为 0 到 n-1。任何一个子集 S 都可以用一个 n 位的二进制数来表示。例如 n = 5 时：
- 二进制
00000 表示空集 {}，对应的整数为 0
- 二进制
10101 表示集合 {0, 2, 4}，对应的整数为 21
- 二进制
11111 表示全集 {0, 1, 2, 3, 4}，对应的整数为 31
# 基本概念示例
n = 5
full_mask = (1 << n) - 1 # 11111 = 31, 表示全集
# 集合 {0, 2, 4}
mask = (1 << 0) | (1 << 2) | (1 << 4) # 10101 = 21
print(mask) # 输出 21
print(bin(mask)) # 输出 0b10101
2.2 位运算的基本操作
状压DP的基石是位运算。以下是最常用的位运算操作，读者应当熟练掌握：
# 假设 mask 是一个表示集合的整数，n 为元素数量
# 1. 判断第 i 个元素是否在集合中
def has_bit(mask, i):
return (mask >> i) & 1
# 2. 将第 i 个元素加入集合
new_mask = mask | (1 << i)
# 3. 将第 i 个元素从集合中移除
new_mask = mask & ~(1 << i)
# 4. 翻转第 i 个元素的状态（异或）
new_mask = mask ^ (1 << i)
# 5. 统计集合中元素的个数（内置函数）
cnt = mask.bit_count() # Python 3.8+
# 或使用内置 bin 函数
cnt = bin(mask).count('1')
技巧：Python 3.10+ 的 int.bit_count() 方法使用 CPU 指令集加速（POPCNT），在大量调用时比 bin(mask).count('1') 快数百倍。在算法竞赛中务必使用 bit_count()。
三、常用位运算技巧
3.1 枚举子集
枚举一个集合的所有子集是状压DP中最常见的操作之一。给定 mask，枚举其所有子集的标准写法如下：
# 枚举 mask 的所有子集（包括空集和自身）
sub = mask
while True:
print(bin(sub)) # 处理子集 sub
if sub == 0:
break
sub = (sub - 1) & mask
# 只枚举真子集（排除自身）
sub = (mask - 1) & mask
while sub:
print(bin(sub))
sub = (sub - 1) & mask
这个算法的精妙之处在于：(sub - 1) & mask 会跳过那些不在 mask 中的位，直接得到下一个子集。它的时间复杂度是 O(2^k) 其中 k 是 mask 中 1 的个数，而不是 O(2^n)。
3.2 枚举超集
在某些DP场景中（如集合覆盖问题），我们需要枚举一个集合的所有超集：
# 枚举 mask 的所有超集（在全集 full_mask 范围内）
sup = mask
while sup <= full_mask:
print(bin(sup)) # 处理超集 sup
sup = (sup + 1) | mask
# 原理：加1后将低位清零，再或上 mask 保证 mask 的位始终保留
3.3 其他实用位运算技巧
# 1. 获取最低位的 1 (lowbit)
lowbit = mask & -mask
# 原理：-mask = ~mask + 1 (补码)，与 mask 相与得到最低位 1
# 2. 移除最低位的 1
mask &= mask - 1
# 3. 枚举所有仅包含 k 个 1 的二进制数（组合枚举）
mask = (1 << k) - 1 # 最小的 k-1 位为 1
while mask < (1 << n):
print(bin(mask))
# 下一个包含 k 个 1 的数 (Gosper's Hack)
c = mask & -mask
r = mask + c
mask = (((r ^ mask) >> 2) // c) | r
Gosper's Hack 是一个精妙的位运算算法，它可以按字典序枚举所有恰好包含 k 个 1 的 n 位二进制数。在需要恰好选择 k 个元素的状压DP问题中非常实用。
3.4 位运算技巧速查表
| 操作 | 表达式 | 说明 |
|---|
| 判断第 i 位 | (mask >> i) & 1 | 返回 1 表示第 i 位为 1 |
| 设置第 i 位为 1 | mask | (1 << i) | 将第 i 位设为 1 |
| 设置第 i 位为 0 | mask & ~(1 << i) | 将第 i 位清零 |
| 翻转第 i 位 | mask ^ (1 << i) | 0 变 1，1 变 0 |
| 最低位的 1 | mask & -mask | 获取 lowbit |
| 移除最低位 1 | mask & (mask - 1) | 消去最后一个 1 |
| 统计 1 的个数 | mask.bit_count() | Python 3.8+，硬件加速 |
| 枚举子集 | sub = (sub - 1) & mask | 从 mask 自身开始 |
| 全集 | (1 << n) - 1 | n 位全为 1 |
四、旅行商问题（TSP）的状压DP解法
4.1 问题描述
旅行商问题（Traveling Salesman Problem, TSP）是经典的NP完全问题：给定 n 个城市和每对城市之间的距离，求一条从起点出发、经过每个城市恰好一次、最后回到起点的最短路径（哈密顿回路）。
4.2 状态定义与转移
用状压DP求解TSP的核心思路：
- 状态定义：
dp[mask][i] 表示已经访问过的城市集合为 mask，当前位于城市 i 时的最短路径长度
- 初始状态：
dp[1 << 0][0] = 0（假设从城市 0 出发）
- 状态转移：从当前城市 i 前往下一个未访问的城市 j：
dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist[i][j])
- 最终答案：
min(dp[(1 << n) - 1][i] + dist[i][0])（返回起点）
def tsp_dp(dist):
"""TSP 状压DP解法
dist: n x n 的距离矩阵, dist[i][j] 表示城市 i 到 j 的距离
返回最短哈密顿回路的长度
"""
n = len(dist)
INF = 10**18
size = 1 << n # 状态总数 2^n
# dp[mask][i]: 已访问 mask 中的城市，当前在 i
dp = [[INF] * n for _ in range(size)]
# 初始状态：从城市 0 出发
dp[1 << 0][0] = 0
# 按 mask 中 1 的个数从小到大递推
for mask in range(1, size):
if not (mask & 1): # 剪枝：必须包含起点城市 0
continue
# 如果 dp[mask][i] 已经被更新过，尝试从 i 走到 j
for i in range(n):
if not (mask >> i) & 1: # 城市 i 不在 mask 中
continue
if dp[mask][i] == INF:
continue
# 尝试前往未访问的城市 j
for j in range(n):
if (mask >> j) & 1: # 城市 j 已访问
continue
new_mask = mask | (1 << j)
new_dist = dp[mask][i] + dist[i][j]
if new_dist < dp[new_mask][j]:
dp[new_mask][j] = new_dist
# 最终答案：访问所有城市后返回起点 0
full_mask = (1 << n) - 1
ans = INF
for i in range(1, n):
if dp[full_mask][i] < INF:
ans = min(ans, dp[full_mask][i] + dist[i][0])
return ans
# 示例：4 个城市的 TSP
dist = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
print(f"最短回路长度: {tsp_dp(dist)}") # 输出: 80 (0->1->3->2->0)
4.3 复杂度分析
TSP状压DP的时间复杂度为 O(n^2 * 2^n)，空间复杂度为 O(n * 2^n)。当 n = 20 时，状态数约为 100 万（2^20 ≈ 10^6），每个状态需要遍历 n 个城市进行转移，总运算量约 4 亿次，在优化后可以在 1-2 秒内完成。
TSP 状压DP vs 暴力枚举：暴力枚举所有排列需要 O(n!)，当 n = 12 时 12! ≈ 4.79 亿，已经难以承受；而状压DP的 O(n^2 * 2^n) 在 n = 20 时仍可接受。这是指数级复杂度之间的巨大差异。
五、图着色问题
5.1 问题描述
图着色问题（Graph Coloring Problem）是指：给定一个无向图，用尽可能少的颜色对每个顶点染色，使得任意相邻的两个顶点颜色不同。这个问题在课程表安排、寄存器分配、频率分配等实际场景中有广泛应用。
5.2 状压DP解法
图着色问题的状压DP解法利用了"独立集"的概念来优化状态表示：
# 图着色问题的状压DP解法
# 求无向图的最小着色数（色数）
def min_colors(n, edges):
"""n: 顶点数量, edges: 边列表 [(u1,v1), (u2,v2), ...]
返回最小着色数
"""
# 预处理每个顶点的邻接掩码
adj = [0] * n
for u, v in edges:
adj[u] |= 1 << v
adj[v] |= 1 << u
# 预处理所有独立集 (independent set)
# 独立集：集合内任意两点之间没有边
size = 1 << n
is_independent = [False] * size
for mask in range(1, size):
# 检查 mask 是否构成独立集
ok = True
temp = mask
while temp:
low = temp & -temp
v = (low.bit_length() - 1) # 最低位 1 对应的顶点编号
if mask & adj[v]:
ok = False
break
temp ^= low # 移除已检查的顶点
is_independent[mask] = ok
# dp[mask] = 着色 mask 中顶点所需的最少颜色数
INF = n # 最多用 n 种颜色
dp = [INF] * size
dp[0] = 0
for mask in range(size):
if dp[mask] == INF:
continue
# 尝试给尚未着色的顶点集涂一种新颜色
remaining = (size - 1) ^ mask
# 枚举 remaining 的子集中是独立集的部分
sub = remaining
while sub:
if is_independent[sub]:
new_mask = mask | sub
dp[new_mask] = min(dp[new_mask], dp[mask] + 1)
sub = (sub - 1) & remaining
return dp[size - 1]
# 示例：一个 4 顶点图，形成一个环
# 0-1-2-3-0 (一个四元环)
n = 4
edges = [(0,1), (1,2), (2,3), (3,0)]
print(f"最小着色数: {min_colors(n, edges)}") # 输出: 2 (二部图, 2-着色)
图着色的状压DP优化技巧：通过预处理所有独立集，将状态转移从 O(n) 降低到了 O(1) 判断。配合子集枚举的技巧，可以在 O(3^n) 的时间内完成整个DP过程（因为每个状态需要枚举其剩余部分的子集，总复杂度为 O(3^n)）。
六、棋盘覆盖问题与插头DP简介
6.1 骨牌覆盖问题
棋盘覆盖问题是状压DP的经典应用之一。考虑一个 n 行 m 列的棋盘，用 1x2 或 2x1 的骨牌覆盖整个棋盘，求有多少种不同的覆盖方案。这类问题可以通过按行递推的状态压缩DP来解决。
# 用 1x2 骨牌覆盖 n x m 棋盘的方案数
# 状态表示：用 m 位二进制表示当前行的填充状态
# 1 表示该列已被占用（从上一行竖放下来），0 表示空闲
def domino_tiling(n, m):
"""返回用 1x2 骨牌覆盖 n x m 网格的方案数"""
size = 1 << m
# dp[row][mask]: 处理到第 row 行，当前行状态为 mask 的方案数
dp = [[0] * size for _ in range(n + 1)]
dp[0][0] = 1
for row in range(n):
for mask in range(size):
if dp[row][mask] == 0:
continue
# 尝试填充下一行，使用 DFS 枚举所有合法的横放/竖放组合
def dfs(col, next_mask, cur_mask):
nonlocal row, mask
if col >= m:
dp[row + 1][next_mask] += dp[row][mask]
return
# 如果当前列已被上一行占用
if (mask >> col) & 1:
dfs(col + 1, next_mask, cur_mask)
else:
# 竖放：占当前列和下一行的当前列
dfs(col + 1, next_mask | (1 << col), cur_mask)
# 横放：占当前列和下一列（要求下一列也在当前行空闲）
if col + 1 < m and not ((mask >> (col + 1)) & 1):
dfs(col + 2, next_mask, cur_mask)
dfs(0, 0, mask)
return dp[n][0]
# 示例：4x4 棋盘的骨牌覆盖方案数
print(f"4x4 棋盘覆盖方案数: {domino_tiling(4, 4)}") # 输出: 36
print(f"4x7 棋盘覆盖方案数: {domino_tiling(4, 7)}") # 输出: 781
6.2 插头DP（Plug DP / DP on Broken Profile）简介
插头DP是状压DP在棋盘类问题中的高级应用，它引入了"轮廓线"（Broken Profile / Contour Line）的概念，将状态压缩的范围从整行缩小到一行中的特定位置。插头DP的核心思想是：在逐格递推时，只记录当前处理位置处的轮廓线状态，从而将部分状态压缩到 O(m * 2^m) 甚至 O(m * 状态数) 的级别。
# 插头DP核心思路（伪码表示）
# 问题：求 n x m 棋盘中，用 1x2 骨牌覆盖的方案数
def plug_dp_domino(n, m):
"""插头DP解决骨牌覆盖问题（逐格递推版本）"""
size = 1 << m
dp = [0] * size
dp[0] = 1
for i in range(n):
for j in range(m):
new_dp = [0] * size
for mask in range(size):
if dp[mask] == 0:
continue
# 计算当前格 (i, j) 在轮廓线上的状态
# 关键：轮廓线中只记录"插头"信息
# 用 mask 的第 j 位表示当前格是否已被左侧或上方占用
occupied = (mask >> j) & 1
if occupied:
# 当前格已被占用，直接跳过，清除插头标记
new_mask = mask & ~(1 << j)
new_dp[new_mask] += dp[mask]
else:
# 当前格空闲，可以尝试竖放（占用下方格子）
# 竖放：在 mask 的第 j 位设置插头，表示下一行对应列被占用
new_mask = mask | (1 << j)
new_dp[new_mask] += dp[mask]
# 横放：占用右侧格子（要求 j+1 < m 且空闲）
if j + 1 < m and not ((mask >> (j + 1)) & 1):
new_mask2 = mask | (1 << (j + 1))
new_dp[new_mask2] += dp[mask]
dp = new_dp
return dp[0]
插头DP vs 逐行DP：逐行DP的状态是 O(2^m)，而插头DP在逐格递推时也维持 O(2^m) 的状态空间，但插头DP可以处理更复杂的条件（如障碍物、特定形状的多联骨牌等），且更容易扩展到更高级的连通性DP（如哈密顿路径计数）。
七、状压DP的优化策略
7.1 预处理合法状态
在许多状压DP问题中，只有一部分状态是合法的。预处理可以大幅减少无效状态的遍历：
# 预处理合法状态的通用模板
def preprocess_states(n):
"""预先筛选出所有合法状态"""
size = 1 << n
valid = []
valid_id = {} # mask -> index 映射
for mask in range(size):
if is_valid(mask): # 根据具体问题定义合法性
valid_id[mask] = len(valid)
valid.append(mask)
return valid, valid_id
# 预处理转移表（进一步优化）
# trans[i] = 从第 i 个合法状态可以转移到的合法状态列表
def preprocess_transitions(valid, n):
trans = []
for mask in valid:
next_states = []
# 枚举可以从 mask 转移到的状态
for next_mask in valid:
if can_transition(mask, next_mask):
next_states.append(next_mask)
trans.append(next_states)
return trans
优化效果示例：在棋盘覆盖问题中，行间合法的转移状态数往往远少于 2^m × 2^m。例如在骨牌覆盖问题中，对于 m=10，合法状态数约 144 种（而不是 1024 种），预处理后转移量可降低 99% 以上。
7.2 滚动数组
当状态转移只依赖于前一层或前几层时，可以使用滚动数组将空间复杂度从 O(2^n × n) 降至 O(2^n)：
# 滚动数组优化模板
def rolling_dp(n):
size = 1 << n
dp = [0] * size # 只用一维数组
dp[0] = 1 # 初始状态
for i in range(n):
new_dp = [0] * size # 新的一层
for mask in range(size):
if dp[mask] == 0:
continue
# 状态转移 ...
# new_dp[new_mask] += dp[mask]
dp = new_dp
return dp[0]
7.3 双向BFS / Meet-in-the-Middle
对于 n 较大的情况（如 n = 30 到 40），完全枚举 2^n 状态不可行。此时可以结合 Meet-in-the-Middle 思想，将状态空间分成两半独立计算，再合并结果。
# Meet-in-the-Middle 在状压DP中的应用
# 示例：集合划分问题 - 将集合划分为两个子集，使两部分和之差最小
def min_partition_diff(nums):
"""将 nums 分成两组，使两组和之差最小"""
n = len(nums)
half = n // 2
# 计算前半部分所有子集的和
left_sums = []
for mask in range(1 << half):
s = 0
for i in range(half):
if (mask >> i) & 1:
s += nums[i]
left_sums.append(s)
# 计算后半部分所有子集的和
right_sums = []
for mask in range(1 << (n - half)):
s = 0
for i in range(n - half):
if (mask >> i) & 1:
s += nums[half + i]
right_sums.append(s)
# 排序后半部分，便于二分查找
right_sums.sort()
total = sum(nums)
ans = total
# 对于前半部分的每个和，在右半部分找最接近 total/2 - s 的值
import bisect
for s in left_sums:
target = total // 2 - s
idx = bisect.bisect_left(right_sums, target)
for k in [idx, idx - 1]:
if 0 <= k < len(right_sums):
diff = abs(total - 2 * (s + right_sums[k]))
ans = min(ans, diff)
return ans
Meet-in-the-Middle 优化效果：将枚举量从 O(2^n) 降低到 O(2^(n/2))。对于 n=40，2^40 ≈ 1 万亿次运算是不可行的，但 2^20 ≈ 100 万，完全可以在 1 秒内完成。
八、复杂度分析
8.1 时间复杂度
状压DP的时间复杂度分析通常遵循以下规律：
- 基础状压DP：O(2^n × n) 或 O(2^n × n^2)，如 TSP 问题（O(n^2 × 2^n)）
- 子集枚举型DP：O(3^n)，因为 ∑ C(n,k) × 2^k = 3^n。典型问题：图着色、集合覆盖
- 按行递推型DP：O(n × 状态数 × 转移数)，棋盘覆盖问题
- Meet-in-the-Middle：O(2^(n/2) × n)，适用于 n 在 30-40 范围内的拆分问题
8.2 空间复杂度
空间复杂度决定了状压DP的可行性边界：
- 一维DP（只用 mask）：O(2^n)，可支持 n ≤ 25（2^25 × 8 bytes = 256 MB）
- 二维DP（mask + 位置）：O(n × 2^n)，可支持 n ≤ 20（2^20 × 20 × 8 ≈ 160 MB）
- 滚动数组优化：O(2^n)，常见于逐行递推的棋盘问题
可行性边界速查表（以 Python 为例，单测例 2 秒时限）：
- n ≤ 12：暴力搜索或全排列即可
- n ≤ 20：标准状压DP的最佳区间，二维DP安全
- n ≤ 25：需要一维DP或滚动数组，且需预处理优化
- n ≤ 40：需要 Meet-in-the-Middle 或折半搜索
- n > 40：需要结合贪心/近似算法或其他范式
九、核心要点总结
知识体系一览
- 状态压缩的本质：用二进制位表示集合状态，将高维状态映射为一维整数，利用位运算实现高效状态转移
- 基础操作：判断位、设置位、清除位、翻转位、统计1的个数、lowbit 提取
- 枚举技巧：子集枚举 (sub-1)&mask、超集枚举 (sup+1)|mask、Gosper's Hack 组合数枚举
- 经典应用：TSP（O(n^2×2^n)）、图着色（O(3^n)）、棋盘覆盖（逐行递推）、插头DP（逐格递推）
- 优化手段：预处理合法状态（减少无效枚举）、滚动数组（降低空间）、Meet-in-the-Middle（拆分大n）
- 复杂度边界：n ≤ 20 使用标准状压DP，n ≤ 25 需空间优化，n ≤ 40 使用折半搜索
学习建议：
- 从TSP入手：TSP是状压DP的最标准入门题，理解后可以推广到其他问题
- 熟记位运算模板：子集枚举、lowbit、bit_count 是最常用的三个操作
- 善用Python特性：Python 的无限精度整数使得状态压缩可以轻松扩展到 64 位以上，但要注意
bit_count() 的硬件加速优势
- 练习路径：TSP → 图着色 → 棋盘覆盖 → 插头DP，由易到难循序渐进
- 注意剪枝：有效的剪枝可以减少 90% 以上的状态枚举，是状压DP实用化的关键
十、进一步思考
状压DP是动态规划领域中连接"可解"与"不可解"的重要桥梁。它通过二进制编码将指数级状态空间压缩到内存可承受的范围内，使得许多原本只能暴力搜索的NP问题在小规模下有了确定性解法。
在实际应用中，状压DP的局限性在于它的指数级复杂度——即便经过各种优化，n 仍然被限制在 20-25 的范围内。但正是这种边界，促使算法设计者提出了分支定界、启发式搜索、局部搜索、近似算法等一系列替代方案，构成了算法设计的完整图谱。
对于希望在算法竞赛或面试中脱颖而出的同学，状压DP是必须掌握的核心技能之一。它不仅是一种技术，更是一种思维范式——教会我们如何用有限的资源（位运算）来表达复杂的状态空间，这正是计算机科学的精髓所在。
后续学习方向：
- 高级插头DP（连通性问题、Hamilton路径计数）
- 状态压缩与矩阵快速幂的结合（线性递推加速）
- 概率型状压DP（期望DP + 状态压缩）
- 状压DP与其他算法的融合（如二分图匹配中的状压优化）