区间DP----四边形不等式优化
转载自https://blog.csdn.net/u014800748/article/details/45750737
四边形不等式优化条件
在动态规划中,经常遇到形如下式的状态转移方程:
dp[ i ][ j ]=min( dp[ i ][ j ] , dp[i][k-1] + dp[ k ][ j ]+w[ i ][ j ] ) ; (i≤k≤j)(min也可以改为max)
上述的dp(i,j)表示区间[i,j]上的某个最优值。w(i,j)表示在转移时需要额外付出的代价。该方程的时间复杂度为O(N^3)。
什么是”区间包含的单调性“和”四边形不等式“?
(1)区间包含的单调性:如果对于a≤b<c≤d,有w(b,c)≤w(a,d),那么说明w具有区间包含的单调性。(简记为如果小区间包含于大区间中,那么小区间的w值小于等于大区间的w值)
(2)四边形不等式:对于( a < b <= c< d ),如果 w[a][c]+w[b][d]<=w[b][c]+w[a][d]成立,则称函数w[i][j]满足四边形不等式,简记为交叉小于包含
下面给出两个定理
定理一:如果上述的w函数同时满足区间包含单调性和四边形不等式性质,那么函数dp也满足四边形不等式性质。
我们再定义s(i,j)表示dp(i,j)取得最优值时对应的下标(即i≤k≤j时,k处的w值最大,则s(i,j)=k)。此时有如下定理
定理二:假如dp(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)。
即原来的状态转移方程不变,但是k的取值范围大大缩小:
dp[ i ][ j ]=min( dp[ i ][ j ] , dp[ i ][ k-1 ] + dp[ k ][ j ] + w[ i ][ j ] ; ( s(i,j-1) ≤k≤ s(i+1,j) ) ( min也可以改为max)
应用题:hdu 3506 https://www.cnblogs.com/-citywall123/p/10902315.html
相关文章
- 网站高并发优化性能调优总结
- 系统性能优化十大绝招
- Python中的单例模式的几种实现方式的及优化
- SQL优化经验总结34条
- 《java虚拟机》----线程安全和锁优化
- c# 优化代码的一些规则——优先隐式类型[一]
- ASP.NET 性能监控和优化入门
- 数据库内核月报 - 2015 / 09-MySQL · 备库优化 · relay fetch 备库优化
- 微信小程序---- setData 列表性能优化
- Redis Linux系统上的配置优化
- 2021Android性能优化总结最新、最全面、最完整的资料+实战经验分享
- 【最全最详细explain讲解】explain | 索引优化的这把绝世好剑,你真的会用吗?
- 基于蓄电池进行调峰和频率调节研究【超线性增益的联合优化】(Matlab代码实现)
- 【优化模型】指派问题的计算机求解(实例)
- 鲲鹏性能优化十板斧(三)——网络子系统性能调优
- 基于灰狼优化的BP神经网络(预测应用) - 附代码
- 抖音APP告诉我们什么叫真正的性能优化天花板
- Etcd 高可用集群与性能优化