【DP优化】四边形不等式&决策单调

参考

参考博文：四边形不等式优化讲解（详解）作者：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：如果同时满足四边形不等式和区间单调关系，则dp也满足四边形不等式。
• 定理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()的计算方法。留个坑

---

练习题：

理论都是虚的，实践才是王道。
（参考博文里有）

---