状态压缩动态规划|曾子愚 's Blog

第一部分：解密“状态压缩动态规划”

“状态压缩动态规划”，听起来很高深，但其实它的核心思想非常朴素。让我们把它拆解成两个部分来理解：动态规划 和 状态压缩。

1. 什么是动态规划 (DP)？

动态规划是一种解决问题的策略，通常用于求解最优化问题。它的核心在于将一个大问题分解为若干个规模更小的、相互关联的子问题，并记录下这些子问题的解，以避免重复计算。DP 的两大基石是 最优子结构 和 重叠子问题。

2. “状态” 在 DP 中的角色

在 DP 中，“状态”是用来描述一个子问题的。例如，在经典的“斐波那契数列”问题中，dp[i] 就是一个状态，表示“第 i 个斐波那契数的值”。在“背包问题”中，dp[i][j] 是一个状态，表示“从前 i 个物品中选取，放入容量为 j 的背包所能获得的最大价值”。

通常，DP 的状态都是用简单的数字或数组下标来表示的。

3. 为什么要“压缩”状态？

当我们遇到这样一类问题时：

问题通常建立在一个网格或者集合上。
当前位置的决策，不仅与前一个位置的“值”有关，还与前一个“整体布局”有关。
这个“整体布局”所包含的信息维度很高，无法用一两个数字来描述。

例如，在棋盘上放棋子，第 i 行的摆放方案，会受到第 i-1 行所有棋子位置的影响。如果我们想定义 dp[i] 为“前 i 行的方案数”，我们会发现无法从 dp[i-1] 推导出 dp[i]，因为我们丢失了第 i-1 行的具体棋子布局。

这时候，状态压缩就登场了。它的精髓在于：用一个整数（通常是二进制数）来表示一个复杂的、多维度的状态。

4. 如何进行“状态压缩”？

最常见的压缩方式是位压缩 (Bitmask)。当我们需要记录一个集合中各个元素“是/否”的状态时，位压缩是绝佳的选择。

例如，一个长度为 N 的棋盘行，每个格子可以放或不放棋子。这 N 个格子的状态就可以用一个 N 位的二进制数来表示：

二进制的第 j 位为 1，代表该行第 j 列放了棋子。
二进制的第 j 位为 0，代表该行第 j 列没放棋子。

这样，一个 (1, 0, 1, 1, 0) 的布局就可以被“压缩”成二进制数 10110，也就是十进制的 22。通过这种方式，我们将一整行的布局信息，浓缩到了一个整数里，这个整数就可以作为 DP 状态的一个维度。

状压 DP 的适用场景

数据范围提示：通常题目的某一维度 N 会非常小（例如 N ≤ 10，N ≤ 12 甚至到 N ≤ 20 左右），因为 2^N 的状态数量会随 N 指数级增长。
问题模型：需要在网格上进行布局、填充，或者涉及集合的子集问题。
转移依赖：当前阶段的状态只与上一个阶段的“压缩状态”有关。在棋盘问题中，第 i 行的决策只与第 i-1 行有关。

第二部分：P1896 [SCOI2005] 互不侵犯 - 状压 DP 实战

现在，我们用刚刚学到的知识来攻克这道题。

1. 问题分析与建模

基本要素：在一个 N×N 的棋盘上放 K 个国王。
核心约束：国王们不能互相攻击（周围 8 个格子）。
目标：求合法的方案总数。
数据范围：N ≤ 9，K ≤ N*N。N 非常小，这是使用状压 DP 的强烈信号。

我们将棋盘问题转化为逐行 DP 的过程。当我们考虑在第 i 行摆放国王时，必须满足两个条件：

第 i 行自身摆放的国王不能相邻。
第 i 行的国王不能与第 i-1 行的国王互相攻击。

为了做出第 i 行的决策，我们必须知道：

已经处理到第几行了。
总共已经放了多少个国王。
第 i-1 行的国王布局是怎样的（以便检查冲突）。

这引导我们定义出 DP 状态。

2. 状态定义

根据上面的分析，一个完备的状态需要包含行数、国王总数、当前行布局这三个信息。

我们可以定义 dp[i][j][k] 为：

i: 当前处理到第 i 行。
j: 第 i 行的布局状态，用一个二进制数表示。
k: 在前 i 行（包括第 i 行）总共摆放了 k 个国王。
dp[i][j][k] 的值：表示满足上述条件的方案总数。

但是，状态 j 的取值范围是 0 到 2^N-1，如果直接用 j 作为下标，DP 数组会很大且稀疏。一个常见的优化是，我们预处理出所有单行内合法的布局状态，并给它们一个唯一的编号。

所以，最终的状态定义是：
dp[i][s_idx][k]：在前 i 行，总共摆放了 k 个国王，且第 i 行的布局是第 s_idx 个合法状态时的方案数。

3. 思考过程与代码讲解

Step 1: 预处理合法状态 (对应代码中的 line 向量)

首先，不是所有 0 到 2^N-1 的二进制串都是合法的行布局。国王在同一行内不能相邻。一个状态 msk 合法的条件是，不能有两个相邻的 1。
用位运算可以很方便地检查：如果 msk & (msk << 1) 的结果不为 0，说明 msk 中至少有一对相邻的 1，这个状态不合法。
例如 N=4, msk = 6 (0110)。msk << 1 是 12 (1100)。0110 & 1100 = 0100 (即 4)，不为 0，所以不合法。

你的代码中这部分逻辑是：

// line 向量用于存储所有单行内合法的状态
line.reserve(n*n+1);
line.push_back(0); // 状态0 (一个国王都不放) 是永远合法的
for(ll msk=0;msk<(1ll<<n);++msk){
    // 这个循环检查 msk 中是否有相邻的 1
    // (msk >> (i-1)) & 1 检查的是第 i-1 位
    // (msk >> i) & 1 检查的是第 i 位
    // 这种写法等价于 (msk & (msk >> 1)) != 0
    if ((msk & (msk >> 1)) == 0) { // 使用更简洁的判断
        line.push_back(msk);
    }
}

你的原代码使用了 goto 和一个更复杂的循环，效果是等价的，但 (msk & (msk >> 1)) == 0 是更常用和简洁的写法。

同时，我们还需要知道每个合法状态 msk 包含多少个国王。这可以用 __builtin_popcount(msk) 快速得到。

Step 2: DP 初始化 (Base Case)

我们的 DP 从第一行开始。对于任何一个合法的单行状态 s（在 line 向量中的一个元素），如果它有 c 个国王，那么在只考虑第一行的情况下，摆放 c 个国王形成这个状态的方案数就是 1。

dp[1][s_idx][c] = 1

这在你的代码中体现为：

// dp[i][状态索引][国王数量]
dp.resize(n+1,std::vector<std::vector<ll>>(line.size(),std::vector<ll>(K+1)));

// 初始化第一行
for(ll j=1;j<line.size();j++){ // 遍历所有合法的状态
    ll num1 = get1n(line[j]); // 获取该状态的国王数
    if(num1 > K) continue;   // 如果国王数超过总数K，跳过
    dp[1][j][num1] = 1;       // 方案数为1
}

注意：你的代码中循环从 j=1 开始，忽略了 line[0] (即不放国王的状态)。这在 K>0 时可能没问题，但对于 K=0 会导致错误答案。一个完整的实现应该将 dp[1][0][0] 初始化为 1，并且所有循环都应该包含索引 0。

Step 3: 状态转移 (The Core Logic)

这是最关键的一步。我们来思考如何计算 dp[i][j][x]，即第 i 行采用状态 line[j]，总共用 x 个国王的方案数。

这个方案数，等于所有能在第 i-1 行与 line[j] 兼容的状态的方案数之和。
假设第 i-1 行的状态是 line[k]，它用了 y 个国王。那么，要计算 dp[i][j][x]，我们需要从 dp[i-1][k][y] 转移过来。
两者需要满足：

国王总数一致：y 加上 line[j] 中的国王数 cur1n 必须等于 x。即 y = x - cur1n。
状态兼容：第 i 行的 line[j] 和第 i-1 行的 line[k] 不能有国王互相攻击。

如何检查兼容性？国王的攻击范围包括正上、左上、右上。

正上冲突：line[j] & line[k]。如果结果不为 0，说明在同一列有国王。
左上冲突：line[j] 的国王与 line[k] 右边的国王冲突。等价于 line[j] & (line[k] << 1)。
右上冲突：line[j] 的国王与 line[k] 左边的国王冲突。等价于 line[j] & (line[k] >> 1)。

如果这三个位运算结果都为 0，则 line[j] 和 line[k] 兼容。

状态转移方程如下：
dp[i][j][x] = Σ dp[i-1][k][x - cur1n]
其中，求和的条件是 line[j] 和 line[k] 兼容。cur1n 是 line[j] 中的国王数。

代码实现：

for(ll i=2; i<=n; i++){ // 从第二行开始，逐行计算
    for(ll j=0; j<line.size(); j++){ // 遍历当前行 i 的所有合法状态 line[j]
        ll cur1n = get1n(line[j]);
        for(ll k=0; k<line.size(); k++){ // 遍历上一行 i-1 的所有合法状态 line[k]
            // 检查兼容性
            if(
                (line[j] & line[k]) == 0       // 正上
                && (line[j] & (line[k]<<1)) == 0 // 左上
                && (line[j] & (line[k]>>1)) == 0 // 右上
            ){
                // 如果兼容，则进行状态转移
                for(ll x=cur1n; x<=K; x++){ // 遍历总国王数
                    // 累加方案数
                    // 当前方案数 = 之前所有兼容的上一行状态的方案数之和
                    dp[i][j][x] += dp[i-1][k][x-cur1n];
                }
            }
        }
    }
}

这里我修改了你的代码，将状态循环从 0 开始，并简化了冲突判断，使其更加清晰和完备。你的原代码逻辑是正确的，但循环边界和判断方式可以优化。

Step 4: 计算最终答案

当我们完成了所有行的计算后，最终的答案就是：在第 N 行（最后一行）完成了 K 个国王摆放的所有方案的总和。
这等于把 dp[n][j][K] 对所有合法的末行状态 j 求和。

ll ans=0;
// 累加最后一行的所有状态，当国王总数为 K 时的方案数
for(ll j=0; j<line.size(); j++){
    ans += dp[n][j][K];
}
std::cout << ans << "\n";

总结

通过这个例子，我们可以看到状压 DP 解决问题的完整流程：

识别信号：发现 N 很小，问题与网格布局相关。
定义状态：将行布局压缩成一个整数，并结合其他必要信息（行号、物品数等）构成 DP 状态 dp[i][state][count]。
预处理：筛选出所有单行内合法的状态，减少 DP 的状态空间。
状态转移：核心步骤。通过位运算检查新旧状态间的兼容性，并据此写出转移方程。
求解：确定初始条件（Base Case），然后根据转移方程递推，最后汇总目标状态得到答案。

希望这份详细的讲解能帮助你彻底理解状态压缩 DP 的思想和这道题的解法！