Skip to main content

状态压缩动态规划

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

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

练习题​

LC464 - 我能赢吗（题解）​

LC465 - 最优账单平衡（题解）​

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

提示一

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

提示二

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

LC691 - 贴纸拼词（题解）​

提示

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

LC864 - 获取所有钥匙的最短路径（题解）​

LC1349 - 参加考试的最大学生数（题解）​

注意

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

LC1371 - 每个元音包含偶数次的最长子字符串（题解）​

LC1434 - 每个人戴不同帽子的方案数（题解）​

提示

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

LC1494 - 并行课程 II​

LC1595 - 连通两组点的最小成本（题解）​

注意

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

LC1723 - 完成所有工作的最短时间（题解）​

提示

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

LCP13 - 寻宝（题解）​

提示

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

ABC152F - Tree and Constraints​

提示

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

ABC195F - Coprime Present​

提示

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