DP总结。
线性DP
·LIS
·LCS
`数字三角形
·LCIS（最长公共上升子序列）
背包
01背包
完全背包
多重背包
分组背包
区间DP
用(f[l][r])表示区间([l,r])的最优解，然后枚举区间，用小区间的状态更新大区间的状态。
典型例题：合并石子
环形DP
环形DP的常用套路是断环成链。
·Naptime
·Polygon
树形DP
1、自上而下的递归DP
2、自下而上的拓扑排序DP
例题：没有上司的舞会
背包类树形DP
例题：选课
有后效性的DP
状压DP
·互不侵犯
DP的优化
矩阵加速
待补
单调队列优化
待学
二进制优化
待学
倍增优化
待学
数据结构优化
待补
四边形不等式优化
待学
斜率优化
待学