2026-02-10
1 什么是状态压缩DP？
状态压缩动态规划（State Compression Dynamic Programming）:
一种巧妙地将多维状态压缩到单个整数中的算法技术。当我们需要处理那些状态可以表示为 “选中/未选中” 等二元选择的问题时，这种算法尤为有效。
核心思想：
用一个整数的二进制位来表示一个集合的状态，每位代表一个元素的两种状态。通过位运算，我们可以高效地进行状态转移和集合操作。
2 为什么需要状态压缩？
2.1 传统方法的局限性
考虑一个典型问题：
有n个城市，需要找到一条经过所有城市恰好一次的最短路径。朴素的方法是枚举所有可能的排列，时间复杂度为 \(O(n·n!)\) 当 \(n=20\) 时， \(20! ≈ 2.4 * 10^{18}\)，这个数字远超出计算机的处理能力
2.2 状态压缩的优势
通过观察发现，如果我们已经访问过某些城市，现在停留在某个城市，那么具体以什么顺序访问这些城市并不重要，重要的是：
- 我们已经访问了哪些城市
- 我们现在在哪个城市
这正是状态压缩的用武之地：
- 用 \(n\) 位二进制数表示 \(n\) 个城市的访问状态
- 这只需要 \(2^n\) 种状态，当 \(n=20\) 时，\(2^20 ≈ 10^6\)，这个数量级是计算机可以处理的
3 状态压缩DP的三大核心要素
3.1 状态设计
状态设计是状态压缩DP的关键，好的状态设计应该：
- 包含所有必要信息：状态必须包含所有影响未来决策的信息
- 尽可能简洁：不包含冗余信息
- 便于转移：能够方便地从其他状态转移而来
经典状态设计：dp[state][i]=val
state：二进制数，表示已访问的集合i：当前所在位置val：达到这种状态的最小代价
3.2 状态转移
状态转移是状态压缩DP的核心。我们需要找到从已知状态推导出未知状态的方法。
两种转移思路：
填表法（Pull DP）：
"我是从哪里来的？"
计算当前状态时，考虑所有可能到达当前状态的前驱状态
刷表法（Push DP）：
"我可以去哪里？"
从当前状态出发，更新所有可能到达的后继状态
两种方法各有优劣，填表法通常更直观，刷表法有时可以简化代码。
3.3 边界与目标
- 初始状态：通常是一个确定的状态，如起点、空集等
- 目标状态：通常是一个完整的状态，如访问所有点、达到目标条件等
5 从二进制到多进制
5.1 为什么需要多进制？
二进制只能表示两种状态，但有些问题需要更多状态：
- 三进制：每个元素有3种状态
- 例：每个城市最多访问2次
- 四进制：每个元素有4种状态
- 例：每个位置可以有4种不同的颜色
5.2 多进制状态的处理技巧
由于计算机没有内置的多进制位运算，我们需要手动实现：
关键操作：
- 获取第i位的值：\((state / base^i) % base\)
- 设置第i位的值：先清除原值，再设置新值
- 状态转移：检查当前值是否允许转移，然后更新