1.前缀/后缀优化
利用O(n)预处理前缀/后缀信息，使得后续调用区段信息时可以O(1)完成。
思想比较简单，也比较容易想到，但是往往因为不想浪费一个线型数组的空间而弃用，其实完全没必要担心这样的空间……
前缀/后缀优化 练习列表
备注:前缀和只是附带优化，与dp类型关系不大
2.单调队列优化
用单调队列维护最值，解决有序扫描的序列问题(滑动窗口)。
转移方程往往可以写作:
$$\large f_i=\frac{max}{min}\ ^{i-1}{j=l_i}{g[j]}+w_i\ ,\ l_i\leq l{i+1}$$
显然，如果我们在同一个区间内发现对于一个g(j)，存在更优的g(k)，由于区间有序右移，故j比k更早消失，对k出现后的所有答案无法做出任何贡献，故将j弹出单调队列。
单调队列的队首元素总是最优的，其出队条件有两种：
1.队首元素不在转移区间内，弹出。
2.新区间内找到了更优的元素，弹出比新值劣的所有元素。
单调队列优化 练习列表
备注:$T_1$是单调队列优化多重背包
3.二分栈决策优化
在下貌似不会呢，留待下一步学习。
二分栈优化 练习列表
备注:二分栈的题目难度往往是NOI+,省选内基本不考察
4.分治优化
在下貌似写不出什么东西，因为没怎么用过呢，稍后试试水再回来写吧。
分治优化 练习列表
备注:分治优化的练习题比较劝退，对着递推式都要好好想一阵子……
5.斜率优化
斜率优化在复赛中考察可能性应该高于上述各种。常常用于接手一些方程类似于单调队列优化，但是不可用其优化的dp题。
不能使用单调队列的原因，主要是因为附加值不再是仅与i,j中的一个相关的值，而往往是与两者都相关的值，比如说：
$$\large f_i=\frac{max}{min}\ ^{i-1}{j=l_i}{g[j]}+sum_i*sum_j\ ,\ l_i\leq l{i+1}$$
由于交叉项sum的出现，单调队列就无法保证弹出的正确性。
此时将式子再多写一个i,k的关系式，不妨令k优于j,我们就可以把两个等式Aj和Ak，利用k优于j的关系相减，使得所有式子中与i相关的量是个定值，如(min为例)：
$$\large f_i=g[j]+sum_i*sum_j ······[A_j]$$
$$\large f_i=g[k]+sum_i*sum_k ······[A_k]$$
$$g[k]+sum_isum_k\leq g[j]+sum_isum_j(A_j\leq A_k)$$
这样就在j,k间建立起了不等关系，这样的不等关系可以用同类项作差相除的方式转成类似斜率的表达式:
$$g[k]-g[j]\leq sum_i*(sum_j-sum_k)$$
$$\frac{g[k]-g[j]}{sum_j-sum_k}\leq sum_i$$
现在我们令前者作为斜率，对斜率维护一个上凸包，即保证其最优即可。
怎么维护？使用单调队列或者单调栈。前者在斜率递增时可用队首维护最优决策；后者在i递增时可使用当前直线斜率转移。（口胡带师）
斜率优化 练习列表
备注1:最近把这些题的式子都重新推一下找找感觉
备注2:$T_2$双倍经验见SP15086
6.矩阵优化递推
主要用于多阶递推式的快速转移取模。
例如，对于
$$f[i]=f[i-1]+2*f[i-3]$$
我们连续推进，可以得到这样的数个式子：
$$f[n]=1f[n-1]+0f[n-2]+2*f[n-3]$$
$$f[n-1]=1f[n-1]+0f[n-2]+0*f[n-3]$$
$$f[n-2]=0f[n-1]+1f[n-2]+0*f[n-3]$$
把系数拆分出来，我们就得到了一个这样的矩阵：
$$A=\begin{bmatrix}1&0&2\1&0&0\0&1&0\end{bmatrix}$$
然后我们发现对于递推矩阵B，存在下列关系：
$$B_n=\begin{bmatrix}f_{n}\f_{n-1}\f_{n-2}\end{bmatrix}$$
$$B_{n-1}*A=B_n$$
$$B_1*A^{n-1}=B_n$$
所以我们发现可以利用矩阵快速幂的方式，对A矩阵进行n-1幂次求值，再使其与B1相乘就得到了结果。
方法简单，主要是别忘了怎么推式子。
矩阵优化递推 练习列表
备注:已经按照难度排序。
7.数据结构优化
考差的不多，但是对于优化时间之类还是很有用。
内容较多，日后填坑。
8.滚维优化
上述内容好像都是时间优化，对于某些空间爆炸的题滚维也是很必要的。
要滚维需满足下列条件：
1.矩阵式递推相邻行之间可以转移，并且不再涉及到以前的状态，所以可以存两行，用完就扔。滚掉行数
2.对于一些多维递推中以1递变的状态，可以滚掉。(其实包含1.)
3.……
9.一些奇怪的优化
杂项，往往是可遇而不可求，很多都是现想出来的，不遇到特定类型的题目几乎用不着（雾）。
- 扫序列的时候在干什么？时间够不够？考虑下随机吗？
话说随机对序列选数问题简直是一大杀伤性算法，因为往往这样的题目数据不会允许递推，搜索也需要极大的剪枝，那为什么不当一个快乐的人呢？
小孩子才做选择，我
全都要无所谓。
- 为什么排个序就不一样？
很大一部分dp的题目需要先对数据进行排序，比如上述的土地征用，这样就能保证顺序递推的正确性。
- 正着推还是倒着推？
记得到的死记，记不到的随缘现推。
10.看看就好的优化
DP凸优化？
WQS二分优化？
带权二分优化？