状压 DP

概念讲解

什么是状压 DP？

用二进制数表示状态的动态规划。

状态表示

用二进制数的每一位表示一个元素是否被选择。

经典问题

1. 旅行商问题（TSP）

问题： 访问所有城市并回到起点，求最短路径。

1234567891011121314151617181920212223int tsp(vector<vector<int>>& dist) {
    int n = dist.size();
    int ALL = (1 << n) - 1;
    vector<vector<int>> dp(1 << n, vector<int>(n, 1e9));
    dp[1][0] = 0;  // 从城市 0 出发
    
    for (int mask = 1; mask <= ALL; mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], 
                                              dp[mask][u] + dist[u][v]);
            }
        }
    }
    
    int ans = 1e9;
    for (int u = 0; u < n; u++) {
        ans = min(ans, dp[ALL][u] + dist[u][0]);
    }
    return ans;
}

时间复杂度：O(2n⋅n2)O(2^n \cdot n^2)

考点分析

初赛考查方式

  1. 程序阅读： 状压 DP
  2. 编程题： 集合问题

常见考点

  • TSP 问题
  • 状态表示
  • 枚举子集

例题精讲

例题 1：TSP

题目： 4 个城市的 TSP 问题。

解答：

状态用 4 位二进制表示，枚举所有状态。

练习题

  1. 状压 DP 的适用条件是什么？
查看答案

状压 DP 的适用条件：

  1. n 较小：通常 n≤20n \le 20（因为状态数是 2n2^n）
  2. 状态可以用二进制表示：每个元素只有选/不选两种状态
  3. 需要记录集合信息：如已经访问过哪些点
  1. TSP 的时间复杂度是多少？
查看答案

O(2n⋅n2)O(2^n \cdot n^2)

  • 状态数：2n2^n（所有可能的访问集合）
  • 每个状态转移：O(n2)O(n^2)（枚举当前点和下一个点）
  1. 如何枚举子集？
查看答案
12345678910// 枚举集合 s 的所有子集
for (int subset = s; subset; subset = (subset - 1) & s) {
    // subset 是 s 的子集
}

// 枚举所有子集（包括空集）
for (int subset = s; ; subset = (subset - 1) & s) {
    // subset 是 s 的子集
    if (subset == 0) break;
}

易错点

⚠️ 注意：

  1. n 不能太大（通常 ≤ 20）
  2. 状态转移要正确
  3. 枚举子集用 (mask-1) & mask
  4. 初始化要正确