01.State-DP.md

1. 状态压缩 DP 简介

状态压缩 DP：简称为「状压 DP」，是一种应用在「小规模数据」的数组 / 字符串上，结合「二进制」的性质来进行状态定义与状态转移的动态规划方法。

我们曾在「位运算知识」章节中，学习过「二进制枚举子集算法」。这里先来回顾一下如何通过二进制枚举子集。

1.1 二进制枚举子集

对于一个元素个数为 $n$ 的集合 $S$ 来说，每一个位置上的元素都有选取和未选取两种状态。我们可以用数字 $1$ 来表示选取该元素，用数字 $0$ 来表示不选取该元素。

那么我们就可以用一个长度为 $n$ 的二进制数来表示集合 $S$ 或者表示 $S$ 的子集。其中二进制的每一个二进位都对应了集合中某一个元素的选取状态。对于集合中第 $i$ 个元素来说，二进制对应位置上的 $1$ 代表该元素被选取，$0$ 代表该元素未被选取。

举个例子，比如长度为 $5$ 的集合 $S = \lbrace 5, 4, 3, 2, 1 \rbrace$，我们可以用一个长度为 $5$ 的二进制数来表示该集合。

比如二进制数 $11111_{(2)}$ 就表示选取集合的第 $1$ 位、第 $2$ 位、第 $3$ 位、第 $4$ 位、第 $5$ 位元素，也就是集合 $\lbrace 5, 4, 3, 2, 1 \rbrace$，即集合 $S$ 本身。如下表所示：

集合 S 中元素位置	5	4	3	2	1
二进位对应值	1	1	1	1	1
对应选取状态	选取	选取	选取	选取	选取

再比如二进制数 $10101_{(2)}$ 就表示选取集合的第 $1$ 位、第 $3$ 位、第 $5$ 位元素，也就是集合 $\lbrace 5, 3, 1 \rbrace$。如下表所示：

集合 S 中元素位置	5	4	3	2	1
二进位对应值	1	0	1	0	1
对应选取状态	选取	未选取	选取	未选取	选取

再比如二进制数 $01001_{(2)}$ 就表示选取集合的第 $1$ 位、第 $4$ 位元素，也就是集合 $\lbrace 4, 1 \rbrace$。如下标所示：

集合 S 中元素位置	5	4	3	2	1
二进位对应值	0	1	0	0	1
对应选取状态	未选取	选取	未选取	未选取	选取

通过上面的例子我们可以得到启发：对于长度为 $5$ 的集合 $S$ 来说，我们只需要从 $00000 \sim 11111$ 枚举一次（对应十进制为 $0 \sim 2^5 - 1$）即可得到长度为 $5$ 的集合 $S$ 的所有子集。

我们将上面的例子拓展到长度为 $n$ 的集合 $S$。可以总结为：

• 对于长度为 $n$ 的集合 $S$ 来说，只需要枚举 $0 \sim 2^n - 1$（共 $2^n$ 种情况），即可得到集合 $S$ 的所有子集。

1.2 状态定义与状态转移

1.2.1 状态定义

在状压 DP 中，我们通常采用二进制数的形式来表示一维状态，即集合中每个元素的选取情况。

和「二进制枚举子集算法」一样，我们通过一个「 $n$ 位长度的二进制数」来表示「由 $n$ 个物品所组成的集合中所有物品的选择状态」。

二进制数的每一个二进位都对应了集合中某一个元素的选取状态。如果该二进制数的第 $i$ 位为 $1$，说明集合中第 $i$ 个元素在该状态中被选取。反之，如果该二进制的第 $i$ 位为 $0$，说明集合中第 $i$ 个元素在该状态中没有被选取。

1.2.1 状态转移

一般来说，状压 DP 的状态转移方式有两种：

1. 枚举子集：对于一个状态，枚举它的所有子集，或者枚举所有元素位置，找到比当前状态少选一个元素的子集。然后根据子集的值和状态之间的关系，更新当前状态的值。
2. 枚举超集：对于一个状态，枚举它的所有超集。然后根据超集的值和状态之间的关系，更新当前状态的值。

其中，最常用的是「枚举子集」的方式。

1.3 状压 DP 的使用条件

对于元素个数不超过 $n$ 的集合来说，一共会出现 $2^n$ 个状态数量。因为在 $n$ 变大时会呈现指数级增长，所以状态压缩 DP 只适用于求解小数据规模问题（通常 $n \le 20$）。当 $n$ 过大时，使用状态压缩 DP 可能会超时。

2. 状态压缩 DP 中常用的位运算

在状压 DP 中，一维状态是集合，对状态进行操作或者状态之间进行转移，也就是要对集合进行操作。

因为我们使用二进制数来定义集合状态，所以对集合进行操作，就是对二进制数进行位运算操作。

如下所示，其中 $n$ 为集合中的元素个数，$A$、$B$ 为两个集合对应的二进制数，$i$ 表示某个元素位置。

• 总状态数量：1 << n

• 在集合 $A$ 中加入第 $i$ 位元素（将二进制数第 $i$ 位赋值为 $1$）：A = A | (1 << i)

• 在集合 $A$ 中删除第 $i$ 位元素（将二进制数第 $i$ 位赋值为 $0$）：A = A & ~(1 << i)

• 判断集合 $A$ 是否选取了第 $i$ 位元素（判断二进制数第 $i$ 位是否为 $1$） ：if A & (1 << i): 或者 if (A >> i) & 1:

• 将集合 $A$ 设置为空集：A = 0

• 将集合 $A$ 设置为全集：A = 1 << n

• 求集合 $A$ 的补集：A = A ^ ((1 << n) - 1)

• 求集合 $A$ 与集合 $B$ 的并集：A | B

• 求集合 $A$ 与集合 $B$ 的交集：A & B

• 枚举集合 $A$ 的子集（包含 $A$）：

  subA = A						# 从集合 A 开始
  while subA > 0:					
      ...
      subA = (subB - 1) & A		# 获取下一个子集

• 枚举全集的所有子集：

  for state in range(1 << n):		# state 为子集
      for i in range(n):			# 枚举第 i 位元素
          if (state >> i) & i:	# 如果第 i 位元素对应二进制位 1，则表示集合中选取了该元素
              ...

3. 状态压缩 DP 的应用