DP 及其优化

DP

DP 概述

线性 DP

区间 DP

状压 DP

数位 DP

树形 DP

• 树形 DP

• 树形背包

DP优化

状态优化

缩减状态优化

• DP 套 DP（建 DAG 优化）

• 折半优化

状态复用优化

• 长链剖分优化

  • 暂时地，全局偏移优化也放在这里，\(\text{P1600 [NOIP2016 提高组] 天天爱跑步}\) 处。

• 树上启发式合并？？？

转移优化

决策单调性优化

• 单调队列优化

• 斜率优化

• 王钦石二分优化

• 四边形不等式优化

转移压缩优化

• 倍增优化

• 矩阵快速幂优化

• 拉格朗日插值优化（目前可参考 P5469 [NOI2019] 机器人 解题报告）

• 卷积优化（目前可参考 22.8.4 T4 road 解题报告）

• 结合律优化

暂时不知道怎么分类优化

• 分治优化