状压DP
高级状压 DP 是 CSP-S 高频考点，经典问题：TSP、棋盘覆盖。
// 算法讲解
状压DP
演示状压DP求解旅行商问题(TSP)的过程。
待机
速度 中
待机 ⌨1int tsp(vector<vector<int>>& dist) {
2 int n = dist.size();
3 vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
4 dp[1][0] = 0;
5 for (int mask = 1; mask < (1 << n); mask++)
6 for (int u = 0; u < n; u++) {
7 if (dp[mask][u] == INT_MAX) continue;
8 for (int v = 0; v < n; v++)
9 if (!(mask & (1 << v)))
10 dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + dist[u][v]);
11 }
12 int ans = INT_MAX;
13 for (int u = 1; u < n; u++)
14 ans = min(ans, dp[(1<<n)-1][u] + dist[u][0]);
15 return ans;
16}
复杂度分析
时间 O(2^n × n)
空间 O(2^n × n)
最优 O(2^n × n)
最坏 O(2^n × n)
算法讲解
状压 DP 用二进制位表示集合中哪些元素被选中。
经典问题：旅行商问题（TSP）、N 皇后、棋盘覆盖。
state dp[mask][i] 表示已访问集合 mask、当前在节点 i 的最优解。
时间复杂度 O(2^n × n)，适用于 n ≤ 20 的场景。