状态压缩动态规划

状态压缩动态规划（英文一般称为bitmask DP），指的是一类使用二进制（也有使用三进制等的情形）数来表示动态规划中的状态的动态规划方法。其时间复杂度一般包含$2^N$或$3^N$（如果进行了子集枚举）的项，因此是指数而非多项式时间的算法。

在编程竞赛中，状态压缩动态规划的一个明显标志是题目中某一参数的上限为一个很小的常数（通常不超过20）。同时，题目中存在某种非此即彼的状态，比如工作是否完成，灯是否点亮，等式是否满足，数值的奇偶，等等。

练习题

LC464 - 我能赢吗 (opens new window)（题解 (opens new window)）

LC465 - 最优账单平衡 (opens new window)（题解 (opens new window)）

本题与BS - Minimum Number of Transfers to Settle Debts (opens new window)（English Editorial (opens new window)）是相同的。

提示一

如果$k$个人的总收支是0，则我们可以用最多$k-1$次操作使得其中每一个人的收支都变为0。因此，本题实际上就是要将这些人分成总收支为0的小组，且使得小组的数目最多。

提示二

预处理每一个分组的总收支后，进行状态压缩动态规划。注意这里需要用到枚举子集的方法。

LC691 - 贴纸拼词 (opens new window)（题解 (opens new window)）

提示

优化枚举顺序，可以减少重复计算，从而加快计算速度。

LC864 - 获取所有钥匙的最短路径 (opens new window)（题解 (opens new window)）

LC1349 - 参加考试的最大学生数 (opens new window)（题解 (opens new window)）

注意

本题有多项式时间的网络流解法。

LC1371 - 每个元音包含偶数次的最长子字符串 (opens new window)（题解 (opens new window)）

LC1434 - 每个人戴不同帽子的方案数 (opens new window)（题解 (opens new window)）

提示

表示帽子的状态（是否分配给了人）需要$2^{40}$个数，但注意到$N\leq10$，我们可以反过来表示人的状态（是否戴上了帽子），这样最多只有$2^{10}$个状态。

LC1494 - 并行课程 II (opens new window)

LC1595 - 连通两组点的最小成本 (opens new window)（题解 (opens new window)）

注意

本题有多项式时间的网络流解法。

LC1723 - 完成所有工作的最短时间 (opens new window)（题解 (opens new window)）

提示

二分答案 + 状态压缩动态规划。

LCP13 - 寻宝 (opens new window)（题解 (opens new window)）

提示

BFS预处理距离之后进行状态压缩动态规划。这里的状态为机关的打开情况。

ABC152F - Tree and Constraints (opens new window)

提示

最短路径 + 状态压缩动态规划。

ABC195F - Coprime Present (opens new window)（English Editorial）

提示

72以内的质数一共有20个。