状态压缩类动态规划
又叫集合动态规划。
参考学长博客和信息学奥赛一本通。
【基本概念】 通常将以一个集合内的元素信息作为状态且状态总数为指数级别的动态规划称为状态压缩动态规划。
其是一类以集合信息为状态的特殊的动态规划问题，主要有传统集合动态规划与基于连通性状态压缩的动态规划两种。
其原理是通过二进制位运算将状态压缩（用整数表示集合）作为动态规划的状态来解决问题。
通常具备以下两个特点：
- 数据规模的某一维或几维特别小
- 需要具备动态规划问题的两个基本性质：最优性原理、无后效性原则
- 左移： << 相当于*2
- 右移： >> 相当于/2
- 与 ： &
- 或 ： |
- 非 ： !
- 计算当前数二进制最低位的1代表的值：
int lowbit(int x){return x&(-x); } - 判断x二进制的第 i 位是否为0：
int pd(int i,int x){return ((1<<(i-1))&x == 0); } - 将x二进制的第 i 位设置成1：
int setb(int i,int x){return (x|(1<<(i-1))); } - 将x第二进制第 i 位设置成0：
int setb(int i,int x){return (x&~(1<<(i-1))); } - 把x二进制下最靠右的第一个1去掉：x = x & (x-1)
- 计算x二进制下含有1或0的个数：
int num=0； while(x){x = x & (x-1); num++; } - 判断x是否为 2 的 n 次方:
bool pd(int x){ return ((x & (x-1)) == 0); }
代码:
const int inf=0x3f3f3f3f;
const int maxn = 20;
int dp[(1<=0;
s--)
for(int v=0;
v 【使用】 在任意时刻，已经求出最优解的状态与尚未求出最优解的状态在各维度上的分界点组成了 DP 扩展的轮廓，对于某些问题，需要在动态规划的状态中记录一个集合，保存这个轮廓的详细信息，以便进行状态转移。
若集合大小不超过 n，集合中每个元素都是小于 k 的自然数，则可以把这个集合看作一个 n 位 k 进制数，以一个[0, k n k^{n} kn - 1 ]之间的十进制整数的形式作为 DP 状态的一维。
【例题】 【动态规划|动态规划 —— 状压DP (附一些位运算小知识)】//待整理
推荐阅读
- 笔记|如何在Windows11安装安卓子系统（）
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- 数据结构与算法|【算法】力扣第 266场周赛
- 2021年下半年《信息系统项目管理师》真题
- 个人理解|【C语言基础之类型转换】
- 学习分享|【C语言函数基础】
- 个人理解|【C语言实现井字棋及电脑落子优化】
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- 动态规划|暴力递归经典问题