四边形不等式优化-蒲公英云

四边形不等式优化

因为在动态规划中，有这样的一类问题：比如石子合并问题。

状态转移方程 dp[i][j]=min{dp[i][k-1]+dp[k][j] }+w[i][j] k>i&&k<=j 时间复杂度为 O(n^3)

且有如下一些定义和定理：

如果一个函数w[i][j]，满足 w[i][j]+w[i’][j’]<=w[i][j’]+w[i’][j], i<=i’<=j<=j’ 则称w满足凸四边形不等式.

如果一个函数w[i][j]，满足 w[i’][j]<=w[i][j’] ,i<=i’<=j<=j’ 则称w关于区间包含关系单调.

定理1：如果w同时满足四边形不等式和区间单调关系，则dp也满足四边形不等式

定理2：如果定理1条件满足时让dp[i][j]取最小值的k为K[i][j]，则K[i][j-1]<=K[i][j]<=K[i+1][j]，即K[ i ][ j-1]<=K[ i+1 ][ j ].

注：定理2是四边形不等式优化的关键所在，它说明了决策具有单调性，然后我们可以据此来缩小决策枚举的区间，进行优化

定理3：w为凸当且仅当 w[i][j]+w[i+1][j+1]<=w[i+1][j]+w[i][j+1]

几点说明：

1：定理1的证明比较烦躁，详细的可以见《动态规划算法的优化技巧》毛子青大神的论文

2：定理3其实告诉我们验证w是否为凸的方法，就是固定一个变量，然后看成是一个一元函数，进而判断单调性。

如，我们可以固定j算出w[i][j+1]-w[i][j]关于i的表达式，看它是关于i递增还是递减，如果是递减，则w为凸

3：实际操作中，我们往往并不需要进行烦躁的证明，而只需要打表，然后观察就行了。如w[i][j],dp[i][j]是否满足四边形不等式啊，w[i][j]是否单调啊，决策函数K[i][j]是否满足定理2的不等式关系啊，都可以通过打表来验证一下。

最有代价用d[ i, j ]表示
d[ i , j ]=min{ d [ i,k-1 ]+d[ k+1, j ] }+w[i,j]
其中w[ i , j ]=sum[ i , j ]
四边形不等式
w[a,c]+w[b,d]<=w[b,c]+w[a,d](a<b<c<d) 就称其满足凸四边形不等式
决策单调性
w[i,j]<=w[i’,j’] ([i,j]属于[i’,j’]) 既 i’<=i<j<=j’

于是有以下三个定理

定理一：如果w同时满足四边形不等式和决策单调性 ,则d也满足四边形不等式
定理二：当定理一的条件满足时，让d[i,j]取最小值的k为K[i,j]，则K[i,j-1]<=K[i,j]<=K[i+1,j]
定理三：w为凸当且仅当w[i,j]+w[i+1,j+1]<=w[i+1,j]+w[i,j+1]

由定理三知判断w是否为凸即判断 w[i,j+1]-w[i,j]的值随着i的增加是否递减
于是求K值的时候K[i,j]只和K[i+1,j] 和 K[i,j-1]有关，所以可以以i-j递增为顺序递推各个状态值最终求得结果将O(n^3)转为O(n^2)