数据结构与算法 - 动态规划（状态压缩）

发表于 2020-10-05 更新于 2021-11-07 分类于数据结构与算法

转载说明

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/dynamic-programming-2-plus/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

状态表示

状态压缩动态规划，是利用计算机二进制的性质来描述状态的一种动态规划方式。

例如：有一个大小为 n*n 的格子，我们可以在任意处放置物品，现在来描述一下某一行的某种状态：

设 n = 9；

有 9 位二进制数 101011011，每一位表示该格子是否被放置物品，1 表示放置了，0 表示没放置，这样一种状态就被我们表示出来了：

列 数   1   2   3   4   5   6   7   8   9
二进制  1   0   1   0   1   1   0   1   1
是否用  √   ×   √   ×   √   √   ×   √   √

对于一行的状态，一共有 1 << n 种。

现在我们得到了表示状态的方法，这里状态为集合中的各个元素选择情况，用二进制枚举了全部的状态，共 \(2^{n}\)。

状压其实是一种很暴力的算法，因为他需要遍历每个状态，所以将会出现 \(2^{n}\) 个状态数量，n 一般需要小于等于 20 才可以考虑。

不过有时可以先排除不合法的方案，使一行的总方案数大大减少从而使得用二进制枚举所有状态成为可能。

位运算

状态压缩动态规划中，状态是集合，对状态进行操作或访问也就是要对集合进行操作和访问。

为了更好的理解状压 dp，首先介绍位运算相关的知识。

与位运算相关的运算符共有 6 种，&，|，^，~，>>，<<

& 符号，x & y ，会将两个十进制数在二进制下进行与运算，然后返回其十进制下的值。
符号，x | y ，会将两个十进制数在二进制下进行或运算，然后返回其十进制下的值。
^ 符号，x ^ y ，会将两个十进制数在二进制下进行异或运算，然后返回其十进制下的值。
<< 符号，x << y 左移操作，将 x 在二进制下的每一位向左移动 y 位，最右边用 0 填充。
>> 符号，x >> y 右移操作，将 x 在二进制下的每一位向右移动 y 位，最左边用 0 填充。
~ 符号，~x ，按位取反操作，将 x 在二进制下的每一位取反，返回其十进制下的值

用位运算可以表示集合的常见操作，如下，其中 A,B 表示两个集合，c 表示某个元素。

c 插入 A ：A |= (1 << c)
A 删除 c ：A &= ~(1 << c)
A 置空：A = 0
并集：A | B
交集：A & B
全集：(1 << n) - 1
补集：((1 << n) - 1) ^ A
子集：(A & B) == B
判断是否是 2 的幂：A & (A - 1) == 0
最低位的 1 变为 0 ：n &= (n - 1)
最低位的 1：A & (-A)，最低位的 1 一般记为 lowbit(A)，表示 A 的二进制表达式中最低位的 1 所对应的值。

最高位的 1：

int p = lowbit(A)
while(p != A)
{
    A -= p;
    p = lowbit(A);
}
return p;

枚举 A 的子集：

for(subset = (A - 1) & A; subset != A; subset = (subset - 1) & A)
{
    ...
}

枚举全集的子集：

for(i = 0; i <= (1 << n) - 1; ++i)
{
    ...
}

旅行商问题

旅行商问题是状态压缩动态规划的经典问题，它的问题描述如下：

一个商人想要旅行各地并进行贸易。各地之间有若干条单向的通道相连，商人从一个地方出发，想要用最短的路程把所有地区环游一遍，请问环游需要的最短路程是多少？

如果在极端情况下也就是所有点之间都有连线的时候，对于每一个点来说，它可以选择的下一个位置一共有 n-1 种。那么一共可以选择的路线总共有 n! 种。

状态压缩的做法

要用动态规划的思路来解决这个问题，就要考虑状态定义和状态转移。

利用二进制可以用一个整数来表示一个集合的状态，我们很容易会把这个状态当成是动态规划当中的状态，但在这里是不全面的。单纯集合之间的转移没有限制条件，比如有 5 个球，已经拿了 1 号球和 2 号球，后面只要是剩下的球都可以拿，但是对于旅行商问题，有 5 个地方，我们已经去过了 1 和 2 两个地方，我们当前在位置 1，我们只能选与 1 相邻的地方来更新状态，也就是说状态转移是有限制的。

为了保证地点之间的移动顺序正确，我们还需要加上一维，也就是当前所处的位置。所以真正的状态是我们之前遍历过的位置的状态，加上当前所处的地点，这两者的结合。

状态定义
dp[s][i] := 已经选过 s 这些点，最后一个点是 i

状态转移
dp[s][i] = dp[s | (1 << j)][j] + w[i][j]; 从 i 点转移到 j 点，这里 j 可能已经在 s 中了

状态压缩动态规划的变化不多，以上 TSP 问题的分析过程和做法基本就是状态压缩动态规划的分析过程和做法了。

状态压缩动态规划主要的难点是想到用状态压缩动态规划做，下一节有 12 道练习题，通过这些题的练习，我们可以大致了解状态压缩动态规划的常见问题和问法。

状态压缩动态规划练习题

以下 12 道题是力扣上的状态压缩的习题，涵盖了状态压缩动态规划的常见套路。

安卓系统手势解锁
我能赢吗
不同路径 III —— 状态压缩 DP + 记忆化
划分为 k 个相等的子集 —— 状态压缩 DP + 记忆化
访问所有节点的最短路径 —— Floyd + 状态压缩 DP 求最短哈密顿路
最短超级串 —— 状态压缩 DP + DP 过程记录路径
优美的排列
骑士拨号器
参加考试的最大学生数
大礼包
贴纸拼词
按位与为零的三元组

何照江的博客