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

参考

参考博文：四边形不等式优化讲解（详解）作者：NOIAu 来源：CSDN（有证明过程）
参考书籍：《算法以数与信息学竞赛》P152

引入

对于DP问题常见的状态转移方程：

dp[i][j]=min{dp[i][k]+dp[k+1][j]}+w[i][j]} (i<k<j)

此方程的时间复杂度为O(n^3)，这种复杂度基本是不可接受的（数据量超过100就会TLE），而通过四边形不等式和决策单调就可以把复杂度降为O(n^2)

目标

对于原状态转移方程，对k值的遍历复杂度为n，而四边形不等式&决策单调优化的就是k值的遍历过程。

四边形不等式&决策单调

  • 如果函数w满足：

    w[a,c] + w[b,c] \leq w[b,c]+w[a,d]（a<b<c<d）

    则w满足四边形不等式（简称w为凸）

  • 如果函数w满足：

    w[i,j] \leq w[i'][j'] ([i,j]\subseteq[i',j'])

    则说w关于区间包含关系单调

基于这两个定义可以证明：

  • 定理1：如果w同时满足四边形不等式和区间单调关系，则dp也满足四边形不等式。
  • 定理2：定理1条件满足时让dp[i,j]取最小的k值为K[i,j]，则K[i,j-1] \leq K[i,j] \leq K[i+1,j]
  • 定理3：w为凸当且仅当 w[i,j] + w[i+1,j+1] \leq w[i+1,j] + w[i,j+1]

实际上 w[i,j] + w[i+1,j+1] \leq w[i+1,j] + w[i,j+1]，只需要证明：
f(j) = w(i+1,j) - w(i,j)关于 j 递减，或f(i) = w(i,j+1)-w(i,j)关于i递减。

定理3的是用于验证w是否为凸的。

我们可以发现，如果满足定理1，那么通过定理2，决策范围变为了K[i,j-1] 到 K[i+1,j]。

需要注意的地方

我们取K[i,j]时，需要K[i,j-1] 和 K[i+1,j]已经计算完成，那么遍历的顺序需要是，i从大到小，j从小到大。

实际上可以先用O(n^3)的方法打表，看看决策是否单调，或者满足凸和区间单调。

时间复杂度的证明：

动态规划加速原理之四边形不等式 作者：赵爽 来源：百度文库
看了很多的博文，以及上方的证明过程，还是不明白O(n^2)的计算方法。留个坑

练习题：

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

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。