$（挖坑中，未完待续......）$

注：本文当前主要摘自 参考文献 1，后期可能会适当改写。

1. 前言

状态压缩 是 DP 的一个小技巧，一般应用在集合问题中（状压 DP 又叫 子集 DP(DP on Subsets)）。当 DP 状态 是 集合 时，把集合的组合或排列用一个 二进制整数 表示，这个二进制整数的 0/1 组合表示集合的一个 子集，从而把对 DP 状态 的处理转换为二进制的位操作，让代码变得简洁易写（注：相对集合操作而言），同时提高算法效率。从二进制操作简化集合处理的角度看，状态压缩 也是一种 DP 优化方法。

注：DP 优化的方法有很多，其中 状态压缩 是对 DP 状态表示 的优化~

2. 状压DP 经典问题 —— 最短哈密顿(Hamilton)路径问题

2.1 Hamilton 问题

状态压缩 DP 常常用 Hamilton（旅行商）问题作为引子。

最短 Hamilton 路径 - AcWing
问题描述：给定一个有权无向图，包括 $n$ 个点，标记 $0\sim n-1$，以及连接 $n$ 个点的边，求从起点 $0$ 到终点 $n-1$ 的最短路径。要求必须经过所有点，而且只经过一次。$1\le n\le 20$。
输入：第 $1$ 行输入整数 $n$。接下来 $n$ 行中，每行输入 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示点 $i$ 到点 $j$ 的距离，即为 $a[i,j]$。$0\le a[i,j]\le 10^7$。
输出：输出一个整数，表示最短 Hamilton 路径的长度。
时间限制：3s。

Hamilton 问题是 NP 问题，没有多项式复杂度的解法（注：这里说的可能不严谨，不过这不重要）。
先尝试暴力解法，枚举 $n$ 个点的全排列。共有 $n!$ 个全排列，一个全排列就是一条路径，计算每个全排列的路径长度，需要做 $n$ 次加法。在所有路径中找最短路径，总的时间复杂度为 $O(n\times n!)$。

PS：当 $n=20$ 时，$n!=2432902008176640000\approx 10^{18}$，$n\times n!=48658040163532800000\approx 10^{19}$ （前面的常数省了）~

2.2 DP 求解 Hamilton 问题

如果用状态压缩 DP 求解，能把时间复杂度降低到 $O(n^2\times 2^n)$。当 $n=20$ 时，$n^2\times 2^n=419430400\approx 10^8$，比暴力解法好很多了。下面介绍 状态压缩 DP 的做法。

首先定义 $\text{dp}$ 状态。设 $S$ 为图的一个子集，用 $\text{dp}[S][j]$ 表示集合 $S$ 内的最短 Hamilton 路径，即从起点 $0$ 出发，经过 $S$ 中的所有点，到达终点 $j$ 的最短路径（集合 $S$ 中包含 $j$ 点）。然后根据 DP 的思路，让 $S$ 从最小的子集逐步扩展到整个图，最后得到的 $\text{dp}[N][n-1]$ 就是答案，$N$ 表示包含图上所有点的集合。

如何求 $\text{dp}[S][j]$？可以从小问题 $S-j$ 递推到大问题 $S$。其中，$S-j$ 表示从集合 $S$ 中去掉 $j$，即不包含 $j$ 点的集合。

如何从 $S-j$ 递推到 $S$？设 $k$ 为 $S-j$ 中的一个点，把 $0\sim j$ 的路径分为两部分：$0\to 1\to \cdots \to k$ 和 $(k+1)\to \cdots \to j$。以 $k$ 为变量，枚举 $S-j$ 中的所有点，找出最短路ing，状态转移方程为：

集合 $S$ 初始时只包含起点 $0$，然后逐步将图中的点包含进来，直到最后包含所有点。这个过程用状态转移方程实现。

枚举集合 $S-j$ 中的所有点

上图可以解释上述原理。读者可以体会为什么用 DP 遍历路径比用暴力法遍历路径更有效率。其关键在于已经遍历过的点的顺序对以后的决策没有影响，这体现了 DP 的无后效性。

2.3 用状态压缩 DP 编码

以上是 $\text{dp}$ 状态设计，接下来是编码实现，最重要的是如何操作集合 $S$。这就是状态压缩 DP 的技巧：用一个二进制整数表示集合 $S$，把集合 $S$ “压缩” 到一个二进制整数中。这个二进制整数的每一位表示图上的一个点，等于 $0$ 表示 $S$ 不包含这个点，等于 $1$ 表示包含。例如，$S=00110101$，其中有 $4$ 个 $1$，表示集合中包含 $5,4,2,0$ 共 $4$ 个点。本题最多有 $20$ 个点，那么就定义一个 $20$ 位的二进制整数表示集合 $S$。

下面给出代码，第 $1$ 个 $for$ 循环有 $2^n$ 次，加上后面两个各 $n$ 次的 $for$ 循环，总的时间复杂度为 $O(n^2\times 2^n)$。

第 $1$ 个 $for$ 循环实现了从最小的集合扩展到整个集合。最小的集合为 $S=1$，它的二进制表示最后一位是 $1$，即包含起点 $0$；最大的集合是 $S=(1<<n)-1$，它的二进制表示中有 $n$ 个 $1$，包含了所有点。

算法最关键的部分是 “枚举集合 $S-j$ 中所有点”，是通过代码中的两个 $if$ 语句实现的：

• if ((S >> j) & 1)，判断当前集合 $S$ 中是否含有 $j$ 点；
• if ((S ^ (1 << j)) >> k & 1)，其中 S ^ (1 << j) 的作用是从集合 $S$ 中去掉 $j$ 点，得到集合 $S-j$，然后 >> k & 1 表示用 $k$ 遍历集合 $S$ 中的 $1$，这些 $1$ 就是 $S-j$ 中的点，这样就实现了 “枚举集合 $S-j$ 中所有点”。注意，S ^ (1 << j) 也可以写成 S - (1 << j)。

这两个语句可以写在一起：

if (((S >> j) & 1) && ((S ^ (1 << j)) >> k & 1))

不过，分开写效率更高。

#include<bits/stdc++.h>
using namespace std;
int n, dp[1 << 20][21];
int dist[21][21];
int main(){
    // 初始化为最大值
    memset(dp, 0x3f, sizeof(dp));
    cin >> n;
    // 输入图
    for (int i = 0; i < n; i ++)    
        for (int j = 0; j < n; j ++)
            // 输入点之间的距离
            cin >> dist[i][j];
    // 开始：集合中只有点 0，起点和终点都是 0
    dp[1][0] = 0;
    // 从小集合扩展到大集合，集合用 S 的二进制表示            
    for (int S = 1; S < (1 << n); S ++) 
        // 枚举点 j
        for (int j = 0; j < n; j ++)
            // (1) 这个判断与下面的 (2) 同时起作用
            if ((S >> j) & 1)
                // 枚举到达 j 的点 k，k 属于集合 S - j
                for (int k = 0; k < n; k ++)
                    // (2) k 属于集合 S - j，S - j 用 (1) 保证
                    if ((S ^ (1 << j)) >> k & 1)
                    // 把 (1) 和 (2) 写在一起更容易理解，但是效率低一些
                    // if (((S >> j) & 1) && ((S ^ (1 << j)) >> k & 1))
                        dp[S][j] = min(dp[S][j], dp[S ^ (1 << j)][k] + dist[k][j]);
    // 输出：路径包含了所有的点，终点是 n - 1
    cout << dp[(1 << n) - 1][n - 1];
    return 0;
}

3. 状压DP 其他例题

$（待补充......）$

4. 参考文献

1. 罗永军, 郭卫斌. 算法竞赛[M]. 北京: 清华大学出版社, 2022.
2. 李煜东. 算法竞赛进阶指南[M]. 郑州: 大象出版社, 2022.