四边形不等式优化dp

系统管理员 2021-01-08 14:11 634阅读 0赞

### 今天第一次学习四边形不等式优化dp，感觉优化效果十分给力，不过数学味道比较浓重，证明比较复杂。因此这里删繁就简，给出关于四边形不等式优化必须要明白的地方，以后直接套用条件即可。 ###

## 四边形不等式优化条件 ##

在动态规划中，经常遇到形如下式的转台转移方程：

m(i,j)=min\{m(i,k-1),m(k,j)\}+w(i,j)(i≤k≤j)（min也可以改为max）

上述的m(i,j)表示区间\[i,j\]上的某个最优值。w(i,j)表示在转移时需要额外付出的代价。该方程的时间复杂度为O(N^3)。

下面我们通过四边形不等式来优化上述方程，首先介绍什么是”区间包含的单调性“和”四边形不等式“

（1）区间包含的单调性：如果对于i≤i'<j≤j'，有w(i',j)≤w(i,j')，那么说明w具有区间包含的单调性。（可以形象理解为如果小区间包含于大区间中，那么小区间的w值不超过大区间的w值）

（2）四边形不等式：如果对于i≤i'<j≤j'，有w(i,j)+w(i',j')≤w(i',j)+w(i,j')，我们称函数w满足四边形不等式。（可以形象理解为两个交错区间的w的和不超过小区间与大区间的w的和）

下面给出两个定理

定理一：如果上述的w函数同时满足区间包含单调性和四边形不等式性质，那么函数m也满足四边形不等式性质。

我们再定义s(i,j)表示m(i,j)取得最优值时对应的下标（即i≤k≤j时，k处的w值最大，则s(i,j)=k）。此时有如下定理

定理二：假如m(i,j)满足四边形不等式，那么s(i,j)单调，即s(i,j)≤s(i,j+1)≤s(i+1,j+1)。

好了，有了上述的两个定理后，我们发现如果w函数满足区间包含单调性和四边形不等式性质，那么有s(i,j-1)≤s(i,j)≤s(i+1,j)。即原来的状态转移方程可以改写为下式：

m(i,j)=min\{m(i,k-1),m(k,j)\}+w(i,j)(s(i,j-1)≤k≤s(i+1,j))（min也可以改为max）

由于这个状态转移方程枚举的是区间长度L=j-i，而s(i,j-1)和s(i+1,j)的长度为L-1，是之间已经计算过的，可以直接调用。不仅如此，区间的长度最多有n个，对于固定的长度L，不同的状态也有n个，故时间复杂度为O(N^2)，而原来的时间复杂度为O(N^3)，实现了优化！今后只需要根据方程的形式以及w函数是否满足两条性质即可考虑使用四边形不等式来优化了。

发表评论取消回复

表情：

评论列表（有 0 条评论，634人围观）

还没有评论，来说两句吧...

相关阅读

相关 jensen不等式(jensen不等式对于凹函数)

用Jensen不等式证明两边取自然对数。。。构造函数：f(x)=xln(x) Jensen不等式jensen不等式及其应用 ?dbname=cjfd1993&file

小咪咪/ 2023年09月26日 00:51/ 0 赞/ 50 阅读

相关琴生不等式

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

墨蓝/ 2022年12月10日 11:29/ 0 赞/ 145 阅读

相关柯西不等式

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

待我称王封你为后i/ 2022年12月10日 11:26/ 0 赞/ 176 阅读

相关均值不等式

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

阳光穿透心脏的1/2处/ 2022年12月10日 10:29/ 0 赞/ 150 阅读

相关四边形不等式优化

因为在动态规划中，有这样的一类问题：比如石子合并问题。状态转移方程 dp\[i\]\[j\]=min\{dp\[i\]\[k-1\]+dp\[k\]\[j\] \}+w\[

落日映苍穹つ/ 2022年09月28日 11:59/ 0 赞/ 172 阅读

相关蓝桥石子合并（区间DP四边形不等式）

算法提高合并石子时间限制：2.0s 内存限制：256.0MB 问题描述　　在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子

古城微笑少年丶/ 2022年05月29日 07:53/ 0 赞/ 211 阅读

相关 Post Office（邮局）之四边形不等式优化dp

目录前言题目解析四边形不等式优化何为四边形不等式何为区间包含单调性四边形不等式性质 DP 优化参考代码（附注释） ------------

男娘i/ 2022年04月01日 10:44/ 0 赞/ 227 阅读

相关等式约束优化与不等式约束优化

在学习SVM的原理时，接触到了等式约束优化与不等式约束优化，下面是根据相关资料自己总结出来的自己的，希望对大家有所帮助，这是第一篇博客。 1.等式约束优化 1.1.问题描述

爱被打了一巴掌/ 2022年03月27日 06:48/ 0 赞/ 350 阅读

相关四边形优化dp入门

参考博客： [https://www.cnblogs.com/zxndgv/archive/2011/08/02/2125242.html][https_www.cnb

红太狼/ 2021年12月14日 02:15/ 0 赞/ 282 阅读

相关四边形不等式优化dp

今天第一次学习四边形不等式优化dp，感觉优化效果十分给力，不过数学味道比较浓重，证明比较复杂。因此这里删繁就简，给出关于四边形不等式优化必须要明白的地方，以后直接套用条件...

系统管理员/ 2021年01月08日 14:11/ 0 赞/ 634 阅读