状态压缩动态规划：用二进制位来记忆状态

你有没有想过，用一个数字就能记住一套完整的“选择题答案”？比如去超市购物，5样东西每样买或不买，就能写成 10100 这样一串0和1。状态压缩动态规划（状压DP）就是利用二进制数来高效地表示和转移状态，专门解决“集合”或“子集”类的组合优化问题。当物品数量较小（通常 n ≤ 20）时，它能把指数级的枚举压缩成可计算的动态规划。

为什么需要“二进制编码”？

先回忆一下，普通动态规划的状态往往是一维或二维的，比如“前i件物品的最大价值”。但有些问题中，我们需要同时知道“哪些物品已经用过了”，这时候状态数量是指数级的（2^n）。但巧的是，每个物品只有“选”或“不选”两种状态，正好对应二进制位的0和1。于是我们就可以用一个整数来表示所有物品的选择情况，这个整数叫做 掩码（mask）。

生活例子： 你有4个游戏金币，每个金币只能使用一次，你需要在闯关时决定使用哪些金币。所有可能的用法有16种（2^4）。状压DP会把每种用法（比如用了第1、3个金币）编码成二进制 1010（从右往左第0位开始），即十进制10，然后用dp[10][...]来记录此时的状态。

常用位运算技巧

由于状态存在一个整数里，需要用位运算来操作。下面几个操作是状压DP的“基础工具”：

1. 表示所有状态总数

(1 << n) 表示2^n，即所有可能的状态数。例如n=3时，1<<3=8，状态从0到7。

2. 检查某一位是否为1（某物品是否被选）

mask & (1 << k)
如果结果非0，则第k位为1，即第k个物品已被选择。
例子： mask=5（二进制0101），检查第2位（从0开始）：(5 & (1<<2)) = 5 & 4 = 4，非0，说明第2个物品（即第3个）被选了。

3. 把某一位设为1（选择物品）

mask | (1 << k)
例子： mask=5（0101），想选第1个物品（第1位）：5 | (1<<1) = 5 | 2 = 7（0111）。

4. 把某一位设为0（取消选择）

mask & ~(1 << k)
例子： mask=7（0111），取消第1位：7 & ~(1<<1) = 7 & ~2 = 7 & 5 = 5（0101）。

5. 枚举一个状态的所有子集（重要技巧）

for (int sub = state; sub; sub = (sub - 1) & state) {
    // 对子集 sub 进行处理
}

这个循环会遍历 state 的所有非空子集（包括state本身）。例如state=5（101），子集有5（101）、4（100）、1（001）。它效率很高，每个子集恰好枚举一次。

核心思想：状态设计与转移

状压DP的关键是把“当前选了哪些物品”作为一维状态，有时还需要另一维来表示“最后的位置”或“当前背包容量”等。常见的状态定义：

dp[mask]：只考虑mask中的物品时，某个最优值。
dp[mask][last]：已经选了mask中的物品，并且最后一个选定的是 last 时的最优值（如最短Hamilton路径）。

转移时，从当前mask出发，尝试加入一个还没选的新物品，更新新状态。

新手容易犯的错误

位运算优先级搞错
mask & (1<<k) 外围的括号不能少。写成 mask & 1<<k 会先计算 mask & 1，然后左移，结果完全错误。建议养成加括号的习惯。
忘记初始化
通常要将 dp 数组初始化为极大值（如 0x3f3f3f3f），然后把起点状态（如只包含第0个物品）设为0。漏掉这一步会导致答案错乱。
下标搞反
二进制位从右往左是第0位、第1位……对应物品0、1、2……。小心别把第k个物品对应 1<<k 写成 1<<(k-1)。
循环顺序不对
在最短路径问题中，外层循环必须是 mask 从小到大，这样才能保证在转移时，dp[mask][last] 已经被计算好。如果把 last 循环放在外层，可能会使用还未更新的状态。
范围越界
如 dp[1<<n][n] 会导致数组越界，因为 1<<n 是状态总数，但下标最大是 (1<<n)-1。数组大小的第二维也应是n。

完整示例：最短Hamilton路径（旅行商简化版）

问题：有n个城市（这里n=4），城市间的距离已知，从城市0出发，每个城市恰好经过一次，最后回到城市0，求最短路径长度。

我们选用 dp[mask][last] 表示已经走过mask中的城市，当前最后到达的是 last，且起点0已经包含在mask中。初始状态：dp[1][0]=0（只走了城市0）。转移：从当前状态尝试走到下一个未访问城市next，更新新状态。最后答案：遍历所有最后城市last（不含0），加上从last回到0的距离。

下面是带详细中文注释的完整代码：

#include <iostream>
#include <cstring>   // 用于 memset
#include <algorithm> // 用于 min
using namespace std;

const int INF = 0x3f3f3f3f;  // 一个很大的数，代表无穷大
int n = 4;                   // 城市数量
// 城市间距离矩阵，dist[i][j] 表示从 i 到 j 的距离
int dist[4][4] = {
    {0, 2, 9, 10},
    {1, 0, 6, 4},
    {15, 7, 0, 8},
    {6, 3, 12, 0}
};

// dp[mask][last]：已经访问过的城市集合为mask，最后停在last的最短路径长度
// mask 用二进制表示，第 i 位为1表示城市 i 已访问
int dp[1 << 4][4];   // 1<<4 = 16，状态总数16

int main() {
    // 初始化所有dp值为无穷大
    memset(dp, INF, sizeof dp);
    // 起点：只访问了城市0（mask=1），最后在0，距离为0
    dp[1][0] = 0;

    // 枚举所有访问状态（mask 从1到15）
    for (int mask = 1; mask < (1 << n); mask++) {
        // 枚举当前最后所在城市 last
        for (int last = 0; last < n; last++) {
            // 如果 last 不在 mask 中，跳过（不可能的状态）
            if (!(mask & (1 << last))) continue;
            // 尝试从 last 走到下一个城市 next
            for (int next = 0; next < n; next++) {
                // 如果 next 已经访问过，跳过
                if (mask & (1 << next)) continue;
                // 新状态：加入 next 城市
                int newMask = mask | (1 << next);
                // 更新更短路径
                dp[newMask][next] = min(dp[newMask][next],
                                        dp[mask][last] + dist[last][next]);
            }
        }
    }

    // 计算最终答案：必须访问所有城市（mask = (1<<n)-1），最后回到城市0
    int ans = INF;
    int fullMask = (1 << n) - 1;  // 所有位全为1，即15
    for (int last = 1; last < n; last++) {
        // 从 fullMask 状态，最后在 last，加上返回0的距离
        ans = min(ans, dp[fullMask][last] + dist[last][0]);
    }
    cout << "最短Hamilton路径长度: " << ans << endl;
    return 0;
}

输出结果：运行后得到13（具体路径：0 → 1 → 3 → 2 → 0）。

什么时候使用状压DP？

当问题涉及“子集”、“选择集合”、“顺序或排列”时。典型问题：最短Hamilton路径（旅行商）、任务分配、棋盘覆盖、集合划分等。
状态总数 2^n 必须可接受。一般n ≤ 20，最多22（再大会超内存或超时）。如果n=20，状态数约100万，再乘上n=20，约2000万操作，C++勉强能过。
如果n更大，需要考虑其他优化（如折半搜索、启发式算法）。

状态压缩动态规划：用二进制编码来记忆