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

原标题：算法竞赛专题解析│四边形不等式优化
《算法竞赛入门到进阶》的第7章“动态规划” ，讲解了DP的概念，以及线性DP、区间DP、树形DP、数位DP、状态压缩DP等应用场景。
本文以及后续几篇，将介绍DP的优化技术。
四边形不等式DP优化涉及的证明比较复杂，如果先给出定义和证明会让人迷惑，所以本文的组织结构是：先给出应用场景，引导出四边形不等式的概念，再进行定义和证明，最后用例题巩固。
四边形不等式DP优化，虽然理论有点复杂，但是编码很简单。
*本文内容由罗勇军老师提供。
01
理论背景
四边形不等式（quadrangleinequality）应用于DP优化，是一个古老的知识点。它起源于Knuth（高纳德）1971年的一篇论文，用来解决最优二叉搜索树问题。 1980年，储枫（F.FrancesYao ，姚期智的夫人）做了深入研究，扩展为一般性的DP优化方法，把一些复杂度O(n3)的DP问题，优化为O(n2) 。所以这个方法又被称为“Knuth-YaoDPSpeedupTheorem” 。
02
应用场合
有一些常见的DP问题，通常是区间DP问题，它的状态转移方程是：
dp[i][j]=min(dp[i][k]+dp[k+1][j]+w[i][j])
其中i<=k<j ，初始值dp[i][i]已知。 min()也可以是max() ，见本篇第6小节的说明。
方程的含义是：
（1）dp[i][j]表示从i状态到j状态的最小花费。题目一般是求dp[1][n] ，即从起始点1到终点n的最小花费。
（2）dp[i][k]+dp[k+1][j]体现了递推关系。 k在i和j之间滑动， k有一个最优值，使得dp[i][j]最小。
（3）w[i][j]的性质非常重要。 w[i][j]是和题目有关的费用，如果它满足四边形不等式和单调性，那么用DP计算dp的时候，就能进行四边形不等式优化。
这类问题的经典的例子是“石子合并” ，它的转移矩阵就是上面的dp[i][j] ， w[i][j]是从第i堆石子到第j堆石子的总数量。
石子合并
题目描述：
有n堆石子排成一排，每堆石子有一定的数量。将n堆石子并成为一堆。每次只能合并相邻的两堆石子，合并的花费为这两堆石子的总数。经过n-1次合并后成为一堆，求总的最小花费。
输入：测试数据第一行是整数n ，表示有n堆石子。接下来的一行有n个数，分别表示这n堆石子的数目。
输出：总的最小花费。
输入样例：
3
245
输出样例：
17
提示：样例的计算过程是：第一次合并2+4=6；第二次合并6+5=11；总花费6+11=17 。
在阅读后面的讲解时，读者可以对照“石子合并”这个例子来理解。注意，石子合并有多种情况和解法，详情见本文的例题“洛谷P1880石子合并” 。
dp[i][j]是一个转移矩阵，如何编码填写这个矩阵？复杂度是多少？如果直接写i、j、k的3层循环，复杂度O(n3) 。
注意3层循环的写法。 dp[i][j]是大区间，它从小区间dp[i][k]和dp[k+1][j]转移而来，所以应该先计算小区间，再逐步扩展到大区间。
for(inti=1;i<=n;i++)
dp[i][i]=0;//初始值
for(intlen=2;len<=n;len++)//len：从小区间扩展到大区间
for(inti=1;i<=n-len+1;i++){//区间起点i
intj=i+len-1;//区间终点j
for(intk=i;k<j;k++)//大区间[i,j]从小区间[i,k]和[k+1,j]转移而来
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);
}
03
四边形不等式优化
只需一个简单的优化操作，就能把上面代码的复杂度变为O(n2) 。这个操作就是把循环i≤k<j改为：
s[i][j?1]≤k≤s[i+1][j]
其中s[i][j]记录从i到j的最优分割点。在计算dp[i][j]的最小值时得到区间[i,j]的分割点k ，记录在s[i][j]中，用于下一次循环。
这个优化被称为四边形不等式优化。下面给出优化后的代码，优化见注释的几行代码。
for(i=1;i<=n;i++){
dp[i][i]=0;
s[i][i]=i;//s[][]的初始值
}
for(intlen=2;len<=n;len++)
for(inti=1;i<=n-len+1;i++){
intj=i+len-1;
for(k=s[i][j-1];k<=s[i+1][j];k++){//缩小循环范围
if(dp[i][j]>dp[i][k]+dp[k+1][j]+w[i][j]){//是否更优
dp[i][j]=dp[i][k]+dp[k+1][j]+w[i][j];
s[i][j]=k;//更新最佳分割点
}
}
}
代码的复杂度是多少？
代码中i和k这2个循环，优化前是O(n2)的。优化后，每个i内部的k的循环次数是s[i+1][j]?s[i][j?1] ，其中j=i+len?1 。那么：
i=1时， k循环s[2][len]?s[1][len?1]次。
i=2时， k循环s[3][len+1]?s[2][len]次。
…
i=n?len+1时， k循环s[n?len+2][n]?s[n?len+1][n+1]次。
上述次数相加，总次数：
s[2][len]?s[1,len?1]+s[3][len+1]?s[2,len]+…+s[n+1,n]?s[n][n]