状压 DP：用位运算驯服指数空间

当一个组合优化问题的状态空间是某个集合的所有子集时，我们面对的是一个大小为 2^n 的搜索空间。暴力枚举当然不可取，但如果 n 足够小（通常 n <= 20），我们可以把每个子集用一个 n 位整数（bitmask）来表示，从而在 O(2^n * poly(n)) 的时间内求解。这就是状态压缩动态规划（Bitmask DP），也常被简称为”状压 DP”。

状压 DP 的核心思想并不复杂：用一个整数的二进制位来编码集合的成员关系，第 i 位为 1 表示元素 i 在集合中，为 0 表示不在。这样，集合的并、交、差、补等操作全部归结为位运算——而位运算在现代 CPU 上只需一个时钟周期。

本文将从位运算基础出发，系统讲解 TSP（旅行商问题）、Steiner Tree（斯坦纳树）、SOS（子集和）、轮廓线 DP 等经典应用，并给出完整的 C++ 实现。

一、位运算操作复习

在进入状压 DP 之前，我们需要熟练掌握一组位运算操作。这些操作是状压 DP 的”汇编语言”。

1.1 基本操作

// 检查第 i 位是否为 1
bool has(int mask, int i) {
    return (mask >> i) & 1;
}

// 设置第 i 位为 1（加入元素 i）
int set_bit(int mask, int i) {
    return mask | (1 << i);
}

// 清除第 i 位（移除元素 i）
int clear_bit(int mask, int i) {
    return mask & ~(1 << i);
}

// 翻转第 i 位
int flip_bit(int mask, int i) {
    return mask ^ (1 << i);
}

1.2 枚举子集

枚举一个集合 mask 的所有子集（包括空集）是状压 DP 中最核心的技巧之一：

// 枚举 mask 的所有非空子集
for (int s = mask; s > 0; s = (s - 1) & mask) {
    // s 是 mask 的一个非空子集
}
// 注意：循环结束后 s = 0，即空集未被枚举
// 如果需要包含空集，可在循环外单独处理

这个循环的原理值得细细品味。s - 1 会把 s 的最低位的 1 变成 0，同时把它下面的所有 0 变成 1。然后 & mask 把不属于 mask 的位清零。这样每次迭代，s 严格减小，且始终是 mask 的子集。

时间复杂度分析：如果 mask 有 k 个 1，则它有 2^k 个子集。所有 mask 的子集枚举总次数为：

sum_{k=0}^{n} C(n,k) * 2^k = 3^n

这个等式来自二项式定理 (1+2)^n = 3^n。这是一个非常重要的复杂度，在 Steiner Tree 等问题中会反复出现。

1.3 popcount、lowbit 和 ctz

// popcount：统计二进制中 1 的个数
int popcount(int x) {
    return __builtin_popcount(x);
}

// lowbit：取最低位的 1（返回的是一个 2 的幂）
int lowbit(int x) {
    return x & (-x);
}

// ctz (count trailing zeros)：最低位 1 的位置
int ctz(int x) {
    return __builtin_ctz(x);
}

// clz (count leading zeros)：最高位 1 前面的 0 的个数
int clz(int x) {
    return __builtin_clz(x);
}

// 最高位 1 的位置（0-indexed）
int highest_bit(int x) {
    return 31 - __builtin_clz(x);
}

1.4 枚举所有大小为 k 的子集

有时我们需要枚举 {0, 1, …, n-1} 的所有大小恰好为 k 的子集。Gosper’s hack 提供了高效做法：

// 枚举 {0,...,n-1} 中所有大小为 k 的子集
void enumerate_k_subsets(int n, int k) {
    int mask = (1 << k) - 1;  // 最小的大小为 k 的子集
    while (mask < (1 << n)) {
        // 处理 mask
        process(mask);

        // Gosper's hack: 求下一个大小为 k 的子集
        int c = mask & (-mask);
        int r = mask + c;
        mask = (((r ^ mask) >> 2) / c) | r;
    }
}

Gosper’s hack 的原理是：找到最低位的 1（lowbit），加上它使得进位产生，然后把进位消耗掉的 1 重新排列到最低位。这保证了每次得到的 mask 恰好比前一个大，且 popcount 不变。

1.5 实用技巧汇总

操作	表达式	说明
判空	`mask == 0`	集合为空
全集	`(1 << n) - 1`	{0, 1, …, n-1}
补集	`((1 << n) - 1) ^ mask`	相对于全集的补
是否为子集	`(sub & mask) == sub`	sub 是否是 mask 的子集
是否恰有一个元素	`mask && !(mask & (mask-1))`	mask 是 2 的幂
去掉最低位的 1	`mask & (mask - 1)`	常用于迭代
仅保留最低位的 1	`mask & (-mask)`	lowbit

二、TSP：旅行商问题的精确解

旅行商问题（Traveling Salesman Problem，TSP）是组合优化的”果蝇”——它简单到任何人都能理解，却困难到至今没有多项式时间算法。给定 n 个城市和它们之间的距离，求经过每个城市恰好一次并返回起点的最短回路。

2.1 问题建模

设城市编号为 0, 1, …, n-1，dist[i][j] 表示城市 i 到城市 j 的距离。定义：

dp[mask][i] = 从城市 0 出发，访问了 mask 集合中的城市，当前停在城市 i 的最短路径长度

其中 mask 的第 j 位为 1 表示城市 j 已经被访问过。初始条件：dp[1][0] = 0（只访问了城市 0，停在城市 0，路径长度为 0）。

2.2 状态转移

dp[mask | (1 << j)][j] = min(dp[mask][i] + dist[i][j])

其中 i 必须在 mask 中（第 i 位为 1），j 不在 mask 中（第 j 位为 0）。

最终答案：

ans = min_{i=1}^{n-1} (dp[(1<<n)-1][i] + dist[i][0])

即遍历完所有城市后，从最后一个城市返回起点。

2.3 Held-Karp 算法

这个 DP 方案就是 Held 和 Karp 在 1962 年独立提出的算法（Bellman 也在同年独立发现），它将 TSP 的时间复杂度从 O(n!) 降到了 O(2^n * n^2)，空间复杂度为 O(2^n * n)。

让我们算一笔账：对于 n = 20，n! 约为 2.4 * 10^18，而 2^20 * 20^2 约为 4.2 * 10^8。这就是状压 DP 的威力——将阶乘级别的搜索压缩到指数级别。

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int tsp(int n, vector<vector<int>>& dist) {
    int full = (1 << n) - 1;
    // dp[mask][i]: 访问了 mask 中的城市，当前在城市 i 的最短路径
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0;  // 起点在城市 0

    for (int mask = 1; mask <= full; mask++) {
        for (int i = 0; i < n; i++) {
            if (dp[mask][i] == INF) continue;
            if (!(mask & (1 << i))) continue;  // i 必须在 mask 中

            // 尝试扩展到城市 j
            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) continue;  // j 不在 mask 中
                int next_mask = mask | (1 << j);
                dp[next_mask][j] = min(dp[next_mask][j],
                                       dp[mask][i] + dist[i][j]);
            }
        }
    }

    // 求回到起点的最短回路
    int ans = INF;
    for (int i = 1; i < n; i++) {
        if (dp[full][i] < INF) {
            ans = min(ans, dp[full][i] + dist[i][0]);
        }
    }
    return ans;
}

2.4 路径恢复

实际应用中，我们往往不仅需要最短路径的长度，还需要具体路径。可以通过记录前驱来恢复：

struct TSPSolver {
    int n;
    vector<vector<int>> dist;
    vector<vector<int>> dp;
    vector<vector<int>> parent;  // 记录前驱城市

    TSPSolver(int n, vector<vector<int>>& d)
        : n(n), dist(d),
          dp(1 << n, vector<int>(n, INF)),
          parent(1 << n, vector<int>(n, -1)) {}

    int solve() {
        int full = (1 << n) - 1;
        dp[1][0] = 0;

        for (int mask = 1; mask <= full; mask++) {
            for (int i = 0; i < n; i++) {
                if (dp[mask][i] == INF) continue;
                if (!(mask & (1 << i))) continue;

                for (int j = 0; j < n; j++) {
                    if (mask & (1 << j)) continue;
                    int nm = mask | (1 << j);
                    int cost = dp[mask][i] + dist[i][j];
                    if (cost < dp[nm][j]) {
                        dp[nm][j] = cost;
                        parent[nm][j] = i;
                    }
                }
            }
        }

        int ans = INF, last = -1;
        for (int i = 1; i < n; i++) {
            int cost = dp[full][i] + dist[i][0];
            if (cost < ans) {
                ans = cost;
                last = i;
            }
        }
        return ans;
    }

    vector<int> get_path() {
        int full = (1 << n) - 1;

        // 找最优终点
        int ans = INF, last = -1;
        for (int i = 1; i < n; i++) {
            int cost = dp[full][i] + dist[i][0];
            if (cost < ans) {
                ans = cost;
                last = i;
            }
        }

        // 回溯路径
        vector<int> path;
        int mask = full, cur = last;
        while (cur != -1) {
            path.push_back(cur);
            int prev = parent[mask][cur];
            mask ^= (1 << cur);
            cur = prev;
        }
        reverse(path.begin(), path.end());
        path.push_back(0);  // 回到起点
        return path;
    }
};

2.5 TSP 变体

TSP 有很多变体，状压 DP 都能处理：

开路 TSP（不需要回到起点）：答案改为 min(dp[full][i])。
有起点无终点：与上面相同。
有起点有终点：dp[1 | (1 << t)][t] 也可以作为初始状态，或者改造转移。
带权 TSP：每个城市有一个收益，求最大收益减去路径成本。
多旅行商：mTSP，需要更复杂的状态设计。

三、Steiner Tree：子集枚举的经典应用

斯坦纳树问题是另一个 NP-hard 问题：给定一个图 G 和一组”终端节点”T，求包含所有终端节点的最小权重连通子图（树）。

3.1 问题定义

给定无向图 G = (V, E)，边权非负，终端节点集 T = {t_0, t_1, …, t_{k-1}} 是 V 的子集。求一棵树，使得 T 中的所有节点都在树中，且边权总和最小。

如果 T = V，这就是最小生成树问题（多项式可解）。但当 T 是 V 的真子集时，问题变成 NP-hard。

3.2 DP 定义

设 |T| = k，|V| = n。定义：

dp[mask][v] = 连接 mask 对应的终端节点集合，以 v 为根的最小斯坦纳树的权重

其中 mask 是一个 k 位的二进制数，表示哪些终端节点需要被包含。

3.3 状态转移

转移有两种：

（1）合并子树（枚举子集）

dp[mask][v] = min_{sub ⊂ mask, sub ≠ ∅, sub ≠ mask} (dp[sub][v] + dp[mask ^ sub][v])

这里 sub 是 mask 的非空真子集，mask ^ sub 是补集。含义是：把连接 sub 的树和连接 mask的树在节点 v 处合并。

注意这里会有重复计算（sub 和 mask^sub 各算一次），所以实际只需枚举 sub 使得 sub 的最低位为 mask 的最低位即可避免重复。

（2）松弛（最短路扩展）

dp[mask][v] = min_{(u,v) ∈ E} (dp[mask][u] + w(u,v))

含义是：如果连接 mask 的最优树的根在 u，那么可以通过边 (u,v) 扩展到 v。

3.4 完整实现

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

struct Edge {
    int to, weight;
};

int steiner_tree(int n, vector<vector<Edge>>& adj, vector<int>& terminals) {
    int k = terminals.size();
    int full = (1 << k) - 1;

    // dp[mask][v]: 连接 mask 中终端节点，以 v 为根的最小权重
    vector<vector<int>> dp(1 << k, vector<int>(n, INF));

    // 初始化：单个终端节点
    for (int i = 0; i < k; i++) {
        dp[1 << i][terminals[i]] = 0;
    }

    for (int mask = 1; mask <= full; mask++) {
        // 阶段一：枚举子集合并
        for (int sub = (mask - 1) & mask; sub > 0; sub = (sub - 1) & mask) {
            int comp = mask ^ sub;
            if (sub < comp) continue;  // 避免重复
            for (int v = 0; v < n; v++) {
                if (dp[sub][v] < INF && dp[comp][v] < INF) {
                    dp[mask][v] = min(dp[mask][v],
                                      dp[sub][v] + dp[comp][v]);
                }
            }
        }

        // 阶段二：Dijkstra 松弛
        // 使用优先队列进行最短路扩展
        priority_queue<pair<int,int>, vector<pair<int,int>>,
                       greater<pair<int,int>>> pq;
        for (int v = 0; v < n; v++) {
            if (dp[mask][v] < INF) {
                pq.push({dp[mask][v], v});
            }
        }
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dp[mask][u]) continue;
            for (auto& [v, w] : adj[u]) {
                if (dp[mask][u] + w < dp[mask][v]) {
                    dp[mask][v] = dp[mask][u] + w;
                    pq.push({dp[mask][v], v});
                }
            }
        }
    }

    // 答案：dp[full][v] 的最小值
    int ans = INF;
    for (int v = 0; v < n; v++) {
        ans = min(ans, dp[full][v]);
    }
    return ans;
}

3.5 复杂度分析

子集枚举部分：对于每个 mask，枚举其所有子集，总次数为 3^k（前文已推导）。每次枚举还要遍历所有 n 个节点。总计 O(3^k * n)。
最短路松弛部分：对于每个 mask（共 2^k 个），运行一次 Dijkstra，时间 O((n + m) log n)。总计 O(2^k * (n + m) * log n)。
总复杂度：O(3^k * n + 2^k * (n + m) * log n)。

当 k <= 10 左右时（3^10 ≈ 59000），该算法在实践中是可行的。

四、SOS DP：高维前缀和

SOS（Sum over Subsets）DP 解决的是这样一个问题：给定一个长度为 2^n 的数组 f[]，对于每个 mask，求：

g[mask] = sum_{sub ⊆ mask} f[sub]

朴素做法是对每个 mask 枚举其所有子集，总复杂度 O(3^n)。但 SOS DP 可以在 O(n * 2^n) 内完成。

4.1 核心思想

SOS DP 本质上是一个高维前缀和。把 n 位二进制看作一个 n 维超立方体，每一维只有 0/1 两个取值。g[mask] 就是在这个超立方体上做”前缀和”。

回忆一维前缀和：对于数组 a[0..m]，前缀和 s[i] = sum_{j<=i} a[j]。二维前缀和用容斥原理展开。高维前缀和则是把每一维依次做一次前缀和。

4.2 实现

// SOS DP: g[mask] = sum of f[sub] for all sub ⊆ mask
void sos_dp(int n, vector<long long>& f) {
    // f 既是输入也是输出，原地计算
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < (1 << n); mask++) {
            if (mask & (1 << i)) {
                f[mask] += f[mask ^ (1 << i)];
            }
        }
    }
    // 现在 f[mask] = sum_{sub ⊆ mask} f_original[sub]
}

这段代码的思路是：外层枚举维度 i，内层枚举所有 mask。如果 mask 的第 i 位为 1，则 f[mask] += f[mask ^ (1<<i)]，即把第 i 位从 1 变成 0 对应的那个子集的值加上来。经过 n 轮迭代后，每个 f[mask] 就变成了它所有子集的和。

4.3 逆操作：莫比乌斯反演

SOS DP 的逆操作（从 g 恢复 f）就是莫比乌斯反演，只需把加法改成减法：

// 莫比乌斯反演：从 g 恢复 f
void mobius_inversion(int n, vector<long long>& g) {
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < (1 << n); mask++) {
            if (mask & (1 << i)) {
                g[mask] -= g[mask ^ (1 << i)];
            }
        }
    }
}

4.4 超集和

有时我们需要的是超集和而不是子集和：

h[mask] = sum_{mask ⊆ sup} f[sup]

实现也只需要小改动：

void super_sos(int n, vector<long long>& f) {
    for (int i = 0; i < n; i++) {
        for (int mask = (1 << n) - 1; mask >= 0; mask--) {
            if (!(mask & (1 << i))) {
                f[mask] += f[mask | (1 << i)];
            }
        }
    }
}

4.5 应用：容斥原理的高效计算

SOS DP 在容斥原理中有天然的应用。例如，计算”至少满足 mask 中一个条件”的方案数：

至少满足一个条件 = sum_{∅ ≠ sub ⊆ mask} (-1)^{|sub|+1} * f[sub]

通过 SOS DP，我们可以快速计算这类容斥式。

4.6 应用举例：整除子集

给定 n 个正整数，对于每个数，求有多少其他数是它的因子。将每个数分解质因数后，用 bitmask 表示其质因子集合，然后通过 SOS DP 求子集和。

// 求数组中每个数有多少个因子（在数组中出现的）
// 简化版：假设所有数都是前 k 个质数的积
void count_divisors(vector<int>& masks, int k) {
    int sz = 1 << k;
    vector<long long> cnt(sz, 0);

    // 统计每个 mask 出现的次数
    for (int m : masks) cnt[m]++;

    // SOS: cnt[mask] = 在 mask 所有子集中出现的总次数
    for (int i = 0; i < k; i++) {
        for (int mask = 0; mask < sz; mask++) {
            if (mask & (1 << i)) {
                cnt[mask] += cnt[mask ^ (1 << i)];
            }
        }
    }

    // cnt[mask] 就是 mask 的因子数量
}

五、轮廓线 DP：棋盘类问题的利器

轮廓线 DP（Profile DP）是状压 DP 在二维网格问题上的经典应用。它用一个 bitmask 来表示当前处理行与上一行之间的”轮廓线”状态，从而将二维问题降为一维扫描。

5.1 问题背景

考虑经典的骨牌覆盖问题：用 1x2 的骨牌完全覆盖一个 n x m 的棋盘，有多少种方案？

如果用暴力搜索，复杂度是指数级的。但如果 m 较小（比如 m <= 12），我们可以用轮廓线 DP 在 O(n * 2^m) 的时间内求解。

5.2 状态定义

我们逐列（或逐格）处理棋盘。定义轮廓线为当前已处理区域与未处理区域的边界。轮廓线上的每个位置，要么被之前放置的骨牌”占用”（从上方或左方伸出来），要么”空闲”。

用一个 m 位的 bitmask 表示轮廓线状态：第 j 位为 1 表示第 j 行的这个位置已被占用。

5.3 逐格转移

逐格转移（cell-by-cell）是轮廓线 DP 最通用的写法。我们按行优先顺序处理每个格子 (i, j)：

对于格子 (i, j)，轮廓线状态 mask 中第 j 位的含义：
- 1：(i-1, j) 放了一个竖骨牌，下半部分占据 (i, j)，格子已满
- 0：(i, j) 还未被占用

转移时有两种选择：

如果 mask 第 j 位为 1，说明上方有竖骨牌伸下来，(i,j) 已满。新状态中第 j 位变 0。
如果 mask 第 j 位为 0：
- 放一个竖骨牌（上半部分在 (i,j)，下半部分在 (i+1,j)）。新状态中第 j 位变 1。
- 如果 j > 0 且 mask 第 (j-1) 位为 0，放一个横骨牌。新状态中第 j 位仍为 0，第 (j-1) 位也为 0。

5.4 完整实现：骨牌覆盖

#include <bits/stdc++.h>
using namespace std;

long long domino_tiling(int n, int m) {
    if ((n * m) % 2 != 0) return 0;  // 奇数面积不可能

    // 确保 m 是较小的维度
    if (n < m) swap(n, m);

    // dp[mask]: 当前轮廓线状态为 mask 的方案数
    vector<long long> dp(1 << m, 0);
    dp[0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            vector<long long> ndp(1 << m, 0);

            for (int mask = 0; mask < (1 << m); mask++) {
                if (dp[mask] == 0) continue;

                // 情况 1：第 j 位为 1，上方有竖骨牌伸下来
                if (mask & (1 << j)) {
                    // 这个格子已被占用，清除第 j 位
                    ndp[mask ^ (1 << j)] += dp[mask];
                } else {
                    // 情况 2a：放竖骨牌（下半部分占 (i+1,j)）
                    if (i + 1 < n) {
                        ndp[mask | (1 << j)] += dp[mask];
                    }

                    // 情况 2b：放横骨牌（占 (i,j) 和 (i,j+1)）
                    if (j + 1 < m && !(mask & (1 << (j + 1)))) {
                        ndp[mask | (1 << (j + 1))] += dp[mask];
                    }

                    // 注意：不放骨牌不是合法选择（我们要完全覆盖）
                    // 但如果是破碎棋盘（有些格子不可放），则可以跳过
                }
            }

            dp = ndp;
        }
    }

    return dp[0];  // 所有格子都处理完，轮廓线全 0 表示合法
}

5.5 破碎棋盘

如果棋盘上有些格子被挖掉（不可放置骨牌），只需在转移时额外判断：遇到被挖掉的格子时，该格子必须跳过（即第 j 位视为 0，且不放任何骨牌）。

long long broken_board_tiling(int n, int m, vector<vector<bool>>& blocked) {
    if (n < m) {
        // 需要转置棋盘
        // 这里省略转置逻辑
    }

    vector<long long> dp(1 << m, 0);
    dp[0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            vector<long long> ndp(1 << m, 0);

            for (int mask = 0; mask < (1 << m); mask++) {
                if (dp[mask] == 0) continue;

                if (blocked[i][j]) {
                    // 被挖掉的格子：第 j 位必须为 0
                    if (!(mask & (1 << j))) {
                        ndp[mask] += dp[mask];
                    }
                    continue;
                }

                if (mask & (1 << j)) {
                    ndp[mask ^ (1 << j)] += dp[mask];
                } else {
                    if (i + 1 < n && !blocked[i + 1][j]) {
                        ndp[mask | (1 << j)] += dp[mask];
                    }
                    if (j + 1 < m && !(mask & (1 << (j + 1)))
                        && !blocked[i][j + 1]) {
                        ndp[mask | (1 << (j + 1))] += dp[mask];
                    }
                }
            }

            dp = ndp;
        }
    }

    return dp[0];
}

5.6 行压缩法

除了逐格转移，还有一种常见的写法是逐行转移：预处理出相邻两行之间所有合法的状态对，然后按行转移。这种方法更适合某些问题（如不相邻放置、国王放置等）。

// 示例：n x m 棋盘上放国王，使得没有两个国王相邻
// 状态：每行的放置方案用 bitmask 表示
long long king_placement(int n, int m) {
    // 预处理合法行状态：没有相邻的 1
    vector<int> valid;
    for (int mask = 0; mask < (1 << m); mask++) {
        if (!(mask & (mask << 1))) {  // 没有相邻的 1
            valid.push_back(mask);
        }
    }

    // 预处理兼容的行对
    int sz = valid.size();
    vector<vector<bool>> compat(sz, vector<bool>(sz, false));
    for (int a = 0; a < sz; a++) {
        for (int b = 0; b < sz; b++) {
            int va = valid[a], vb = valid[b];
            // 上下不相邻，左上右上也不相邻
            if ((va & vb) == 0 &&
                ((va << 1) & vb) == 0 &&
                ((va >> 1) & vb) == 0) {
                compat[a][b] = true;
            }
        }
    }

    // DP
    vector<long long> dp(sz, 1);  // 第 0 行
    for (int i = 1; i < n; i++) {
        vector<long long> ndp(sz, 0);
        for (int b = 0; b < sz; b++) {
            for (int a = 0; a < sz; a++) {
                if (compat[a][b]) {
                    ndp[b] += dp[a];
                }
            }
        }
        dp = ndp;
    }

    long long ans = 0;
    for (int a = 0; a < sz; a++) {
        ans += dp[a];
    }
    return ans;
}

六、Meet-in-the-Middle：将指数减半

Meet-in-the-Middle（折半搜索）是一种通用的优化技巧，可以将 O(2^n) 的搜索降到 O(2^{n/2})，代价是需要额外的排序或哈希查找。

6.1 基本思想

将 n 个元素分成两半 A 和 B，各含约 n/2 个元素。分别对 A 和 B 进行 2^{n/2} 的枚举，然后把两半的结果”拼接”起来。

6.2 经典应用：子集和问题

给定 n 个整数和目标值 target，判断是否存在一个子集的和等于 target。

bool subset_sum_mitm(vector<int>& a, long long target) {
    int n = a.size();
    int half = n / 2;

    // 枚举前半部分的所有子集和
    set<long long> left_sums;
    for (int mask = 0; mask < (1 << half); mask++) {
        long long s = 0;
        for (int i = 0; i < half; i++) {
            if (mask & (1 << i)) s += a[i];
        }
        left_sums.insert(s);
    }

    // 枚举后半部分，检查是否能与前半部分拼出 target
    int rest = n - half;
    for (int mask = 0; mask < (1 << rest); mask++) {
        long long s = 0;
        for (int i = 0; i < rest; i++) {
            if (mask & (1 << i)) s += a[half + i];
        }
        if (left_sums.count(target - s)) return true;
    }

    return false;
}

6.3 应用于 TSP

对于更大的 n（如 n = 36），标准 Held-Karp 已经不可行（2^36 ≈ 6.9 * 10^10）。但 Meet-in-the-Middle 可以把空间降到 O(2^{n/2})，虽然时间常数较大。

基本思路是：把城市分成两组，分别对每组求解 TSP，然后合并。具体实现较复杂，这里只给出框架思路：

1. 将 n 个城市分为 A（前 n/2 个）和 B（后 n/2 个）
2. 对 A 做 Held-Karp，记录 dp_A[mask_A][i][j]：
   访问了 mask_A 中的 A 城市，从 A 中的 i 出发到 A 中的 j
3. 对 B 做类似处理
4. 合并：枚举 A 和 B 的分割点，拼接路径

实际上，完整的 TSP Meet-in-the-Middle 需要更精细的状态设计。在竞赛中更常见的是用于子集和类问题。

6.4 更一般的分治框架

Meet-in-the-Middle 的思想不限于二分，也可以分成三份甚至更多。不过二分通常是最优的——更多的分割需要更复杂的合并步骤，且实际收益递减。

七、工程实践中的注意事项

状压 DP 在竞赛和工程中都有很多”坑”。以下是我总结的经验：

7.1 常见陷阱表

陷阱	说明	解决方案
内存爆炸	2^20 * 20 个 int = 80 MB	使用 short 或压缩存储；检查 n 的上界
整数溢出	1 << 31 是未定义行为	使用 `1LL << i` 或 `1u << i`
枚举顺序错误	mask 必须从小到大枚举	TSP 天然按 popcount 递增；SOS 需要注意方向
空集处理	`for(s=mask;s;s=(s-1)&mask)` 不含空集	循环外额外处理空集
n > 30 时 int 不够	int 只有 32 位	使用 long long（n <= 63）或 bitset
初始化遗漏	dp 数组未正确初始化为 INF 或 0	用 memset 或 fill 初始化
子集枚举重复	Steiner Tree 中 (sub, mask^sub) 和 (mask^sub, sub) 重复	限制 sub 包含 lowbit(mask)
缓存不友好	dp[mask][v] 的 mask 维度太大	交换维度顺序或分块处理
popcount 的平台兼容	__builtin_popcount 是 GCC 扩展	C++20 用 std::popcount；或手写

7.2 内存优化

当 n 较大时，2^n * n 的空间可能成为瓶颈。以下是一些优化方法：

滚动数组：如果 DP 转移只依赖于 popcount 较小的状态，可以按 popcount 分层，只保留相邻两层。

// TSP 按 popcount 分层（节省约一半内存，但实现更复杂）
// 通常不值得，除非内存非常紧张

位压缩值域：如果 DP 值的范围有限（如路径长度不超过 10000），可以用 short 代替 int：

vector<vector<short>> dp(1 << n, vector<short>(n, 30000));

稀疏表示：如果大部分 dp[mask][i] 都是 INF，可以用 hash_map 只存有效状态：

unordered_map<int, vector<int>> dp;
// 只存 dp[mask] 中有有效值的 mask

7.3 时间优化

预处理 popcount：频繁调用 __builtin_popcount 时，可以预处理到表中：

int pc[1 << 20];
void init_popcount(int n) {
    for (int i = 1; i < (1 << n); i++) {
        pc[i] = pc[i >> 1] + (i & 1);
    }
}

利用 lowbit 加速枚举：遍历 mask 中的所有 1 位：

for (int tmp = mask; tmp; tmp &= tmp - 1) {
    int i = __builtin_ctz(tmp);
    // i 是 tmp（也是 mask）的某个 1 位
}

这比逐位检查快，因为只迭代 popcount(mask) 次。

7.4 调试技巧

// 打印 mask 的二进制表示和对应集合
void debug_mask(int mask, int n) {
    printf("mask = %d, bits = ", mask);
    for (int i = n - 1; i >= 0; i--) {
        printf("%d", (mask >> i) & 1);
    }
    printf(", set = {");
    bool first = true;
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i)) {
            if (!first) printf(", ");
            printf("%d", i);
            first = false;
        }
    }
    printf("}\n");
}

八、综合实战：三道经典题

8.1 最短汉密尔顿路径

给定一个带权有向图，求从节点 0 到节点 n-1 的最短汉密尔顿路径（经过每个节点恰好一次）。

这与 TSP 的区别在于：不需要回到起点，且有固定的起点和终点。

int shortest_hamilton_path(int n, vector<vector<int>>& dist) {
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0;

    for (int mask = 1; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i))) continue;
            if (dp[mask][i] == INF) continue;

            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) continue;
                int nm = mask | (1 << j);
                dp[nm][j] = min(dp[nm][j], dp[mask][i] + dist[i][j]);
            }
        }
    }

    return dp[(1 << n) - 1][n - 1];
}

8.2 任务分配问题

有 n 个人和 n 个任务，cost[i][j] 表示第 i 个人完成第 j 个任务的代价。求将 n 个任务分配给 n 个人（每人恰好一个任务）的最小总代价。

这本质上是一个二分图最优匹配问题，可以用匈牙利算法 O(n^3) 求解，但也可以用状压 DP：

int assignment(int n, vector<vector<int>>& cost) {
    // dp[mask]: 前 popcount(mask) 个人已分配，分配了 mask 中任务的最小代价
    vector<int> dp(1 << n, INF);
    dp[0] = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] == INF) continue;
        int person = __builtin_popcount(mask);  // 下一个要分配的人
        if (person >= n) continue;

        for (int j = 0; j < n; j++) {
            if (mask & (1 << j)) continue;  // 任务 j 已被分配
            int nm = mask | (1 << j);
            dp[nm] = min(dp[nm], dp[mask] + cost[person][j]);
        }
    }

    return dp[(1 << n) - 1];
}

注意这里状态只有 dp[mask] 而不是 dp[mask][i]，因为 person 可以从 mask 的 popcount 推导出来。这把空间从 O(2^n * n) 降到了 O(2^n)。

8.3 集合覆盖问题

给定全集 U = {0, 1, …, n-1} 和 m 个子集 S_0, S_1, …, S_{m-1}，每个子集有一个代价。求代价最小的子集族，使得它们的并等于 U。

int set_cover(int n, int m, vector<int>& subsets, vector<int>& costs) {
    int full = (1 << n) - 1;
    vector<int> dp(1 << n, INF);
    dp[0] = 0;

    for (int mask = 0; mask <= full; mask++) {
        if (dp[mask] == INF) continue;
        for (int i = 0; i < m; i++) {
            int nm = mask | subsets[i];
            dp[nm] = min(dp[nm], dp[mask] + costs[i]);
        }
    }

    return dp[full];
}

这个 DP 简洁而有效，复杂度 O(2^n * m)。

九、SOS DP 进阶应用

9.1 计数问题：子集卷积

子集卷积（Subset Convolution）是 SOS DP 的一个高级应用。给定两个函数 f 和 g，定义卷积：

(f * g)[mask] = sum_{sub ⊆ mask} f[sub] * g[mask \ sub]

其中 mask sub = mask ^ sub（mask 减去 sub）。

与普通的子集和不同，这里要求 sub 和 mask不相交（它们的并才是 mask）。直接枚举子集是 O(3^n)，但通过引入 popcount 维度，可以在 O(n^2 * 2^n) 内完成。

// 子集卷积
// f_hat[k][mask] = sum of f[sub] where sub ⊆ mask and popcount(sub) == k
void subset_convolution(int n,
                        vector<long long>& f,
                        vector<long long>& g,
                        vector<long long>& result) {
    int sz = 1 << n;

    // 按 popcount 分层
    vector<vector<long long>> fh(n + 1, vector<long long>(sz, 0));
    vector<vector<long long>> gh(n + 1, vector<long long>(sz, 0));

    for (int mask = 0; mask < sz; mask++) {
        int pc = __builtin_popcount(mask);
        fh[pc][mask] = f[mask];
        gh[pc][mask] = g[mask];
    }

    // 对每一层做 SOS
    for (int k = 0; k <= n; k++) {
        for (int i = 0; i < n; i++) {
            for (int mask = 0; mask < sz; mask++) {
                if (mask & (1 << i)) {
                    fh[k][mask] += fh[k][mask ^ (1 << i)];
                    gh[k][mask] += gh[k][mask ^ (1 << i)];
                }
            }
        }
    }

    // 逐点乘积（按 popcount 做卷积）
    vector<vector<long long>> rh(n + 1, vector<long long>(sz, 0));
    for (int mask = 0; mask < sz; mask++) {
        for (int k = 0; k <= n; k++) {
            for (int j = 0; j <= k; j++) {
                rh[k][mask] += fh[j][mask] * gh[k - j][mask];
            }
        }
    }

    // 莫比乌斯反演还原
    for (int k = 0; k <= n; k++) {
        for (int i = 0; i < n; i++) {
            for (int mask = 0; mask < sz; mask++) {
                if (mask & (1 << i)) {
                    rh[k][mask] -= rh[k][mask ^ (1 << i)];
                }
            }
        }
    }

    // 提取结果
    result.assign(sz, 0);
    for (int mask = 0; mask < sz; mask++) {
        result[mask] = rh[__builtin_popcount(mask)][mask];
    }
}

9.2 AND/OR 卷积

如果卷积的定义改为 OR 卷积或 AND 卷积：

(f OR g)[mask] = sum_{a | b == mask} f[a] * g[b]
(f AND g)[mask] = sum_{a & b == mask} f[a] * g[b]

这两种卷积可以通过 SOS/超集和 + 逐点乘法 + 莫比乌斯反演在 O(n * 2^n) 内完成。

// OR 卷积
void or_convolution(int n, vector<long long>& f, vector<long long>& g,
                    vector<long long>& result) {
    int sz = 1 << n;
    result.resize(sz);

    // f 做子集和（莫比乌斯变换）
    vector<long long> F(f.begin(), f.end());
    vector<long long> G(g.begin(), g.end());

    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < sz; mask++) {
            if (mask & (1 << i)) {
                F[mask] += F[mask ^ (1 << i)];
                G[mask] += G[mask ^ (1 << i)];
            }
        }
    }

    // 逐点乘法
    for (int mask = 0; mask < sz; mask++) {
        result[mask] = F[mask] * G[mask];
    }

    // 莫比乌斯反演
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < sz; mask++) {
            if (mask & (1 << i)) {
                result[mask] -= result[mask ^ (1 << i)];
            }
        }
    }
}

十、状压 DP 与图论的结合

10.1 汉密尔顿路径计数

统计有向图中汉密尔顿路径的数量是一个典型的状压 DP 问题：

long long count_hamilton_paths(int n, vector<vector<bool>>& adj) {
    vector<vector<long long>> dp(1 << n, vector<long long>(n, 0));

    // 任意节点作为起点
    for (int i = 0; i < n; i++) {
        dp[1 << i][i] = 1;
    }

    for (int mask = 1; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i))) continue;
            if (dp[mask][i] == 0) continue;

            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) continue;
                if (!adj[i][j]) continue;
                dp[mask | (1 << j)][j] += dp[mask][i];
            }
        }
    }

    long long total = 0;
    int full = (1 << n) - 1;
    for (int i = 0; i < n; i++) {
        total += dp[full][i];
    }
    return total;
}

10.2 图着色问题

给定图 G，判断它是否可以用 k 种颜色着色（相邻节点颜色不同）。用状压 DP 可以在 O(2^n * n) 时间内判定。

关键观察：一个独立集（没有边连接的节点集合）可以涂同一种颜色。于是问题变成：能否把 V 分成 k 个独立集？

// 计算图的色多项式（chromatic number 的一般化）
int chromatic_number(int n, vector<vector<bool>>& adj) {
    // 预处理：对于每个子集 mask，判断它是否是独立集
    vector<bool> is_independent(1 << n, true);
    for (int mask = 0; mask < (1 << n); mask++) {
        // 检查 mask 中是否有相邻节点
        vector<int> nodes;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) nodes.push_back(i);
        }
        for (int a = 0; a < (int)nodes.size() && is_independent[mask]; a++) {
            for (int b = a + 1; b < (int)nodes.size(); b++) {
                if (adj[nodes[a]][nodes[b]]) {
                    is_independent[mask] = false;
                    break;
                }
            }
        }
    }

    // dp[mask]: 将 mask 中的节点用最少几种颜色着色
    vector<int> dp(1 << n, n + 1);
    dp[0] = 0;

    for (int mask = 1; mask < (1 << n); mask++) {
        // 枚举 mask 的所有非空子集作为独立集
        for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
            if (is_independent[sub]) {
                dp[mask] = min(dp[mask], dp[mask ^ sub] + 1);
            }
        }
    }

    return dp[(1 << n) - 1];
}

10.3 预处理独立集的优化

上面判断独立集的朴素方法是 O(2^n * n^2)。可以用增量法优化到 O(2^n * n)：

vector<bool> is_independent(1 << n, true);
vector<int> adj_mask(n, 0);  // adj_mask[i] = i 的邻居集合

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (adj[i][j]) adj_mask[i] |= (1 << j);
    }
}

for (int mask = 1; mask < (1 << n); mask++) {
    int v = __builtin_ctz(mask);  // mask 中最低位的节点
    int rest = mask ^ (1 << v);   // 去掉 v 后的子集
    // mask 是独立集 <=> rest 是独立集 且 v 与 rest 中的节点不相邻
    is_independent[mask] = is_independent[rest] &&
                           ((adj_mask[v] & rest) == 0);
}

十一、复杂度边界与适用范围

11.1 何时使用状压 DP

状压 DP 的适用条件：

n 足够小：通常 n <= 20（2^20 ≈ 10^6），极端情况下 n <= 25（需要特殊优化）。
状态可以用集合表示：问题的状态空间是某个 n 元集的幂集。
存在子结构：DP 的最优子结构性质成立。

11.2 复杂度速查表

算法	时间复杂度	空间复杂度	n 的实际上限
TSP (Held-Karp)	O(2^n * n^2)	O(2^n * n)	~20
任务分配	O(2^n * n)	O(2^n)	~23
Steiner Tree	O(3^k * V + 2^k * V * E)	O(2^k * V)	k~10
SOS DP	O(n * 2^n)	O(2^n)	~23
子集卷积	O(n^2 * 2^n)	O(n * 2^n)	~20
轮廓线 DP	O(2^m * n * m)	O(2^m)	m~15
图着色	O(3^n)	O(2^n)	~15
Meet-in-the-Middle	O(2^{n/2} * poly)	O(2^{n/2})	~40

11.3 与其他方法的比较

回溯 + 剪枝：对于小规模实例可能更快（常数小），但最坏情况下退化为 O(n!)。
ILP（整数线性规划）：对于结构化问题可能更好，但实现复杂。
近似算法：对于大规模 TSP 等问题，必须使用近似算法（如 2-opt、Christofides 算法）。
随机化算法：如模拟退火、遗传算法，适用于实际工程但没有精确保证。

十二、个人思考与总结

12.1 状压 DP 的哲学

状压 DP 教会我们一个深刻的道理：指数并不总是敌人。当 n 足够小时，2^n 就是一个完全可控的数字。而位运算给了我们一种优雅的方式来操纵这个指数空间——每个集合操作只需一条机器指令。

我个人认为，状压 DP 是算法设计中”空间换时间”思想的极致体现。我们用 2^n 大小的数组来”记忆”所有子集的最优解，避免了重复计算。这与人类记忆的方式有异曲同工之妙：与其每次都从头推导，不如记住中间结果。

12.2 实际工程中的状压 DP

在工业界，状压 DP 的直接应用并不多见（因为 n > 20 的约束太严格），但它的思想影响深远：

编译器的寄存器分配：n 是寄存器数量（通常 16 或 32），可以用状压 DP 做精确分配。
FPGA 布局布线：小规模电路的精确优化。
密码学：某些密码分析中的子集和问题。
组合博弈论：Sprague-Grundy 定理中的状态枚举。

12.3 学习建议

如果你是初学者，我建议按以下顺序学习：

先熟练掌握位运算操作（第一节）。
做几道基础的状压 DP 题（任务分配、汉密尔顿路径）。
理解 TSP 的 Held-Karp 算法。
学习子集枚举技巧。
进阶到 SOS DP 和轮廓线 DP。
最后了解 Meet-in-the-Middle 和子集卷积。

12.4 从本文中带走的关键点

状压 DP 用整数的二进制位编码集合，将集合操作转化为 O(1) 的位运算。
TSP 的 Held-Karp 算法是状压 DP 的经典代表，将 O(n!) 降到 O(2^n * n^2)。
子集枚举的 (s-1) & mask 技巧是核心操作，总复杂度为 O(3^n)。
SOS DP 是高维前缀和，在 O(n * 2^n) 内完成子集求和。
轮廓线 DP 是状压 DP 在二维网格上的应用，适合 m 较小的棋盘问题。
Meet-in-the-Middle 将指数减半，适用于 n 在 20-40 之间的情况。

状压 DP 不是银弹——它只适用于 n 较小的情况。但在这个范围内，它是精确求解 NP-hard 问题的最强武器。理解状压 DP，也就理解了计算复杂性理论中”精确指数算法”的核心思想。

参考文献

Held, M., & Karp, R. M. (1962). A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1), 196-210.
Bellman, R. (1962). Dynamic programming treatment of the travelling salesman problem. Journal of the ACM, 9(1), 61-63.
Dreyfus, S. E., & Wagner, R. A. (1971). The Steiner problem in graphs. Networks, 1(3), 195-207.
Bjorklund, A. (2014). Determinant sums for undirected Hamiltonicity. SIAM Journal on Computing, 43(1), 280-299.
CLRS, Introduction to Algorithms, Chapter 15 (Dynamic Programming).
Competitive Programmer’s Handbook, Chapter 10 (Bit manipulation).

算法系列导航：上一篇：树形 DP | 下一篇：斜率优化与凸包技巧

相关阅读：图着色与 NP-hard 近似 | DP 在工业界

目录