算法竞赛专题解析│四边形不等式优化( 二 ) ：算法竞赛专题解析│四边形

=s[n?len+2][n]?s[1][len?1]
<n
i和k循环的时间复杂度优化到了O(n) 。总复杂度从O(n3)优化到了O(n2) 。
在后面的四边形不等式定理证明中，将更严谨地证明复杂度。
下图给出了四边形不等式优化的效果， s1是区间[i,j?1]最优分割点， s2是区间[i+1,j]的最优分割点。

文章图片
▍图1四边形不等式优化效果
读者对代码可能有2个疑问：
（1）为什么能够把i<=k<j缩小到s[i][j?1]≤k≤s[i+1][j]？
（2）s[i][j?1]≤s[i+1][j]成立吗？
下面几节给出四边形不等式优化的正确性和复杂度的严谨证明，解答了这2个问题。
04
四边形不等式定义和单调性定义
在四边形不等式DP优化中，对于w ，有2个关键内容：四边形不等式定义、单调性。
（1）四边形不等式定义：设w是定义在整数集合上的二元函数，对于任意整数i≤i′≤j≤j′ ，如果有w(i,j)+w(i′,j′)≤w(i,j′)+w(i′,j) ，则称w满足四边形不等式。
四边形不等式可以概况为：两个交错区间的w和，小于等于小区间与大区间的w和。
为什么被称为“四边形”？把它变成一个几何图，画成平行四边形，见下面图中的四边形i′ijj′ 。图中对角线长度和ij+i′j′大于平行线长度和ij′+i′j ，这与四边形的性质是相反的，所以可以理解成“反四边形不等式” 。请读者注意，这个“四边形”只是一个帮助理解的示意图，并没有严谨的意义。也有其他的四边形画法，下面这种四边形是储枫论文中的画法。当中间两个点i′=j时，四边形变成了一个三角形。

文章图片
【算法竞赛专题解析│四边形不等式优化】▍图2四边形不等式w(i,j)+w(i',j')≤w(i,j')+w(i',j)
定义1的特例是定义2 。
（2）四边形不等式定义2：对于整数i<i+1≤j<j+1 ，如果有w(i,j)+w(i+1,j+1)≤w(i,j+1)+w(i+1,j) ，称w满足四边形不等式。
定义1和定义2实际上是等价的，它们可以互相推导。
（3）单调性：设w是定义在整数集合上的二元函数，如果对任意整数i≤i′≤j≤j′ ，有w(i,j′)≥w(i′,j) ，称w具有单调性。
单调性可以形象地理解为，如果大区间包含小区间，那么大区间的w值超过小区间的w值。

文章图片
▍图3w的单调性w(i,j')≥w(i',j)
在石子合并问题中，令w[i][j]等于从第i堆石子加到第j堆石子的石子总数。它满足四边形不等式的定义、单调性：
w[i][j′]≥w[i′][j] ，满足单调性；
w[i][j]+w[i′][j′]=w[i][j′]+w[i′][j] ，满足四边形不等式定义。
利用w的四边形不等式、单调性的性质，可以推导出四边形不等式定理，用于DP优化。
05
四边形不等式定理（Knuth-YaoDPSpeedupTheorem）
在储枫的论文中，提出并证明了四边形不等式定理。
四边形不等式定理：如果w(i,j)满足四边形不等式和单调性，则用DP计算dp[][]的时间复杂度是O(n2)的。
这个定理是通过下面2个更详细的引理来证明的。
引理1：状态转移方程dp[i][j]=min(dp[i][k]+dp[k+1][j]+w[i][j]) ，如果w[i][j]满足四边形不等式和单调性，那么dp[i][j]也满足四边形不等式。
引理2：记s[i][j]=k是dp[i][j]取得最优值时的k ，如果dp满足四边形不等式，那么有s[i][j?1]≤s[i][j]≤s[i+1][j] ，即s[i][j?1]≤k≤s[i+1][j] 。
定理2直接用于DP优化，复杂度O(n2) 。
06
证明四边形不等式定理
这里翻译储枫论文中对引理1和引理2的证明，并加上了本作者的一些说明。
定义方程c(i,j)：
c(i,i)=0
c(i,j)=w(i,j)+min(c(i,k?1)+c(k,j))i<k≤j(6?1)
前面的例子dp[i][j]和这里的c(i,j)略有不同， dp[i][j]=min(dp[i][k]+dp[k+1][j]+w[i][j]) ，其中w[i][j]在min内部。证明过程是一样的。
公式(6-1)的w要求满足四边形不等式：
w(i,j)+w(i′,j′)≤w(i′,j)+w(i,j′)i≤i′≤j≤j′(6?2)
而且要求w是单调的：w(i′,j)≤w(i,j′)
[i′,j]?[i,j′]
1.证明引理1
引理1：如果w(i,j)满足四边形不等式和单调性，那么c(i,j)也满足四边形不等式：
c(i,j)+c(i′,j′)≤c(i′,j)+c(i,j′)i≤i′≤j≤j′(6?3)
下面证明(6-3) 。
当i=i′或j=j′时(6-3)显然成立，下面考虑另外2个情况：A).i<i′=j<j′和B).i<i′<j<j′ 。
caseA).i<i’=j<j’
代入公式(6-3) ，得到一个“反”三角形不等式（图4的三角形ijj′ ，两边的和小于第三边）：