GESP 8级 · 状压DP

📖概念讲解

状压DP（状态压缩动态规划）是用二进制整数来表示集合状态的DP技巧。把"哪些元素被选中"压缩成一个整数的二进制位——第 i 位为 1 表示第 i 个元素在集合中。

核心思想：n 个元素的所有子集最多 2ⁿ 个，用 0 ~ 2ⁿ−1 的整数就能枚举。适合 n ≤ 20 的场景。

🔑 三个必备操作：
• 判断第 i 位： mask & (1 << i) — 非零则 i 在集合中
• 加入第 i 位： mask | (1 << i)
• 去掉第 i 位： mask & ~(1 << i)

经典问题：TSP（旅行商问题）—— n 个城市，每个城市恰好访问一次，求最短回路。状态 dp[S][i] 表示已访问城市集合为 S、当前在城市 i 的最短路径。

💻代码示例

下面用状压DP解 TSP 问题（n ≤ 15）：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15, INF = 0x3f3f3f3f;
int dist[N][N];          // 邻接矩阵存距离
int dp[1 << N][N];       // dp[S][i]: 集合S且在城市i的最短距离
int n;
int main() {
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> dist[i][j];
    // 初始化：只访问过城市0，当前在城市0，距离为0
    memset(dp, 0x3f, sizeof(dp));   // 全部设为INF
    dp[1][0] = 0;                    // 000...001 表示只有城市0
    // 枚举所有集合 S
    for(int S = 0; S < (1 << n); S++) {
        for(int i = 0; i < n; i++) {           // i = 当前所在城市
            if(dp[S][i] == INF) continue;     // 不可达则跳过
            for(int j = 0; j < n; j++) {       // j = 下一个要去的城市
                if(S & (1 << j)) continue;    // j已经在集合S中，跳过
                int ns = S | (1 << j);          // 新集合：加入城市j
                dp[ns][j] = min(dp[ns][j],       // 更新最短距离
                    dp[S][i] + dist[i][j]);
            }
        }
    }
    // 回到起点0：所有城市都访问过（全1）且在城市i，再走回0
    int full = (1 << n) - 1;             // 全1 = 111...111
    int ans = INF;
    for(int i = 0; i < n; i++)
        ans = min(ans, dp[full][i] + dist[i][0]); // 从i走回起点
    cout << ans << endl;
    return 0;
}

⏱ 复杂度：O(2ⁿ × n²)，n=15 时约 5×10⁶，完全可接受。

🧩互动小测

Q1：n=5 时，全集 mask 的值是多少？

Q2：如何检查城市 3 是否在集合 S 中？

Q3：状压DP的时间复杂度是？

🏋️动手练一练

📝 编程练习：最短汉密尔顿路径

给定 n 个点的带权有向图（邻接矩阵），求从点 0 出发、经过所有点恰好一次的最短路径长度。

输入格式：第一行 n（2 ≤ n ≤ 15），接下来 n 行每行 n 个整数表示距离矩阵。
输出：一个整数，最短路径长度。

提示：和例题几乎一样，只是不用回到起点。状态定义相同：dp[S][i] 表示走过集合 S 中的城市、当前在城市 i 的最短距离。

参考答案：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=15,INF=0x3f3f3f3f;
int dist[N][N],dp[1<<N][N],n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++) cin>>dist[i][j];
    memset(dp,0x3f,sizeof(dp));
    dp[1][0]=0; // 起点在城市0
    for(int S=0;S<(1<<n);S++)
        for(int i=0;i<n;i++){
            if(dp[S][i]==INF) continue;
            for(int j=0;j<n;j++){
                if(S&(1<<j)) continue;
                int ns=S|(1<<j);
                dp[ns][j]=min(dp[ns][j],dp[S][i]+dist[i][j]);
            }
        }
    int full=(1<<n)-1,ans=INF;
    for(int i=0;i<n;i++)
        ans=min(ans,dp[full][i]); // 不用回到起点
    cout<<ans;
}

要点：区别只在最终答案——取所有 dp[full][i] 的最小值，不需要再加 dist[i][0] 回到起点。

📝易错点提醒

判断成员用 & 不是 &&：位运算用 &，逻辑与用 &&，混用必错。
dp 数组开 1<<N 而不是 N：状态数是 2ⁿ，不是 n。
位运算优先级低于比较运算：S & (1<<j) == 0 实际是 S & ((1<<j)==0)，必须加括号：(S & (1<<j)) == 0。
不要忘记 continue：跳过已访问城市或不可达状态，否则会 TLE。
起点初始化：dp[1][0] = 0，注意 1 的含义是二进制只有第 0 位为 1（城市 0）。

📘状压DP · 状态压缩动态规划

📖概念讲解

💻代码示例

🧩互动小测

Q1：n=5 时，全集 mask 的值是多少？

Q2：如何检查城市 3 是否在集合 S 中？

Q3：状压DP的时间复杂度是？

🏋️动手练一练

📝 编程练习：最短汉密尔顿路径

📝易错点提醒