困难C++7 分钟2,446 字

状态压缩动态规划:用二进制编码来记忆

你有没有想过,用一个数字就能记住一套完整的“选择题答案”?比如去超市购物,5样东西每样买或不买,就能写成 10100 这样一串0和1。状态压缩动态规划(状压DP)就是利用二进制数来高效地表示和转移状态,专门解决“集合”或“子集”类的组合优化问题。当物品数量较小(通常 n ≤ 20)时,它能把指数级的枚举压缩成可计算的动态规划。

为什么需要“二进制编码”?

先回忆一下,普通动态规划的状态往往是一维或二维的,比如“前i件物品的最大价值”。但有些问题中,我们需要同时知道“哪些物品已经用过了”,这时候状态数量是指数级的(2^n)。但巧的是,每个物品只有“选”或“不选”两种状态,正好对应二进制位的0和1。于是我们就可以用一个整数来表示所有物品的选择情况,这个整数叫做 掩码(mask)​​​。

生活例子:​ 你有4个游戏金币,每个金币只能使用一次,你需要在闯关时决定使用哪些金币。所有可能的用法有16种(2^4)。状压DP会把每种用法(比如用了第1、3个金币)编码成二进制 1010(从右往左第0位开始),即十进制10,然后用dp[10][...]来记录此时的状态。

常用位运算技巧

由于状态存在一个整数里,需要用位运算来操作。下面几个操作是状压DP的“基础工具”:

1. 表示所有状态总数

  • (1 << n) 表示2^n,即所有可能的状态数。例如n=3时,1<<3=8,状态从0到7。

2. 检查某一位是否为1(某物品是否被选)

  • mask & (1 << k) 如果结果非0,则第k位为1,即第k个物品已被选择。 例子:​ mask=5(二进制0101),检查第2位(从0开始):(5 & (1<<2)) = 5 & 4 = 4,非0,说明第2个物品(即第3个)被选了。

3. 把某一位设为1(选择物品)

  • mask | (1 << k) 例子:​ mask=5(0101),想选第1个物品(第1位):5 | (1<<1) = 5 | 2 = 7(0111)。

4. 把某一位设为0(取消选择)

  • mask & ~(1 << k) 例子:​ mask=7(0111),取消第1位:7 & ~(1<<1) = 7 & ~2 = 7 & 5 = 5(0101)。

5. 枚举一个状态的所有子集(重要技巧)

cpp
for (int sub = state; sub; sub = (sub - 1) & state) {
    // 对子集 sub 进行处理
}

这个循环会遍历 state 的所有非空子集(包括state本身)。例如state=5(101),子集有5(101)、4(100)、1(001)。它效率很高,每个子集恰好枚举一次。

核心思想:状态设计与转移

状压DP的关键是把“当前选了哪些物品”作为一维状态,有时还需要另一维来表示“最后的位置”或“当前背包容量”等。常见的状态定义:

  • dp[mask]:只考虑mask中的物品时,某个最优值。
  • dp[mask][last]:已经选了mask中的物品,并且最后一个选定的是 last 时的最优值(如最短Hamilton路径)。

转移时​​,从当前mask出发,尝试加入一个还没选的新物品,更新新状态。

新手容易犯的错误

  1. 位运算优先级搞错 mask & (1<<k) 外围的括号不能少。写成 mask & 1<<k 会先计算 mask & 1,然后左移,结果完全错误。建议养成加括号的习惯。
  2. 忘记初始化 通常要将 dp 数组初始化为极大值(如 0x3f3f3f3f),然后把起点状态(如只包含第0个物品)设为0。漏掉这一步会导致答案错乱。
  3. 下标搞反 二进制位从右往左是第0位、第1位……对应物品0、1、2……。小心别把第k个物品对应 1<<k 写成 1<<(k-1)。
  4. 循环顺序不对 在最短路径问题中,外层循环必须是 mask 从小到大,这样才能保证在转移时,dp[mask][last] 已经被计算好。如果把 last 循环放在外层,可能会使用还未更新的状态。
  5. 范围越界 如 dp[1<<n][n] 会导致数组越界,因为 1<<n 是状态总数,但下标最大是 (1<<n)-1。数组大小的第二维也应是n。

完整示例:最短Hamilton路径(旅行商简化版)

问题:有n个城市(这里n=4),城市间的距离已知,从城市0出发,每个城市恰好经过一次,最后回到城市0,求最短路径长度。

我们选用 dp[mask][last] 表示已经走过mask中的城市,当前最后到达的是 last,且起点0已经包含在mask中。初始状态:dp[1][0]=0(只走了城市0)。转移:从当前状态尝试走到下一个未访问城市next,更新新状态。最后答案:遍历所有最后城市last(不含0),加上从last回到0的距离。

下面是带详细中文注释的完整代码:

cpp
#include <iostream>
#include <cstring>   // 用于 memset
#include <algorithm> // 用于 min
using namespace std;

const int INF = 0x3f3f3f3f;  // 一个很大的数,代表无穷大
int n = 4;                   // 城市数量
// 城市间距离矩阵,dist[i][j] 表示从 i 到 j 的距离
int dist[4][4] = {
    {0, 2, 9, 10},
    {1, 0, 6, 4},
    {15, 7, 0, 8},
    {6, 3, 12, 0}
};

// dp[mask][last]:已经访问过的城市集合为mask,最后停在last的最短路径长度
// mask 用二进制表示,第 i 位为1表示城市 i 已访问
int dp[1 << 4][4];   // 1<<4 = 16,状态总数16

int main() {
    // 初始化所有dp值为无穷大
    memset(dp, INF, sizeof dp);
    // 起点:只访问了城市0(mask=1),最后在0,距离为0
    dp[1][0] = 0;

    // 枚举所有访问状态(mask 从1到15)
    for (int mask = 1; mask < (1 << n); mask++) {
        // 枚举当前最后所在城市 last
        for (int last = 0; last < n; last++) {
            // 如果 last 不在 mask 中,跳过(不可能的状态)
            if (!(mask & (1 << last))) continue;
            // 尝试从 last 走到下一个城市 next
            for (int next = 0; next < n; next++) {
                // 如果 next 已经访问过,跳过
                if (mask & (1 << next)) continue;
                // 新状态:加入 next 城市
                int newMask = mask | (1 << next);
                // 更新更短路径
                dp[newMask][next] = min(dp[newMask][next],
                                        dp[mask][last] + dist[last][next]);
            }
        }
    }

    // 计算最终答案:必须访问所有城市(mask = (1<<n)-1),最后回到城市0
    int ans = INF;
    int fullMask = (1 << n) - 1;  // 所有位全为1,即15
    for (int last = 1; last < n; last++) {
        // 从 fullMask 状态,最后在 last,加上返回0的距离
        ans = min(ans, dp[fullMask][last] + dist[last][0]);
    }
    cout << "最短Hamilton路径长度: " << ans << endl;
    return 0;
}

输出结果​​:运行后得到13(具体路径:0 → 1 → 3 → 2 → 0)。

什么时候使用状压DP?

  • 当问题涉及“子集”、“选择集合”、“顺序或排列”时。典型问题:最短Hamilton路径(旅行商)、任务分配、棋盘覆盖、集合划分等。
  • 状态总数 2^n 必须可接受。一般n ≤ 20,最多22(再大会超内存或超时)。如果n=20,状态数约100万,再乘上n=20,约2000万操作,C++勉强能过。
  • 如果n更大,需要考虑其他优化(如折半搜索、启发式算法)。

相关知识点指引

  • 位运算基础​​:掌握 &、|、~、<<、>> 的用法和优先级。
  • 动态规划入门​​:学习背包DP、线性DP,理解状态定义和转移。
  • 子集枚举与状态压缩​​:可以进一步了解“子集DP”如“莫比乌斯变换”或“子集卷积”。
  • 最短Hamilton路径​​:这是状压DP的经典例题,理解后可以尝试“旅行商问题”(每个城市只去一次,求最短回路)。

状压DP就像给你的记忆装了一个“压缩包”,用一个整数记住一大串选择。虽然它只能处理小规模数据,但它是解决组合优化问题的一把瑞士军刀。下次遇到n=15的“选或不选”问题,不妨试试用二进制位来记忆状态!

同类知识点