一句话理解
子集 DP：用子集枚举做转移。
为什么要学
3^n 那种。
讲解
对每个 s 枚举 sub⊂s，用 f[sub] 和 f[s^sub] 合并。
例子
集合划分问题。
常见错误
- 写成 4^n。
- sub 与补集重复计算没除/没定序。
第 354 课
子集 DP
🔴 提高 约 12 分钟
练习 做完再看下一课
枚举子集的状压转移可达 O(3^n)。
进度保存在本机浏览器里。
左右方向键也可翻课
第 354 课
子集 DP：用子集枚举做转移。
3^n 那种。
对每个 s 枚举 sub⊂s，用 f[sub] 和 f[s^sub] 合并。
集合划分问题。
枚举子集的状压转移可达 O(3^n)。
左右方向键也可翻课