动态规划总结
做了很久的dp题，感觉还是略有收获，以下总结如下：
类型
1.线性dp：注意优化技巧。
2.区间dp：注意优化技巧。
3.环形dp：先考虑链，再考虑环。
4.背包问题：
01背包：滚动数组，初始化。
完全背包：枚举顺序。
多重背包：二进制拆位。
混合背包：组合即可。
多维背包：增加状态维数。
分组背包：分开处理即可。
树形背包：改变枚举顺序，可以
泛化背包：合并两个泛化物品的复杂度是
5.树形dp：注意多叉树转二叉树的技巧。
基环树dp：1.找环。 2.对环用环形dp。3.对子树用树形dp。
6.DAG上的dp：注意拓扑序。
7.概率与期望dp：注意期望的线性性质。
8.状压dp：注意斯坦纳树及位运算技巧。
9.数位dp：区间求值转化为前缀和，逐位确定，注意空间和编程复杂度。
10.轮廓线和插头dp：括号表示法。
常见优化技巧
1.动态维护最值（借助递推顺序或桶）。
2.前缀和降维。
3.数据结构维护转移。
4.倍增。
5.二分。
6.矩阵加速。
7.决策单调性。
8.单调队列。
9.斜率优化。
10.四边形不等式（线性dp，区间dp）。
11.将未来费用计算到当前状态或增加维数描述未来决策（即未来dp）。
12.将状态由等值变为范围。
13.差分。
14.分治。