我的算法书 - 状态压缩 DP

一句话算法

状态压缩 DP 用一个二进制数表示集合，把“选了哪些元素”压进一个整数状态里。

问题模型

当题目中元素数量较小，例如 $n \le 20$ ，并且状态和“某些元素是否被选过”有关时，可以用二进制集合表示状态。

例如有 n 个点：

第 i 位为 1：表示点 i 已经被选择或访问；
第 i 位为 0：表示点 i 还没有被选择或访问。

这样，一个整数 mask 就能表示一个集合。

核心直觉

普通 DP 的状态可能写成：

已经访问过 {0, 2, 3}，最后停在 3

状态压缩后：

mask = 1101(二进制)
last = 3

集合变成整数后，就可以用位运算快速判断、加入、删除元素。

常用位运算

判断第 i 位是否为 1：

cpp

        1

        mask & (1 << i)

加入第 i 个元素：

cpp

        1

        mask | (1 << i)

删除第 i 个元素：

cpp

        1

        mask ^ (1 << i)   // 前提是这一位原来为 1

全集：

cpp

        1

        (1 << n) - 1

算法步骤

以最短 Hamilton 路径为例：从点 0 出发，访问所有点一次，求最小代价。

定义：

dp[mask][last]

表示已经访问集合 mask，当前停在 last 时的最小代价。

转移：

从 last 走到 next
new_mask = mask | (1 << next)
dp[new_mask][next] = min(dp[new_mask][next], dp[mask][last] + cost[last][next])

初始状态：

cpp

        1

        dp[1][0] = 0;

答案：

cpp

        1

        min(dp[(1 << n) - 1][last])

算法证明

核心不变量：dp[mask][last] 始终表示访问集合恰好为 mask 且最后停在 last 的最小代价。

初始时只访问点 0，代价为 0，不变量成立。

转移时，从一个合法状态走向尚未访问的 next，新集合正好多出 next，新代价等于旧代价加边权。对同一个新状态取最小值，就保留了所有可能路径中的最优代价。

任意访问所有点的路径都可以按最后一步倒推到某个 dp[mask][last] 状态，因此所有合法方案都会被枚举。最终全集状态中的最小值就是答案。

复杂度分析

设元素数量为 $n$ 。

状态数： $2^n \times n$ 。
每个状态枚举下一个点： $O(n)$ 。
总时间复杂度： $O(2^n n^2)$ 。
空间复杂度： $O(2^n n)$ 。

状态压缩 DP 适合 n 较小但组合状态很多的问题。

代码实现

模板输入一个 n*n 的代价矩阵，输出从点 0 出发访问所有点一次的最小代价。

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

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

const long long INF = (1LL << 60);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<long long>> cost(n, vector<long long>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> cost[i][j];
        }
    }

    int limit = 1 << n;
    vector<vector<long long>> dp(limit, vector<long long>(n, INF));
    dp[1][0] = 0;

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

            for (int next = 0; next < n; next++) {
                if (mask & (1 << next)) continue;
                int new_mask = mask | (1 << next);
                dp[new_mask][next] = min(dp[new_mask][next], dp[mask][last] + cost[last][next]);
            }
        }
    }

    long long answer = INF;
    int full = limit - 1;
    for (int last = 0; last < n; last++) {
        answer = min(answer, dp[full][last]);
    }

    cout << answer << '\n';
    return 0;
}

测试用例

输入：

输出：

解释：一条最优路径是 0 -> 1 -> 3 -> 2，代价为 1+3+8=12。

应用分类详解

状态压缩 DP 的本质是枚举集合。只要题目中某部分对象数量不大，并且状态取决于“选了哪些”，就可以考虑 bitmask。

一、访问集合类问题

典型模式： 每个点或任务最多访问一次，要求最小代价或最大收益。

识别信号： 出现“访问所有点”“每个任务选或不选”“n <= 20”。

核心建模： mask 表示已访问集合，额外维度表示当前位置或最后选择。

应用场景	经典题目	核心思路
最短 Hamilton 路径	状压 DP 模板题	`dp[mask][last]`
旅行商变体	小规模 TSP	集合 + 最后位置

二、子集枚举类问题

典型模式： 枚举某个集合的所有子集。

识别信号： 出现“把集合分成两部分”“枚举子集转移”。

核心建模： 使用 sub = (sub - 1) & mask 枚举 mask 的子集。

三、集合关系统计

典型模式： 统计子集和、超集和、与/或关系。

识别信号： 出现“所有子集贡献”“所有超集贡献”。

核心建模： SOS DP 是状态压缩 DP 的高阶应用。

经典例题

1. 最短 Hamilton 路径

状态压缩 DP 入门模型，重点是 dp[mask][last] 的状态定义。

2. luogu-P1433

吃奶酪。点数较小，典型的访问集合 + 最后位置模型。

3. SOS DP 相关题

当需要对所有子集或超集统计贡献时，可以进一步学习 SOS DP。

参考

本书 SOS DP 章节：dynamic_programming/sos/index.md