20261007 190853 动态规划系统课程7

动态规划系统课程 · 第七讲：状态压缩 DP ¶

这一讲进入动态规划中非常重要的一类：

状态压缩 DP（Bitmask DP）¶

前面我们学习 DP 时，状态通常比较简单：

dp[i]
dp[i][j]
dp[l][r]
dp[u][0]

但有一类问题会遇到一个困难：

状态不仅需要记录“当前在哪里”，还需要记录“哪些东西已经使用过”。

例如：

已经访问：
1、3、5

当前在：
3

如果直接记录集合：

{1,3,5}

程序处理起来很麻烦。

状态压缩 DP 的核心思想就是：

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

一、什么是状态压缩？¶

假设有 5 个城市：

1 2 3 4 5

我们使用一个二进制数表示访问状态。

规定：

第 0 位 → 城市 1
第 1 位 → 城市 2
第 2 位 → 城市 3
第 3 位 → 城市 4
第 4 位 → 城市 5

例如：

表示：

城市 1：访问
城市 2：没有访问
城市 3：访问
城市 4：没有访问
城市 5：没有访问

也就是：

{1, 3}

二、为什么二进制特别适合表示集合？¶

因为二进制每一位只有：

0
1

正好可以表示：

0 → 没有选择
1 → 已经选择

所以：

集合

可以变成：

二进制整数

例如：

集合 {1,3,4}

对应：

三、状态压缩最重要的三个操作 ¶

假设：

int mask;

1. 判断第 i 个元素是否选择 ¶

使用：

mask & (1 << i)

例如：

if (mask & (1 << i)) {
    // i 已经选择
}

2. 把 i 加入集合 ¶

使用：

mask | (1 << i)

例如：

int newMask = mask | (1 << i);

3. 从集合中删除 i ¶

使用：

mask ^ (1 << i)

前提是：

i 原来一定在集合中。

更通用的写法：

mask & ~(1 << i)

四、最重要的操作：枚举集合中的元素 ¶

如果：

mask

表示已经选择的集合，那么我们经常需要：

枚举所有已经选择的元素。

最简单的写法：

for (int i = 0; i < n; i++) {

    if (mask & (1 << i)) {

        // i 在集合中
    }
}

五、一个非常重要的概念：状态数量 ¶

如果有 n 个元素。

每个元素有两种状态：

选择
不选择

所以一共有：

$$
2^n
$$

种状态。

例如：

n	状态数
5	32
10	1024
15	32768
20	1048576
25	33554432

因此状态压缩 DP 通常适用于：

$$
n\le 20
$$

左右的问题。

具体上限取决于转移复杂度和内存。

六、第一道经典题：TSP ¶

我们开始状态压缩 DP 最经典的问题：

旅行商问题 ¶

有 n 个城市。

城市之间有距离：

dist[i][j]

要求：

从城市 0 出发，每个城市恰好访问一次，最后回到城市 0，求最短路线长度。

例如：

七、为什么普通 DP 不够？¶

如果只写：

dp[i]

表示：

当前在城市 i。

这是不够的。

因为：

当前都在城市 3

可能存在两种情况：

0 → 1 → 2 → 3

或者：

0 → 2 → 1 → 3

虽然当前都是：

但已经访问的城市集合不同。

所以状态必须同时记录：

已访问哪些城市
当前在哪里

于是：

$$
\boxed{dp[S][i]}
$$

八、TSP 状态定义 ¶

定义：

$$
dp[S][i]
$$

表示：

已经访问的城市集合为 S，当前位于城市 i 时的最短路径长度。

其中：

是一个二进制集合。

九、初始化 ¶

从城市 0 出发。

一开始只访问了城市 0：

所以：

$$
dp[1][0]=0
$$

如果从 0 开始编号：

dp[1 << 0][0] = 0;

十、状态转移 ¶

假设：

dp[S][i]

表示：

已经访问集合 S，现在在 i。

下一步去：

要求：

j 还没有访问。

判断：

if (!(S & (1 << j)))

然后：

S
↓
S ∪ {j}

新的集合：

newS = S | (1 << j);

路径增加：

$$
dist[i][j]
$$

所以：

$$
dp[S\cup{j}][j]
=
\min
\left(
dp[S\cup{j}][j],
dp[S][i]+dist[i][j]
\right)
$$

十一、最终答案 ¶

当所有城市都访问完成：

S = (1 << n) - 1

例如 n=4：

表示：

所有城市都访问了

此时我们在某个城市 i。

但题目要求：

最后回到城市 0。

因此：

$$
answer
=
\min_i
\left(
dp[all][i]+dist[i][0]
\right)
$$

注意：

不要忘记最后回到起点。

十二、完整 C++ 实现 ¶

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

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

    int n;
    cin >> n;

    vector<vector<long long>> dist(
        n,
        vector<long long>(n)
    );

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }

    const long long INF = 4e18;

    int total = 1 << n;

    vector<vector<long long>> dp(
        total,
        vector<long long>(n, INF)
    );

    // 从城市 0 出发
    dp[1][0] = 0;

    for (int mask = 0; mask < total; mask++) {

        for (int i = 0; i < n; i++) {

            if (dp[mask][i] == INF)
                continue;

            // 尝试去城市 j
            for (int j = 0; j < n; j++) {

                // j 已经访问
                if (mask & (1 << j))
                    continue;

                int newMask =
                    mask | (1 << j);

                dp[newMask][j] =
                    min(
                        dp[newMask][j],
                        dp[mask][i]
                        + dist[i][j]
                    );
            }
        }
    }

    int all = (1 << n) - 1;

    long long answer = INF;

    // 最后回到 0
    for (int i = 0; i < n; i++) {

        answer = min(
            answer,
            dp[all][i] + dist[i][0]
        );
    }

    cout << answer << '\n';

    return 0;
}

十三、一定要理解 `mask`¶

这是状态压缩 DP 最重要的基础。

假设：

n = 4

那么：

mask

可能是：

其中：

表示：

4 个城市全部访问。

而：

表示：

第 0 个和第 2 个城市已经访问。

十四、位运算详细解释 ¶

假设：

int mask = 5;

二进制：

判断城市 0 ¶

mask & (1 << 0)

也就是：

0101
&
0001
----
0001

结果非零。

所以：

城市 0 已访问。

判断城市 1 ¶

mask & (1 << 1)

即：

0101
&
0010
----
0000

结果为 0。

所以：

城市 1 没有访问。

十五、加入一个城市 ¶

假设：

mask = 0101

现在访问城市 1。

城市 1 对应：

使用：

mask | (1 << 1)

得到：

0101
|
0010
----
0111

于是：

变成：

十六、第二道经典题：集合覆盖 DP ¶

现在把 TSP 稍微抽象一下。

假设有：

n 个任务

每个任务可能被某种操作覆盖。

我们希望：

用最少的操作覆盖所有任务。

如果 mask 表示：

当前已经覆盖的任务集合。

那么可以定义：

$$
dp[mask]
$$

表示：

覆盖集合 mask 所需要的最小代价。

这就是最基础的：

集合 DP ¶

十七、一个简单模型 ¶

假设有 4 个任务：

1 2 3 4

有三个操作：

操作 A：覆盖 1、2
操作 B：覆盖 2、3
操作 C：覆盖 3、4

每个操作有一个费用。

例如：

A：5
B：2
C：4

目标：

覆盖全部任务，最小费用。

十八、状态定义 ¶

$$
dp[mask]
$$

表示：

当前已经覆盖 mask 中的任务所需要的最小费用。

初始：

$$
dp[0]=0
$$

因为：

什么任务都没有覆盖时，费用是 0。

十九、状态转移 ¶

假设当前：

mask

选择一个操作，它覆盖：

cover

新的覆盖集合：

$$
newMask=mask\ |\ cover
$$

那么：

$$
dp[newMask]
=
\min(
dp[newMask],
dp[mask]+cost
)
$$

二十、完整 C++ 代码 ¶

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

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

    int n, m;
    cin >> n >> m;

    vector<int> cover(m);
    vector<long long> cost(m);

    for (int i = 0; i < m; i++) {

        int k;
        cin >> k;

        int mask = 0;

        for (int j = 0; j < k; j++) {

            int x;
            cin >> x;

            // 任务编号从 1 开始
            --x;

            mask |= (1 << x);
        }

        cover[i] = mask;

        cin >> cost[i];
    }

    const long long INF = 4e18;

    int total = 1 << n;

    vector<long long> dp(
        total,
        INF
    );

    dp[0] = 0;

    for (int mask = 0; mask < total; mask++) {

        if (dp[mask] == INF)
            continue;

        for (int i = 0; i < m; i++) {

            int newMask =
                mask | cover[i];

            dp[newMask] =
                min(
                    dp[newMask],
                    dp[mask] + cost[i]
                );
        }
    }

    int all = (1 << n) - 1;

    if (dp[all] == INF)
        cout << -1 << '\n';
    else
        cout << dp[all] << '\n';

    return 0;
}

二十一、这道题和 TSP 有什么关系？¶

TSP：

dp[mask][i]

集合覆盖：

dp[mask]

共同点：

都使用 mask 描述“已经完成了什么”。

区别：

TSP 还需要知道：

当前位置 i

所以：

$$
dp[mask][i]
$$

而集合覆盖只关心：

已经覆盖哪些任务

所以：

$$
dp[mask]
$$

二十二、第三道经典题：状压 DP 的“选数”问题 ¶

现在看一个更加基础的模型。

给定 n 个数：

a1, a2, ..., an

要求选择若干个数。

如果选择状态由：

mask

表示，那么：

mask

就是一个集合。

例如：

mask = 10110

表示选择：

2、3、5

二十三、为什么不直接使用普通 DFS？¶

当然可以。

例如：

void dfs(int pos) {

    // 不选
    dfs(pos + 1);

    // 选
    dfs(pos + 1);
}

这实际上是在枚举所有子集。

但是：

DFS 只能告诉你当前走到了哪里。

如果不同的路径最终产生相同的状态，就会重复计算。

DP 的作用就是：

把相同状态合并。

这就是状态压缩 DP 的价值。

二十四、一个非常重要的思想：状态合并 ¶

假设有：

1 → 2
1 → 3

最终可能产生同一个状态：

mask = 10101

如果这个状态之后的计算完全相同：

那么前面的过程就没有必要重复计算。

只需要保存：

dp[10101]

即可。

这就是 DP 的核心思想之一：

相同状态只计算一次。¶

二十五、状态压缩 DP 的复杂度 ¶

最常见：

$$
2^n
$$

个状态。

如果每个状态枚举 n 个选择：

$$
O(n2^n)
$$

如果再加一层：

$$
O(n^2 2^n)
$$

因此：

n = 20

时：

$$
2^{20}=1,048,576
$$

大约一百万个状态。

这是可以接受的。

但：

n = 30

时：

$$
2^{30}\approx10.7亿
$$

通常就非常困难了。

二十六、状态压缩 DP 的常见状态形式 ¶

以后会经常看到：

形式一 ¶

$$
dp[mask]
$$

表示：

集合 mask 的最优答案。

形式二 ¶

$$
dp[mask][i]
$$

表示：

已经完成 mask，当前位于 i。

TSP 就属于这一类。

形式三 ¶

$$
dp[mask][i][j]
$$

表示：

集合 mask + 两个额外状态。

这种情况状态更多，需要特别注意复杂度。

二十七、状态压缩 DP 最重要的思维 ¶

以后看到：

n 很小，通常 n ≤ 20

并且题目出现：

每个元素选/不选
已经使用了哪些元素
已经访问哪些城市
已经完成哪些任务
集合
子集
每个元素只能使用一次

马上想到：

二进制状态压缩 ¶

二十八、四种常用位运算 ¶

建议学生直接背下来，但更重要的是理解。

假设第 i 位表示元素 i。

判断 ¶

mask & (1 << i)

加入 ¶

mask | (1 << i)

删除 ¶

mask & ~(1 << i)

翻转 ¶

mask ^ (1 << i)

二十九、如何枚举所有子集？¶

如果有 n 个元素：

for (int mask = 0; mask < (1 << n); mask++) {

    // mask 就是一个子集
}

这是最基础的子集枚举。

三十、如何枚举 `mask` 的所有子集？¶

这是状态压缩 DP 中非常重要的技巧。

例如：

mask = 10110

我们想枚举：

可以使用：

for (int sub = mask; sub; sub = (sub - 1) & mask) {

    // sub 是 mask 的一个非空子集
}

这个技巧非常重要。

三十一、为什么 `(sub - 1) & mask` 可以枚举子集？¶

例如：

mask = 10110

假设：

sub = 10100

减一：

再：

10011
&
10110
-----
10010

得到：

仍然是 mask 的子集。

不断重复：

sub = (sub - 1) & mask

最终就会遍历所有子集。

复杂度：

$$
O(3^n)
$$

这会在后面的高级状态压缩 DP 中非常重要。

三十二、状态压缩 DP 与普通 DP 的区别 ¶

普通 DP：

状态数量通常是 n
n²
n³

状态压缩 DP：

状态数量通常是 2^n

所以它的核心交换关系是：

用指数级状态数量，换取对“小规模集合问题”的高效精确求解。

三十三、目前的 DP 知识地图 ¶

到这里已经进入一个比较完整的体系：

动态规划
│
├── ① 线性 DP
│   ├── LIS
│   ├── LCS
│   └── 编辑距离
│
├── ② 背包 DP
│   ├── 01 背包
│   ├── 完全背包
│   ├── 多重背包
│   └── 分组背包
│
├── ③ 区间 DP
│   ├── 石子合并
│   ├── 回文
│   └── 矩阵链
│
├── ④ 树形 DP
│   ├── 最大独立集
│   ├── 没有上司的舞会
│   └── 树上最大路径
│
├── ⑤ DAG DP
│   ├── 最长路
│   ├── 最短路
│   └── 路径计数
│
└── ⑥ 状态压缩 DP
    ├── 子集 DP
    ├── TSP
    ├── 集合覆盖
    └── 位运算

三十四、本讲最重要的三个公式 ¶

判断元素是否在集合中 ¶

$$
\boxed{
mask\ \&\ (1<<i)
}
$$

加入元素 ¶

$$
\boxed{
mask|(1<<i)
}
$$

状压 DP 最经典状态 ¶

$$
\boxed{
dp[mask][i]
}
$$

它表示：

完成集合 mask，当前处于状态 i 时的最优答案。

三十五、一个非常重要的判断口诀 ¶

以后做竞赛题时看到：

n 很小
+
每个元素有选/不选
+
还要记录已经选择了哪些

马上想到：

二进制 → 集合 → 状态压缩 DP

如果进一步出现：

当前在哪里

那么马上想到：

dp[mask][i]

如果题目出现：

每个城市访问一次

马上想到：

TSP / 状态压缩 DP

三十六、下一讲：数位 DP ¶

下一讲我们继续进入一个非常有特色的 DP：

第八讲：数位 DP ¶

数位 DP 专门解决这类问题：

统计 [L,R] 范围内满足某种数字条件的整数个数。

例如：

1 ~ 10^18 中有多少个数字不包含 4？
1 ~ 10^18 中有多少个数字相邻两位不同？
1 ~ N 中有多少个数字的数位和等于 S？
L ~ R 中有多少个数字满足某种数位限制？

届时会重点学习：

$$
\boxed{dp[pos][state][limit][lead]}
$$

这几个状态参数分别是什么意思，以及为什么数位 DP 经常使用：

答案(1 ~ R)
-
答案(1 ~ L-1)

来解决 [L,R] 的问题。

到那时，我们会把动态规划进一步推进到：

线性 DP → 背包 → 区间 → 树形 → DAG → 状态压缩 → 数位 DP → 计数 DP → 概率 DP → DP 优化

这套体系基本就覆盖了中学信息学竞赛中最重要的动态规划框架。