状压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 下,通常使用二进制来表示某些东西在某一时刻下的状态,然后需要根据这些状态,遍历它的所有子集,进行暴力搜索。
举例:
[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
  • 101
实现方法:
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
 
 
你觉得这篇文章怎么样?
YYDS
比心
加油
菜狗
views

Loading Comments...