状态压缩DP

状压 DP

一、什么是状压 DP？

• 记忆化搜索（递归 + 记忆）
• 多阶段决策型 DP（由前一阶段转移到下一阶段）

状压 DP 属于第二类：通过保存每一个阶段的"状态"，由旧状态推导新状态，最终得到最优解或统计结果。



二、什么是「状态压缩」？





1. 状态压缩的本质



状态压缩就是：用尽可能小、尽可能高效的数据结构，表示一个状态。

在绝大多数状压 DP 中：

• 使用 二进制数
• 用 0 / 1 表示某个对象的状态

例如：



二进制位	含义
0	未选 / 未访问 / 未放置
1	已选 / 已访问 / 已放置



若有 $n$ 个对象，则一个 $n$ 位二进制数即可表示一个状态。



2. 为什么通常用二进制？



• 二进制天然对应 "是 / 否"
• CPU 对位运算支持极快
• 一个 int 就可以表示最多 $32$ 个状态单元
• 一个 long long 可以表示最多 $64$ 个状态单元



如果每个单元有 $3$ 种状态，也可以用三进制压缩，但实现与效率都会明显变差，竞赛中极少使用。





三、什么时候适合使用状压 DP？



状压 DP 的适用条件可以总结为以下四点：

1. 状态本身需要被保存（有 DP 属性）

• 问题需要保存"之前做过哪些选择"
• 且当前决策依赖这些历史选择
• 具有 最优子结构

2. 状态单元只有少数几种取值（通常是 0 / 1）
例如：

• 点是否访问
• 格子是否放棋子
• 任务是否完成
• 元素是否被选中

3. 状态单元数量较小

• $n \leq 20$：非常安全
• $n \leq 22$：勉强可行
• $n \geq 25$：通常不可行

这是因为状态数为：
$$ \text{状态数} = 2^n $$



四、状压 DP 的典型应用场景





1. 棋盘 / 格子覆盖类问题



• 放棋子 / 不放棋子
• 相邻格子不能冲突
• 一行一行或一列一列推进

常见于：

• 棋盘覆盖
• 放炮 / 放士兵 / 放国王
• "相邻不能同时为 1"



2. 路径与排列问题（如 TSP）



• 访问哪些点
• 当前在什么位置
• 顺序很重要

经典代表：

• 旅行商问题（TSP）
• Hamilton 路径 / 回路



3. $N$ 很小但状态复杂的问题



• 原问题维度大
• 但某一维非常小
• 可以"指数换多项式"



五、状压 DP 的基本状态设计





1. 常见 DP 形式



• 一维状态：$dp_{mask}$

表示状态为 $mask$ 时的最优值 / 方案数

• 二维状态（最常见）：$dp_{mask,i}$

表示：

- 当前状态集合为 $mask$
- 额外信息是 $i$（如当前位置、最后选的点）



2. 状态转移的两种基本方向



• 从小集合到大集合：
$$ dp_{mask \ | \ (1 \ll k)} \leftarrow dp_{mask} $$

• 从大集合到小集合：
$$ dp_{mask} \leftarrow dp_{mask \ \oplus \ (1 \ll i)} $$



六、典型「状压 DP 模板」解析（棋盘类）





int n;
int maxn = 1 << n;  // 总状态数

for (int i = 1; i <= m; ++i) {        // 枚举阶段（如第 i 行）
    for (int j = 0; j < maxn; ++j) {   // 当前状态
        if (当前状态合法) {
            for (int k = 0; k < maxn; ++k) {  // 上一个状态
                if (上一个状态合法 &&
                    当前状态与上一个状态不冲突) {
                    dp[i][j] = 转移(dp[i-1][k]);
                }
            }
        }
    }
}



模板含义总结：

• $i$：阶段（行 / 层 / 时间）
• $j$：当前阶段的状态
• $k$：上一阶段的状态
• 合法性与冲突判断通常通过位运算完成



七、位运算基础（状压 DP 的数学工具）





1. 位运算符说明





运算	含义	特性
&	与	相同为 1
`\	`	或	有 1 为 1
^	异或	不同为 1
~	取反	0 ↔ 1
<<	左移	×2
>>	右移	÷2





2. 常用位运算技巧（非常重要）





① 判断第 $i$ 位是否为 1





if (x & (1 << (i-1)))





② 将第 $i$ 位设为 1





x |= (1 << (i-1));





③ 将第 $i$ 位设为 0





x &= ~(1 << (i-1));





④ 删除最右侧的 1（经典）





x = x & (x - 1);



常用于：

• 枚举子集
• 统计 1 的个数
• 快速遍历 mask 中的元素

---



状压 DP 的典型问题分类与解题总结





一、路径 / 排列类问题（TSP / Hamilton）





1. 问题识别特征



看到以下关键词，高度怀疑是状压 DP：

• "访问每个点恰好一次"
• "经过所有城市 / 节点"
• "路径 / 回路最短（或最多）"
• $n \leq 20$ 左右

本质特征：顺序重要 + 子集状态 + 终点有关



2. 常见题型



• 旅行商问题（TSP）
• Hamilton 路径 / 回路（最短 / 计数）
• 访问所有特殊点的最短路径
• 从起点出发访问全部点（不一定回到起点）



3. 典型状态设计



$$ dp_{mask,i} $$

含义：

• $mask$：已经访问的点集合
• $i$：当前所在的点（最后一个访问的点）



4. 核心转移方程



从小集合到大集合：
$$ dp_{mask \ | \ (1 \ll j), j} = \min(dp_{mask,i} + cost_{i,j}) $$

或从大集合反推：
$$ dp_{mask,i} = \min(dp_{mask \ \oplus \ (1 \ll i), j} + cost_{j,i}) $$



二、棋盘覆盖 / 相邻约束类问题（行 DP + 状压）





1. 问题识别特征



题目常具有：

• 棋盘 / 网格结构
• 一行一行 / 一列一列处理
• 相邻格子不能同时放置
• $n$（列数）很小，$m$（行数）较大

本质特征：局部约束 + 分阶段推进



2. 常见题型



• 棋盘放棋子（炮、士兵、国王）
• 覆盖问题（不能相邻）
• 农田放牛 / 种地
• 国王不相邻问题



3. 典型状态设计



$$ dp_{row,mask} $$

含义：

• $row$：当前处理到第几行
• $mask$：这一行的放置状态



4. 合法性与转移



行内合法：



(mask & (mask << 1)) == 0



行间不冲突：



(mask & prev_mask) == 0



转移：
$$ dp_{row,mask} += dp_{row-1,prev\_mask} $$



三、匹配 / 配对类问题（小规模）





1. 问题识别特征



• $n$ 为偶数
• 要求"两两配对"
• 每一对有代价 / 权值
• $n \leq 20$ 左右

本质特征：集合中元素两两消除



2. 常见题型



• 最小完美匹配（$n$ 小）
• 组队 / 配对问题
• 拆分为若干二元组



3. 典型状态设计



$$ dp_{mask} $$

含义：

• $mask$：已经被配对的元素集合



4. 核心转移思路



1. 找到 $mask$ 中第一个为 $0$ 的 $i$
2. 枚举另一个未配对的 $j$
3. 把 $i$ 和 $j$ 一起加入 $mask$

$$ dp_{mask \ | \ (1 \ll i) \ | \ (1 \ll j)} = \min(dp_{mask} + cost_{i,j}) $$



四、子集划分 / 分组类问题





1. 问题识别特征



• 把元素划分成若干组
• 每一组要满足条件
• 组的顺序不重要
• $n \leq 20$

本质特征：子集拆分 + 子集 DP



2. 常见题型



• 集合分组最优
• 覆盖问题
• 每组贡献一个 $cost$



3. 典型状态设计



$$ dp_{mask} $$

表示：

• $mask$ 表示"还未处理"的元素

4. 核心转移方式