说到进阶的动态规划，怎么能少了状态压缩动态规划（状压$DP$）呢。我们之前提到过，动态规划就和恋爱一般，一定要将自己的信息包括历史遗留问题交代清楚。但总是有问题很多信息很多的人存在的，我们状压DP就是用来解决这类问题的。

状态压缩动态规划

状压$DP$ 是动态规划的一种通过将状态压缩为整数来达到优化转移的目的的动态规划方法。在进行状压$DP$的时候，我们要把所有的压缩状态都看成是 $01$ 串，不管是 $23333$ 还是 $114514$ 我们都要把它们变成二进制来处理。所以要学习状压$DP$，我们肯定绕不开位运算来便利我们二进制的运算。下面就让我们一同来复习一下位运算吧。

位运算

位运算这块在平常的程序当中用的比较少，下面我们就以 $C++$ 为例，带同学们复习一下一些常用的位运算符号吧。

• << 左移：整个 $01$ 串左移一位，右边补 $0$，会丢弃最高位信息。
• >> 右移：整个 $01$ 串右移一位，左边补符号位(在补码意义下)，会丢弃最低位信息。
• | 或：同为 $0$ 时才为 $0$；
• & 与：同为 $1$ 时才为 $1$；
• ^ 异或：相同为 $0$，不同为 $1$，所以对于一位二进制的 $x$，我们可以用x ^ 1 将 $x$ 取反；
• ~取反：$0$ 变成 $1$，$1$ 变成 $0$。

具体到应用上，对于一位二进制数 $x$：

• 去掉最后一位：x >> 1；
• 在最后加一个 $0$：x << 1；
• 在最后加一个 $1$：(x << 1) | 1；
• 把最后一位变成 $1$：x | 1；
• 把最后一位变成 $0$：(x | 1) - 1 或 (x >> 1) << 1 或 x & 0xFFFFFFFE；
• 最后一位取反：x^1；
• 把右数第 $k$ 位变成 $1$：x | (1 << (k - 1))；
• 把右数第 $k$ 位变成 $0$：x & (~(1 << (k - 1)))；
• 把右数第 $k$ 位取反：x ^ (1 << (k - 1))；
• 取末 $k$ 位：x & ((1 << k) - 1)；
• 取右数第 $k$ 位：(x >> (k - 1)) & 1；
• 把末 $k$ 位变成 $1$：x | ((1 << k) - 1)；
• 把末 $k$ 位取反：x ^ ((1 << k) - 1)；
• 把右边连续的 $1$ 变成 $0$：x & (x + 1)；
• 把右起的第一个 $0$ 变成 $1$：x | (x + 1)；
• 把右边连续的 $0$ 变成 $1$：x | (x - 1)；
• 取右边连续的 $1$：(x ^ (x + 1)) >> 1；
• 去掉右起的第一个 $1$ 的左边：x & (-x)（$lowbit$）。

这边友情提示一下，位运算的优先级很复杂，为了方便起见，一定记得加上括号！！！

经典例题

互不攻击的车

问题描述：在 $n * n(n \le 20)$ 的方格棋盘上放置 $n$ 个车（可以攻击所在的行、列），求使它们不能互相攻击的方案数。

这道题作为引入非常简单，我们一行一行放置，则第一行有 $n$ 种放置的选择，第二行有 $n - 1$ 种放置的选择，……，最后一行只有 $1$ 种放置的选择。根据我们的乘法原理，我们的答案就是 $n!$。

那这道题和我们的状压$DP$有什么关系呢，别急看我对这道题做一点点变换。

问题描述：在 $n * n(n \le 20)$ 的方格棋盘上放置 $n$ 个车（可以攻击所在的行、列），某些格子有障碍不能放车，求使它们不能互相攻击的方案数。

这时就不能简单的排列组合了，数学的方法就得上容斥了，非常麻烦。所以我们来看看状压 $DP$ 的方法。我们知道这个车是需要一行一行放的，在放第 $i$ 行的时候，我们只关系哪些列已经被之前的车占据了，而不会去关心具体每一列由哪一行的车占据。所以我们可以用车占据列的情况作为状态，我们设某一列如果已经放了车则置为 $1$，否则置为 $0$。这样一个状态就可以用一个最多 $20$ 位的二进制数来表示。例如 $n = 5$，第 $1,3,4$ 列已经放置了车，则这个状态就可以表示为 $01101$（从右到左）。

那么我们另 $f[i][st]$ 表示前 $i$ 行状态为 $st$ 的方案数，那么就有 $f[i][st] = \sum f[i - 1][st']$，其中 $st'$是前继状态，也就是我们在第 $i$ 行第 $j$ 列放车，此时满足第 $i$ 行第 $j$ 列不是障碍点，并且 $(st' \& (1 << (j - 1))) == 0$ 并且 $st' + (1 << (j - 1)) == st$。记住我们一定要把状态看成 $01$ 串！举个例子，$f[3][01101]=f[2][00101] + f[2][01001] + f[3][01100]$。

这样我们就完成了这道题，是不是很简单呢？

互不侵犯

问题描述：在 $n * n(1 \le n \le 9)$ 的棋盘里放 $K(0 \le K \le n*n)$ 个国王，使得它们互不攻击，共有多少种摆放方案。国外能攻击到它的上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。

首先最简单的我们可以搜索，但是格子数量挺多，会 $TLE$。然后我们考虑一般的动态规划，我们一个一个格子拓展，好像也很难设计出无后效性的转移方案，所以我们还是考虑放国王的过程。

由于一行可以放很多个国王，所以一个一个放国王的话就不太好写了。我们考虑一行一行来放国王。这时我们对于第 $i$ 行，能放几个国王放在哪，都和前一行国王的位置有关，所以我们关心的是上一行放国王的位置。那我们如何表示每一行的状态呢？没错就是用 $01$ 串。由于每一行的格子小于等于 $9$ 个，每一个格子又只有两种状态——放国王和不放国王，假设我们把放国王的记为 $1$，没有放国王的记为 $0$，很显然每一行的状态就是一个 $01$ 串，如果我们把这个串看成一个二进制数，那这个数就会小于等于 $2^9-1$。

那么我们就可以拿一个 $int$ 类型来表示每一行的状态。那怎么样的状态才是合法的呢？很简单，不能有两个相邻的国王也就是不能有两个相邻的 $1$ 就行了。那怎么判断呢，其实也不难，只要 $(x \& (x << 1)) == 0$ 就可以了。那剩下就是我们枚举上一行的状态是 $x$，当前行的状态是 $y$，那当这两行的国王不会互相攻击也就是 $(x \& y) == 0$ 并且 $(x \& (y << 1)) == 0$ 并且 $(x \& (y >> 1)) == 0$就可以了。

具体到代码上，我们设 $f[i][j][k]$ 表示第 $i$ 行的状态为 $k$ 且已经放了 $j$ 个国王的方案数。接下来我们考虑怎么转移，其实就和我们上面讨论的一样，$f[i][j][k] += f[i - 1][j - num[k]][p]$，其中$(k \& p) == 0$ 并且 $(k \& (p << 1)) == 0$ 并且 $(k \& (p >> 1)) == 0$ 并且 $k$ 和 $p$ 都合法，$num[k]$ 表示 $k$ 这个状态中 $1$ 的数量也就是国王数。这样就完成这道题了。

炮兵阵地

问题描述：司令部的将军们打算在$N*M(N \le 100, M \le 10)$的网格地图上部署他们的炮兵部队。一个$N*M$ 的地图由 $N$ 行 $M$ 列组成，地图的每一格可能是山地（用"$H$" 表示），也可能是平原（用"$P$"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

这道题可以看成是上一道题的升级版，思路和上一题是比较类似的。我们还是沿用之前的思路，我们一行一行地去放炮兵部队。由于每一个炮可以打到两行，所以每一行的放置方法都和前两行的放置情况有关。所以我们设 $f[i][j][k]$ 表示第 $i$ 行的状态为 $j$，第 $i - 1$ 行的状态为 $k$ 时所用的最大炮兵数。我们接下来考虑如何转移，其实当转移到第 $i$ 行时，我们要枚举第 $i$ 行的状态 $j$，第 $i-1$ 行的状态 $p$，第 $i - 2$ 行的状态 $q$，则当 $j,p,q$ 均不互相发生冲突，且 $j,p,q$ 均是合法状态时，我们有 $f[i][j][p] = max(f[i][j][p], f[i - 1][p][q] + num[j])$。其中说 $j,p,q$ 均是合法状态是说任意一个 $1$ 的左右两遍两位都不能是 $1$。比如对于 $j$，我们要求 $((j \& (j >> 1)) == 0) \&\& ((j \& (j >> 2)) == 0)$，并且为 $1$ 的地方都是平原（也用位运算来判断）。比如 $010100$是不合法的，但是 $010001$ 是合法的。

但是如果我们枚举 $j,p,q$ 均从 $00000……0$ 枚举到 $11111……1$，是会超时的。所以我们先预处理出合法的 $01$ 串的数量，也就是任意一个 $1$ 的左右两遍两位都不能是 $1$ 的串数量，处理下来的数量在 $100$ 以内，这样我们只要每次枚举合法的状态再去判冲突就可以了。然后在开数组的时候我们 $f[i][j][k]$ 表示第 $i$ 行的状态为第 $j$ 个合法状态，第 $i - 1$ 行的状态为第 $k$ 个合法状态时所用的最大炮兵数，这样我们的空间也降下来了。

TSP问题

问题描述：旅行商问题（$Traveling$ $Saleman$ $Problem$， $TSP$）又译为旅行推销员问题、担货郎问题，简称为 $TSP$ 问题。

给你一张图（也可以是由若干点和边组成的抽象图），求从某个起点出发，经过且只经过一遍所有点的最短路径。

最简单的方法肯定是 $n!$ 的暴力，我们枚举出每个点到达的顺序然后计算和更新答案。我们下面如何考虑用状压 $DP$ 的方式来解答。

我们设 $f[st][i]$ 表示当前状态是 $st$，最后到达的一个点是 $i$ 时，所经过的最短距离。其中 $st$ 时一个 $01$ 串，表示走过点的信息。比如 $10110$ 从右往左看，代表的就是 $2,3,5$ 号点已经走过但 $1, 4$ 号点还没有走过的状态。我们能够用这样的状态来表示是因为，假如对于状态 $f[10110][3]$，也就是我们走过了 $2,3,5$ 号点，现在位于 $3$ 号点所经过的最短距离。我们其实只关心之前到达过 $2,5$ 号点，但其实不必关心具体的到达顺序时怎么样的。我们最后的答案就是 $min(f[11……1][1], f[11……1][2], ……,f[11……1][n])$。

下面我们考虑如何转移，其实很简单，就是 $f[st][i] = minn(f[st'][j] + a[j][i])$，其中 $st' + (1 << (j - 1)) == st$ 并且 $st' \& (1 << (j - 1)) == 0$，也就是 $st'$ 刚好比 $st$ 在第 $j$ 位少了一个 $1$。

我们举一反三，其实如果要求每个点恰好到达两次，那就用三进制就好了；同理如果每个点要恰好到达 $k$ 次，那我们就用 $k+1$ 进制来表示状态就好了。 当然我们一般会向上取整到 $2^x$ 进制，因为这样就是若干位 $2$ 进制，可以使用位运算来让我们整体的运算更加丝滑。

我们扩展一下，如果要求走完所有点回到原点怎么办。由于是一个环，所以从哪个点出发其实都是一样的，我们不妨从一号点出发，先求出 $f[11……1][2], f[11……1][3], ……,f[11……1][n]$，然后我们最后的答案就是 $min(f[11……1][2]+a[2][1], f[11……1][3]+a[3][1], ……,f[11……1][n]+a[n][1])$。

Most Powerful

问题描述：有不超过 $10$ 种气体，两两之间相互碰撞就会产生一定的能量。比如 $a$ 碰 $b$，那么 $b$ 气体就会消失并产生 $pow[a][b]$ 的能量。气体自己不能碰自己，问最后能得到的最大能量。

我们考虑我们对于某一状态还能产生的最大能量只与现在还存在哪些气体有关。所以我们设 $f[st]$ 表示状态 $st$ 时能获得的最大能量。 $st$ 的第 $k$ 位若等于 $1$ 则表示第 $k$ 个气体已经用了并消失了，为 $0$ 则表示没有用过或者用了但没消失。也就是我们只关心某个气体有没有消失而不关心它有没有碰撞过。我们下面考虑如何转移，我们之前都喜欢考虑前继状态怎么转移来，但在这题会比较难写。所以我们考虑如何贡献到后继状态，我们有 $f[k | (1 << (i - 1))] = max(f[k] + a[j][i])$，其中 $k \& (1 << (i - 1)) == 0$。也就是我们每次枚举一个要消失的气体 $i$ 和与它发生碰撞的气体 $j$ 进行转移。所以最后的答案就是 $max(f[1111……10], f[1111……01], …… , f[0111……11])$。

北大的算法讲座讲过动态规划分为人人为我型动态规划和我为人人型动态规划，而这题我们考虑如何贡献到后继状态显然就是我为人人型动态规划。

棋盘覆盖

题目描述：一个 $N * M(N,M \le 15)$的矩阵，用 $1*2$ 和 $2*1$ 的砖块密铺，问有多少种方法。

首先我们这道题时是将每块砖当成是它的最下点所在行铺设的，也就是下图中橙色是第一行铺设的，紫色是第二行铺设的，我们是将竖着的当成是它下底所在行铺设的所以假如我想放一个竖向砖块的时候，下面一位才记 $1$，上面一位记为 $0$。

所以我们在状态中留的 $0$ 都是给下一行竖向砖块补上的。换言之我们对上一行状态的 $01$ 串和下一行的 $01$ 串进行与运算，其中为 $0$ 的位置由于不会出现 0 & 0 只能是 0 & 1 就是我们要放竖向砖块的地方。除了竖向砖块，剩下的区域一定是偶数，这样才能用横向砖块铺满。

所以我们设 $f[i][st]$ 表示第 $i$ 行状态为 $st$ 的状态数，所以 $f[i][st] += f[i - 1][st']$，其中 $st | st' = 1111……1$，并且 $st \& st'$ 中的连续的 $1$ 的长度必须为偶数。

综合分析

纵观上面讨论的题目，几乎都是普普通通的一个递推公式或者状态转移方程，只不过其中的一维或者多维是压缩的，即把一个状态（一个方案、一个集合等）压缩成一个整数。

这本质上其实就是一个 $Hash$ 的过程，所以状压$DP$也被称为 $Hash$ $DP$ 或集合$DP$。所以我们不仅能 $Hash$ 成 $01$ 串，也能 $Hash$ 成别的其他东西，只不过 $01$ 串有位运算的加持方便和快捷了很多。

除去这一点区别，我们发现它和普通的$DP$没什么区别，都是从已有的状态推知到新的状态，所做的决策都没有后效性……虽然可能没有区间动态规划、背包之类的那么简单，但是本质还是维护信息，理清状态之间的转移方法。

那归根到底，我们为什么要使用状态压缩呢？这是一位一般的状态没办法满足我们的需求，我们在状态压缩当中的一个状态就包含了很多信息，而这些信息又可以压缩成一个二进制甚至 $k$ 进制数，更有甚者可能要用 $map$ 来做状态的映射。

那看到什么样子的问题要去考虑状压 $DP$ 呢？

• 在棋盘格子上的覆盖，并且至少有一维很小，能够状压；
• 类似于 $TSP$ 的路径问题；
• $N$ 比较小，变成 $n$ 位二进制后还很合理……

结语

其实状压$DP$包括后面要讲的数位$DP$往往出的题还没前面的区间$DP$或者背包这么难，因为要达到一样的区分度，现在的进阶$DP$可能只需要一个板子前面的往往需要比较巧妙的巧思，所以同学们千万不要害怕。最后希望你能有所收获，喜欢这篇BLOG！