第 61 课：状态压缩 DP

学习目标

完成本课学习后，你将能够：

理解状态压缩动态规划（Bitmask DP）的核心思想与适用场景。
熟练运用位运算来表示和操作有限集合的状态。
掌握为集合类问题设计状态转移方程的方法。
实现基于子集枚举的经典状态压缩 DP 算法。
将所学知识应用于解决类似旅行商问题（TSP）的集合覆盖或路径问题。

核心概念

1. 什么是状态压缩？

想象一下，你有一组物品，比如有 4 个不同的苹果：A、B、C、D。你想描述“拥有哪些苹果”的所有可能情况。最朴素的想法是用一个字符串（如 “ABD”）或者一个数组（如 [1, 0, 1, 1]）。但在算法中，我们发现用一个整数的二进制位来表示每个物品“选”或“不选”是最高效、最紧凑的。

例如，用 0 表示不选，1 表示选。

物品索引 i 对应整数二进制的第 i 位。
拥有物品 A（索引0）， C（索引2）， D（索引3）的集合状态可以用二进制 1101 表示，即十进制 13。

这种用一个整数的二进制位来编码一个集合的技术，就是状态压缩。

2. 状态压缩动态规划

当 DP 问题的状态本身就表示一个“集合”（例如：访问过的节点、选择的物品子集、棋盘的某种摆放）时，如果集合的大小 n 较小（通常 n ≤ 20），我们可以用一个整数（或长整型）来枚举所有 2^n 种状态，并将这个整数作为 DP 的维度之一。

状态通常记为 dp[mask] 或 dp[mask][i]，其中：

mask 是一个整数，其二进制位表示集合中元素的选取情况。
i 可以是集合中的某个代表元素（例如，当前所在的城市）。

3. 一个简单的例子：子集和

假设有一个整数数组 nums，判断能否从其中选出若干个数，使它们的和恰好等于目标值 S。

状态定义：dp[mask] 表示由 mask 代表的子集的元素之和。
状态转移：dp[mask] = dp[mask_without_i] + nums[i]，其中 i 是 mask 中某个被置位的元素。
初始化：dp[0] = 0（空集之和为0）。
最终答案：检查是否存在某个 mask，使得 dp[mask] == S。

4. 经典应用：旅行商问题（TSP）

问题描述：给定 n 个城市和任意两城市间的距离，一个商人从城市 0 出发，需要访问每个城市恰好一次，并最终返回城市 0。求最短的旅行路径长度。

这是状态压缩 DP 最经典的用例。

状态定义：dp[mask][i] 表示访问了 mask 所代表的城市集合，并且当前停留在城市 i 的最短路径长度。
转移方程：要到达状态 (mask, i)，上一步一定是从某个城市 j 转移而来，且 j 必须在集合 mask 中。 dp[mask][i] = min(dp[mask ^ (1 << i)][j] + dist[j][i])，其中 j 属于 mask ^ (1 << i)（即访问 i 之前的集合）。
边界条件：dp[1][0] = 0（初始状态：只访问了城市0，且停留在城市0，路径长为0）。
最终答案：min(dp[(1<<n)-1][i] + dist[i][0])，其中 i 遍历所有城市，表示访问完所有城市后，从城市 i 返回起点 0 的最短总路径。

代码示例：解决旅行商问题（TSP）

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int tsp(const vector<vector<int>>& dist) {
    int n = dist.size();
    // dp[mask][i]: 访问了 mask 集合中的城市，最后停在城市 i 的最短路径
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));

    // 初始化：从城市0出发
    dp[1][0] = 0; // mask = 1 (二进制 ...001), 停在城市0

    // 遍历所有可能的 mask (代表访问的城市集合)
    for (int mask = 1; mask < (1 << n); ++mask) {
        // 遍历当前 mask 下，所有可能作为“终点”的城市 i
        for (int i = 0; i < n; ++i) {
            // 如果城市 i 不在 mask 集合中，或者 dp 值无效，则跳过
            if (!(mask & (1 << i)) || dp[mask][i] == INT_MAX) continue;

            // 尝试从城市 i 出发，前往一个尚未访问的城市 j (j 不在 mask 中)
            for (int j = 0; j < n; ++j) {
                if (mask & (1 << j)) continue; // j 已在集合中

                // 构造新的状态 mask | (1 << j)，并从 i 转移到 j
                int new_mask = mask | (1 << j);
                dp[new_mask][j] = min(dp[new_mask][j], dp[mask][i] + dist[i][j]);
            }
        }
    }

    // 收集答案：访问了所有城市后，从任意城市 i 返回城市 0 的最短总路径
    int full_mask = (1 << n) - 1;
    int ans = INT_MAX;
    for (int i = 1; i < n; ++i) { // i 从1开始，因为从0出发最后又回到0的路径在dp[full_mask][0]中没有意义（没有走一圈）
        if (dp[full_mask][i] != INT_MAX) {
            ans = min(ans, dp[full_mask][i] + dist[i][0]);
        }
    }
    return ans;
}

int main() {
    // 示例：4个城市的距离矩阵（对角线为0）
    vector<vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };

    cout << "The minimum traveling cost is: " << tsp(dist) << endl;
    // 预期输出: The minimum traveling cost is: 80
    // 一条可能的路径: 0 -> 1 -> 3 -> 2 -> 0， 总距离 10+25+30+15=80

    return 0;
}

代码解析：

dp 数组的第一维 mask 是集合状态，第二维 i 是当前停留城市。
外层循环枚举所有可能的 mask，从小的集合（少城市）扩展到大的集合（多城市）。
中层循环检查当前 mask 下合法的“终点” i。
内层循环尝试进行状态转移：从 i 到另一个未访问的城市 j，更新更大的集合状态 new_mask。
最后，在访问所有城市 (full_mask) 的基础上，加上返回起点的距离，取最小值。

实践练习

练习 1：最短 Hamilton 路径

问题描述：给定 n 个点（编号 0 到 n-1）的带权有向完全图，求从点 0 到点 n-1，恰好不重复地经过所有点的最短路径长度。与 TSP 的区别是：不需要返回起点，且起点和终点固定。要求：修改上述 TSP 代码，解决此问题。 预期输出：对于样例输入 n=4, dist 矩阵同上例，答案应为 65 (路径 0 -> 1 -> 3 -> 2)。

练习 2：集合划分

问题描述：给定一个包含 n 个正整数的数组，将它们划分为两个子集，使得两个子集的元素和之差的绝对值最小。求这个最小差值。要求：使用状态压缩 DP，先计算出所有可能的子集和，然后求解。 预期输出：输入 nums = [1, 6, 11, 5]，输出 1（子集 {1,5,6} 和为12，子集 {11} 和为11，差为1）。

练习 3：带时间窗的旅行商（挑战）

问题描述：在经典 TSP 问题中，每个城市有一个“时间窗” [open_i, close_i]，商人必须在 open_i 之后（含）close_i 之前（含）到达城市 i。从城市 i 到 j 需要时间 t_ij。假设商人从城市 0 出发，时间为 0。判断是否能访问所有城市恰好一次，并在时间窗内到达，如果能，求最短旅行时间（不考虑返回）。要求：扩展状态，考虑时间因素。提示：状态 dp[mask][i] 可以表示访问了 mask 集合、最后停在 i 且 最早可能到达 i 的时间。

常见错误

位运算优先级混淆：
- 1 << n 非常高，但 mask & 1 << i 可能会被错误解析为 (mask & 1) << i。务必使用括号：mask & (1 << i)。
- mask ^ (1 << i) 的优先级也需要注意，最好也加上括号。
状态表示混淆：
- 错误地认为 dp[mask] 中 mask 的1的个数代表访问的顺序。实际上，mask 只表示访问了哪些城市，不表示访问顺序。顺序信息由 DP 的状态转移过程隐式地构建出来。
忽略边界条件和无效状态：
- 初始化 dp[1][0] = 0，其他状态（除了可达状态）应初始化为 INT_MAX 或一个足够大的值，以确保 min 操作的正确性。
- 在转移前，必须检查源状态 dp[mask][i] 是否有效（不是 INT_MAX）。
空间复杂度估算错误：
- dp 数组大小通常是 (1<<n) * n，当 n=20 时，约为 2^20 * 20 ≈ 20 * 10^6，这是可以接受的。但当 n=25 时，就会爆炸式增长。状态压缩 DP 通常只适用于 n 较小（≤20）的情况。

小结

状态压缩 DP 是用一个整数的二进制位来表示一个有限集合，从而将集合枚举融入到 DP 的状态中。
它的核心思想是：用 dp[mask][...] 来记录与集合 mask 相关的最优解信息。
位运算 是操作和访问压缩状态的关键工具：(mask >> i) & 1 或 mask & (1<<i) 判断第 i 位是否为1；mask | (1<<i) 设置第 i 位；mask ^ (1<<i) 翻转第 i 位。
经典应用包括旅行商问题、哈密顿路径、集合划分、棋盘覆盖等问题。
当问题涉及对一个元素数量有限（通常 n≤20）的集合进行选择、排列、覆盖等操作并求最优解时，应首先考虑状态压缩 DP。

掌握状态压缩 DP，相当于获得了一把解开众多“组合爆炸”类难题的利刃，是进阶算法学习中的重要里程碑。

练习编辑器

rust