参考
参考博文：四边形不等式优化讲解（详解）作者：NOIAu 来源：CSDN（有证明过程）
参考书籍：《算法以数与信息学竞赛》P152
引入
对于DP问题常见的状态转移方程：
dp[i][j]=min{dp[i][k]+dp[k+1][j]}+w[i][j]} (i<k<j)
此方程的时间复杂度为O()，这种复杂度基本是不可接受的（数据量超过100就会TLE），而通过四边形不等式和决策单调就可以把复杂度降为O(
)
目标
对于原状态转移方程，对k值的遍历复杂度为n，而四边形不等式&决策单调优化的就是k值的遍历过程。
四边形不等式&决策单调
-
如果函数
满足：
则
-
如果函数
则说
基于这两个定义可以证明：
- 定理1：如果
- 定理2：定理1条件满足时让dp[i,j]取最小的k值为K[i,j]，则
- 定理3：
实际上
，只需要证明：
关于 j 递减，或
关于i递减。
定理3的是用于验证是否为凸的。
我们可以发现，如果满足定理1，那么通过定理2，决策范围变为了K[i,j-1] 到 K[i+1,j]。
需要注意的地方
我们取K[i,j]时，需要K[i,j-1] 和 K[i+1,j]已经计算完成，那么遍历的顺序需要是，i从大到小，j从小到大。
实际上可以先用的方法打表，看看决策是否单调，或者满足凸和区间单调。
时间复杂度的证明：
动态规划加速原理之四边形不等式 作者：赵爽 来源：百度文库
看了很多的博文，以及上方的证明过程，还是不明白O()的计算方法。留个坑
练习题：
理论都是虚的，实践才是王道。
（参考博文里有）
