引言
dp
所要解决的是多阶段决策问题，它利用递归的思想，将规模为n的问题转化为规模较小的问题，直到转化为小到能够直接求解的子问题。通常来说这样做时间复杂度是指数级的，但是如果所有不同的子问题的数目是多项式级别，那么多项式时间就可以解决这个问题，这就是
dp
的本质
dp有三个要素：
(1)所有不同的子问题组成的表
(2)问题解决的依赖关系，这可以看成是一个
图
(3)填充子问题表的顺序（实际上是这个图的一个拓扑排序）
如果状态数量为O(nt)，转移需要依赖于其它O(ne)个子问题，那么称这个问题是tD/eD的
这样可以得到四类典型的动态规划方程
1D/1D:已知D[0]，方程为
E[j]=min
{
D[i]+w(i,j)
}
f(j)≤i<j
2D/0D:已知D[i][0]和D[0][j]，方程为
E[i][j]=min
{
D[i−1][j]+xi,D[i][j−1]+yi,D[i−1][j−z]+zi,j
}
2D/1D:已知D[i][i]=0，方程为
E[i][j]=w(i,j)+min
{
C[i,k−1]+C[k,j]
}
i<k≤j
2D/2D:已知D[i,0]和D[0,j]，方程为
E[i][j]=min
{
D[i′][j′]+w(i′+j′,i+j)
}
0≤i′<i,0≤j′<j
dp问题最直接的算法是O(ne+t)的，但我们不满足与此，于是产生了对应的优化手段
dp
优化无外乎状态优化和转移优化两种手段，状态优化往往依赖于具体题目而变，我们主要研究的是转移优化，转移优化常见的手段有：斜率优化，四边形不等式优化和具体数据结构优化等等，还有一类特殊的针对递推线性的优化即矩阵乘法
一些准备知识
移动窗口：单调队列简介
单调队列是应对较为简单的具有单调性的问题的有力手段，而单调队列的使用不外乎下面五个要点
(1)维护区间最值：维护一段区间内的最优决策
(2)区间出现平移：拓展地来看，区间左右端点都单调即可
(3)去除无用状态：显然如果在某一时刻决策i比决策j先出现，并且决策i比决策j劣，那么在j出现后我无论如何都不会选择决策i，决策i在此之后就是无用的
(4)保持队列单调
：由前面我们知道，队列里的决策时刻满足后面的决策比前面的决策后出现，且更劣
(5)
最优选择在队首：如果后面有一个决策比队首更优，那么它将成为队首，由队列的单调性也可知这一点
动态凸壳：平衡树的应用
前面提到这里的单调性经常与凸包挂钩，而我们时常要维护的是决策点在决策平面上的一个上凸壳或是下凸壳
维护一个凸壳我们通常会使用平衡树，对于一个点(x,y)，我们以x为平衡树的关键字维护，每次插入点就查找前驱后继，然后利用凸性质删去左右不符合要求的点即可
动态凸壳：神器的CDQ分治
在动态凸壳问题中我们还可以用CDQ分治来解决，这里不多赘述了。
1D/1D优化
f[i]=min
{
f[j]+w(i,j)
}
第一种情况：分离决策与状态
这一类优化针对的是这样一类
w(i,j)
w(i,j)=μ(i)+ϕ(j)
也就是说
w(i,j)可以拆成分别只与i有关的函数μ和只与j有关的函数ϕ
(1)
f(j)单调，就符合了我们前面所说的单调队列优化，直接用即可
(2)
f(j)不单调，即一个普通的区间最值查询，需要线段树这样的数据结构来维护了
第二种情况：斜率优化
这一类优化针对的是这样一类方程
f(i)=min
{
ai∗xj+bi∗yj
}
对于每一个决策j来说，xj,yj是唯一确定的，我们
将每一个决策视作一个点
(xj,yj)，画在决策平面上
现在我们的决策平面上有很多点，那么我要寻找的是这样一个点使得
P=ai∗x+bi∗y最小
我们将这个式子变形，有
y=−aibi+Pbi
这个式子代表的是一个直线，这个直线过决策点
(x,y)
，且斜率为一个定值，而
P
最优就意味着纵轴截距最优，也就是说，现在我过每一个决策点作一条相同斜率的直线，求纵轴截距最优的那个点
显然这个点只可能存在于所有点的凸壳上（具体是上凸壳还是下凸壳视情况而定），在凸壳上寻找这个点我们只需要二分斜率即可（斜率单调的话直接可以用第一个点或最后一个点），而维护凸壳我们使用平衡树即可（如果横坐标单调就不用这么麻烦了，使用单调队列即可）
第三种情况：决策单调性优化
这一类优化针对的是这样一类方程
f(i)=min(f(j)+w(i,j))
且w(i,j)满足这样一个凸不等式
w(i,j+1)−w(i,j)>=w(i+1,j+1)−w(i+1,j)
此时我们称w是凸的
注：满足这个不等式就意味着w满足四边形不等式，下面会提到
满足这个不等式等价于
用k(x)表示状态x的最优决策，对任意i≤j,有k(i)≤k(j)
这样，我们可以使用一个栈来维护数据，栈中的每一个元素保存每一个决策是最优的起始位置和终止位置（这显然是一个区间，我们称之为这个决策的作用区间），显然这些区间相互连接且递增
首先我们要寻找最优决策就是要寻找当前状态在哪个决策的作用区间里，由区间的单调性我们二分即可
每次我们还要加入一个新决策，我们从后往前扫描栈，扫到一个老决策的时候，我们做这样两件事：
(1)
如果这个老决策的作用区间的起始位置仍然不如新决策优，那么我们弹出老决策，将老决策的作用区间整个合并到新决策中，继续往前扫
(2)
如果不满足前面的条件，在老决策的作用区间中二分出新决策起作用的起始位置，将老决策分割，新决策入栈，结束扫描过程
2D/1D优化：四边形不等式优化
f(i,j)=w(i,j)+min
{
f(i,k−1)+f(k,j)
}
四边形不等式
假如对于i<i′<j<j′，有w(i,j)+w(i′,j′)≤w(i′,j)+w(i,j′)，则称w满足四边形不等式
区间包含关系的单调性
假如对于i<i′<j<j′，有w(i′,j)≤w(i,j′)，则称w满足区间包含关系的单调性
【定理1】
如果w满足四边形不等式，那么f也满足四边形不等式
我们定义
s(i,j)为f(i,j)的最优决策
【定理2】
s(i,j−1)≤s(i,j)≤s(i+1,j)
这样转移方程从原来的
f(i,j)=w(i,j)+min
{
f(i,k−1)+f(k,j)
}
i≤k≤j
变成了
f(i,j)=w(i,j)+min
{
f(i,k−1)+f(k,j)
}
s(i,j−1)≤k≤s(i+1,j)
复杂度从
O(n3)变成了O(n2)
线性递推优化：矩阵乘法
一般地，对于
m
项递推式，我们记递推式为
fn+m=∑m−1i=0bifn+i
我们就可以把递推式写成如下矩阵形式
⎡⎣⎢⎢⎢⎢an+man+m−1⋮an+1⎤⎦⎥⎥⎥⎥
=
⎡⎣⎢⎢⎢⎢⎢⎢⎢bm−110⋮0bm−201⋮0⋯⋯⋯⋱⋯b100⋮1b000⋮0⎤⎦⎥⎥⎥⎥⎥⎥⎥
×
⎡⎣⎢⎢⎢⎢an+m−1an+m−2⋮an⎤⎦⎥⎥⎥⎥
然后就可以在
O(m3logn)
时间内解决
