状压DP

💡

全称为：状态压缩 DP

1. 通用解法思路

2. 必备技巧

2.1 整型转二进制字符串

// 可以根据 i 的范围调整 bitset 的大小
std::string int_to_bit_str(int i) {
    std::bitset<8> bits(i);
    return bits.to_string();
}

2.2 二进制表示下某个状态的子集

因为状压 DP 下，通常使用二进制来表示某些东西在某一时刻下的状态，然后需要根据这些状态，遍历它的所有子集，进行暴力搜索。

举例：

力扣

https://leetcode.cn/problems/fair-distribution-of-cookies/

[LC 2305] 把 n 个饼干，分给 k 个孩子，我们定义 DP 为:

💡

dp[i][j], i 是前 i 个孩子，j 是这些孩子可以分配的饼干的状态，范围为 0 ~ 2^n - 1

假如有 3 个饼干，那么状态有:

000: 没有饼干

100、010、001 : 只剩下一块饼干

110、101、011: 只剩下两块饼干

111: 剩下三块饼干

假如此时 dp[2][3], 即前 2 个小孩可以分配剩下的 101 块饼干，那么需要考虑当前第 i 个小孩，即第 2 个小孩可以分配的情况（也就是 101 的子集），总共是下面三种情况：

100、001

实现方法:

int j = 5; // 101
for (int p = j; p != 0; p = (p - 1) & j) {
    cout << int_to_bit_str(p) << endl;
}
// 00000101
// 00000100
// 00000001

❓

为什么这段代码可以求子集呢？换一种方式来理解就比较容易: 1. 当 p 的最后一位是 1 时，(p-1) 就是把最后一位从 1 变成 0，其他的 1 不变。 2. 当 p 的最后一位是 0 时，(p-1) 会把目前的最后一个 1 变成 0，& 上 j 之后，相当于把 p 的最后一位 1 变成 0，左边的 1 不变，右边的 0 变回 1（与j对齐）。总的来说，每次 (p-1)&j , 都能去掉一个 1，而且是从大到小遍历，不重不漏。

用 j = 21 来看会更加直观：

// 00010101  // 先去掉最后一个1
// 00010100  // 此时最后一位是 0, 最后一个1在中间，把它变成 0 之后，要把后面原来的1，现在的0 给变回来
// 00010001 
// 00010000  // 此时最后一个1在最前面, 把它变成 0 后，把后面原来的 1 全部恢复，继续遍历
// 00000101
// 00000100
// 00000001