状态压缩 DPCSP-S

💡 核心思想

状态压缩 DP 用二进制整数来表示集合状态，每一位 0/1 代表一个元素是否被选中。当元素数量较少（通常 $\le 20$）时，可以用一个整数编码所有可能的子集，实现紧凑的状态表示。

🎯 直觉理解

想象你有 5 个任务要安排顺序。用 5 位二进制数表示哪些任务已完成：00000 = 都没做，10110 = 第2、3、5个做完了。这样所有可能的完成情况恰好是 $2^5 = 32$ 种，用一个整数就能表示。

📝 算法流程

1. 状态：$dp[S]$ 表示已完成集合 $S$ 时的最优值
2. 转移：枚举 $S$ 中没有的元素 $i$，从 $S - \{i\}$ 转移
3. 遍历：按集合大小从小到大
4. 总状态数：$2^n$

$$dp[S] = \min_{i \in S} \{dp[S \setminus \{i\}] + cost(i, S)\}$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
// TSP 问题：从城市0出发经过所有城市后返回
int main() {
    int n; cin >> n;
    vector dist(n, vector<int>(n));
    for (auto& r : dist) for (auto& x : r) cin >> x;
    const int INF = 1e9;
    vector<vector<int>> dp(1<<n, vector<int>(n, INF));
    dp[1][0] = 0; // 只访问了城市0
    for (int S = 1; S < (1<<n); S++) {
        for (int u = 0; u < n; u++) {
            if (!(S >> u & 1)) continue;
            for (int v = 0; v < n; v++) {
                if (S >> v & 1) continue;
                dp[S|(1<<v)][v] = min(dp[S|(1<<v)][v], dp[S][u] + dist[u][v]);
            }
        }
    }
    int ans = INF;
    for (int i = 1; i < n; i++)
        ans = min(ans, dp[(1<<n)-1][i] + dist[i][0]);
    cout << ans << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目