首页 > 代码库 > 区间动规平行四边形优化
区间动规平行四边形优化
平行四边形优化，是一种在一类区间动规中减少时间复杂度的方法。
有方程：m(i,j)=min(m(i,k)+m(k+1,j)+w(i,j)),s(i,j)为最优点取到值。
公式：如果有w(i, j)+w(i′, j′)≤w(i′, j)+w(i, j′) 那么我们称函数 w 满足四边形不等式。
就有s(i, j)≤s(i, j + 1)≤s(i + 1, j + 1)
证明思路如下：
我们先要证明：m(i,j)+m(i′,j′)≤m(i′,j)+m(i,j′),i≤i′< j≤ j′ 。
分部证明，每部都用数学归纳法证明，用前面一部作为初始条件：
- i=i′或j= j′
- i<i′= j< j′
- i<i′< j< j′
然后再证：s(i, j)≤s(i, j + 1)≤s(i + 1, j + 1)
我们令mk (i, j)表示决策变量取k的时候目标函数的值。
有上面证明的加上w(i, j)+m(i,k?1)+w(i, j+1)+m(i,k′?1) 。
构造出：mk (i, j)?mk′ (i, j)≤mk (i, j+1)?mk′ (i, j+1) 。
就能证明s(i, j +1)≥ s(i, j) 。另一边证明同理。
详细证明：http://files.cnblogs.com/files/SXia/DP平行四边形优化.pdf
区间动规平行四边形优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。