状态压缩动态规划

若元素数量比较小（不超过 20）时，想要存储每个元素取或不取的状态时，可以借助位运算将状态压缩。

需要借助状态压缩过程的动态规划就是状态压缩 DP（很多地方会简称为 状压 DP）。

取若干元素，也就是对应的位置记为 1，其余位置记为 0。例如，一共有 5 个元素 a,b,c,d,e，我们分别用 1,2,4,8,16 表示这五个元素，则集合 {a,c,e} 可以用 $(10101)_2$=21 来表示，而集合 {b,c,d} 可以用 $(01110)_2=14$ 表示。

对于元素个数为 nn 的情况，其空间复杂度为 $\mathcal{O}(2^n)$。

如果不用状态压缩，那么我们状态需要开 5 维的dp[2][2][2][2][2]，这样不仅使得代码的实现变的很复杂，并且当 n 的大小不一样的时候，状态维度也不一样，不是很容易实现。

控件复杂度和状态数量没有变，变的是状态的表达方式

例题

下面我们通过一个具体的题目来了解状态压缩动态规划。

n 个人在做传递物品的游戏,编号为 1-n。

游戏规则是这样的：开始时物品可以在任意一人手上，他可把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人。

即物品只能经过同一个人一次，而且每次传递过程都有一个代价；不同的人传给不同的人的代价值之间没有联系。

求当物品经过所有 n 个人后，整个过程的总代价是多少。

解析

我们就可以将“当前传递过物品的人的集合、最后一个传递到的人”作为状态进行动态规划，用dp[i][j]表示这个状态的最小代价。

这里，我们就要用到状态压缩：把“传递过物品的人的集合”压缩为一个整数。我们用二进制表示这个集合，比如一共5个人，第 0、3、4 个人被传递过（为了方便起见，序号从 0 开始），就用 $11001_{(2)}$表示，该集合的十进制表示为 25。

注意到 jj 是最后一个被传递到的人，也就是说必须在传递集合 ii 中标记为 11，即合法状态必须满足(i & (1 << j)) != 0。如果从 jj 传递到 kk，那 kk 必须不在集合 ii 里，即必须满足(i & (1 << k)) == 0。

转移方程为dp[i | 1 << k][k] = min(dp[i | 1 << k][k], dp[i][j] + a[j][k])， 其中a[j][k]为从 j 传递到 k 的代价。 其中i | (1 << k)是将第k个人加入集合i中

因为开始时物品可以在任意一人手上，所以把dp[1 << i][i]置为 00，其它状态置为无穷大。

总的时间复杂度为 \mathcal{O}(n^22^n)O(n22n)。