区间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