算法竞赛入门到进阶，四边形不等式DP优化

算法竞赛入门到进阶的第7章“动态规划”讲解了DP的概念，以及线性DP、区间DP、树形DP、数位DP、状态压缩DP等应用场景。

本文以及后续几篇，将介绍DP的优化技术。

四边形不等式DP优化涉及的证明比较复杂，如果先给出定义和证明会让人迷惑，所以本文的组织结构是：先给出应用场景，引导出四边形不等式的概念，再进行定义和证明，最后用例题巩固。

四边形不等式DP优化，虽然理论有点复杂，但是编码很简单。

理论背景

四边形不等式（quadrangle inequality）应用于DP优化，是一个古老的知识点。它起源于Knuth（高纳德）1971年的一篇论文，用来解决最优二叉搜索树问题。1980年，储枫（F. Frances Yao，姚期智的夫人）做了深入研究，扩展为一般性的DP优化方法，把一些复杂度O（n 3 ）的DP问题，优化为O（n 2 ）所以这个方法又被称为“Knuth-Yao DP Speedup Theorem”

应用场合

有一些常见的DP问题，通常是区间DP问题，它的状态转移方程是：

d p 【 i 】 【 j 】 = m i n （ d p 【 i 】 【 k 】 + d p 【 k + 1 】 【 j 】 + w 【 i 】 【 j 】 ）

其中i < = k < j ，初始值d p 【 i 】 【 i 】 已知。m i n （ ） 也可以是m a x （ ） ，见本篇第6小节的说明。

方程的含义是：

1d p 【 i 】 【 j 】 表示从i 状态到j 状态的最小花费。题目一般是求d p 【 1 】 【 n 】 ，即从起始点1 到终点n 的最小花费。

2d p 【 i 】 【 k 】 + d p 【 k + 1 】 【 j 】体现了递推关系。k 在i 和j 之间滑动，k 有一个最优值，使得d p 【 i 】 【 j 】 最小。

3w 【 i 】 【 j 】的性质非常重要。w 【 i 】 【 j 】 是和题目有关的费用，如果它满足四边形不等式和单调性，那么用DP计算dp的时候，就能进行四边形不等式优化。

这类问题的经典的例子是“石子合并”它的转移矩阵就是上面的d p 【 i 】 【 j 】 ，w 【 i 】 【 j 】 是从第i 堆石子到第j 堆石子的总数量。

石子合并

题目描述：

有n堆石子排成一排，每堆石子有一定的数量。将n堆石子并成为一堆。每次只能合并相邻的两堆石子，合并的花费为这两堆石子的总数。经过n-1次合并后成为一堆，求总的最小花费。

输入：数据第一行是整数n，表示有n堆石子。接下来的一行有n个数，分别表示这n堆石子的数目。

输出：总的最小花费。

输入样例：

输出样例：

提示：样例的计算过程是：第一次合并2+4=6；第二次合并6+5=11；总花费6+11=17。

d p 【 i 】 【 j 】 是一个转移矩阵，如何编码填写这个矩阵？复杂度是多少？如果直接写i 、 j 、 k 的3层循环，复杂度O（n 3 ）

注意3层循环的写法。d p 【 i 】 【 j 】是大区间，它从小区间d p 【 i 】 【 k 】 和d p 【 k + 1 】 【 j 】 转移而来，所以应该先计算小区间，再逐步扩展到大区间。

for（ inti= 1； i<=n； i++）

dpii = 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】转移而来

dpij = mindpij dpik + dpk + 1j + wij。

四边形不等式优化

只需一个简单的优化操作，就能把上面代码的复杂度变为O（n 2 ）这个操作就是把循环i ≤ k < j 改为：

s 【 i 】 【 j − 1 】 ≤ k ≤ s 【 i + 1 】 【 j 】

其中s 【 i 】 【 j 】 记录从i到j的最优分割点。在计算d p 【 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】

代码的复杂度是多少？

代码中i 和k 这2个循环，优化前是O（n 2 ）的。优化后，每个i 内部的k 的循环次数是s 【 i + 1 】 【 j 】 − s 【 i 】 【 j − 1 】 ，其中j = i + l e n − 1 。那么：

i = 1 时，k 循环s 【 2 】 【 l e n 】 − s 【 1 】 【 l e n − 1 】次。

i = 2 时，k 循环s 【 3 】 【 l e n + 1 】 − s 【 2 】 【 l e n 】 次。

i = n − l e n + 1 时，k 循环s 【 n − l e n + 2 】 【 n 】 − s 【 n − l e n + 1 】 【 n + 1 】 次。

上述次数相加，总次数：

s 【 2 】 【 l e n 】 − s 【 1 ， l e n − 1 】 + s 【 3 】 【 l e n + 1 】 − s 【 2 ， l e n 】 + … + s 【 n + 1 ， n 】 − s 【 n 】 【 n 】

= s 【 n − l e n + 2 】 【 n 】 − s 【 1 】 【 l e n − 1 】

< n

i 和k 循环的时间复杂度优化到了O（n）总复杂度从O（n 3 ）优化到了O（n 2 ）

在后面的四边形不等式定理证明中，将更严谨地证明复杂度。

下图给出了四边形不等式优化的效果，s 1 是区间【 i ， j − 1 】 最优分割点，s 2 是区间【 i + 1 ， j 】 的最优分割点。

▍图1 四边形不等式优化效果

读者对代码可能有2个疑问：

1为什么能够把i < = k < j缩小到s 【 i 】 【 j − 1 】 ≤ k ≤ s 【 i + 1 】 【 j 】 ？

2s 【 i 】 【 j − 1 】 ≤ s 【 i + 1 】 【 j 】 成立吗？

下面几节给出四边形不等式优化的正确性和复杂度的严谨证明，解答了这2个问题。

四边形不等式定义和单调性定义

在四边形不等式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 ′ i j j ′ 。图中对角线长度和i j + i ′ j ′ 大于平行线长度和i j ′ + 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 值。

▍图3 w的单调性wi， j“ ≥ wi” j

在石子合并问题中，令wij等于从第i堆石子加到第j堆石子的石子总数。它满足四边形不等式的定义、单调性：

w 【 i 】 【 j ′ 】 ≥ w 【 i ′ 】 【 j 】 ，满足单调性。

w 【 i 】 【 j 】 + w 【 i ′ 】 【 j ′ 】 = w 【 i 】 【 j ′ 】 + w 【 i ′ 】 【 j 】 ，满足四边形不等式定义。

利用w 的四边形不等式、单调性的性质，可以推导出四边形不等式定理，用于DP优化。

四边形不等式定理（Knuth-Yao DP Speedup Theorem）

在储枫的论文中，提出并证明了四边形不等式定理。

四边形不等式定理：如果w （ i ， j ） 满足四边形不等式和单调性，则用DP计算d p 【 】 【 】 的时间复杂度是O（n 2 ）的。

这个定理是通过下面2个更详细的引理来证明的。

引理1：状态转移方程 d p 【 i 】 【 j 】 = m i n （ d p 【 i 】 【 k 】 + d p 【 k + 1 】 【 j 】 + w 【 i 】 【 j 】 ） ，如果w 【 i 】 【 j 】 满足四边形不等式和单调性，那么d p 【 i 】 【 j 】 也满足四边形不等式。

引理2：记s 【 i 】 【 j 】 = k 是d p 【 i 】 【 j 】 取得最优值时的k ，如果d p 满足四边形不等式，那么有s 【 i 】 【 j − 1 】 ≤ s 【 i 】 【 j 】 ≤ s 【 i + 1 】 【 j 】 ，即s 【 i 】 【 j − 1 】 ≤ k ≤ s 【 i + 1 】 【 j 】 。

定理2直接用于DP优化，复杂度O（n 2 ）

证明四边形不等式定理

定义方程c （ i ， j ） ：

c （ i ， j ） = w （ i ， j ） + m i n （ c （ i ， k − 1 ） + c （ k ， j ） ） i < k ≤ j （6−1）

前面的例子d p 【 i 】 【 j 】 和这里的c （ i ， j ） 略有不同，d p 【 i 】 【 j 】 = m i n （ d p 【 i 】 【 k 】 + d p 【 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：如果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 ′ 。

case A. i < i’ = j < j’

代入公式（6-3）得到一个“反”三角形不等式（图4的三角形i j j ′，两边的和小于第三边）

c （ i ， j ） + c （ j ， j ′ ） ≤ c （ i ， j ′ ） i < j < j ′（6−4）

现在证明公式（6-4）

假设c （ i ， j ′ ） 在k = z 处有最小值，即c （ i ， j ′ ） = c z （ i ， j ′ ） 。这里定义c k （ i ， j ） 等于w （ i ， j ） + c （ i ， k − 1 ） + c （ k ， j ） 。

有2个对称情况A1）和A2）

case A1. z ≤ j

z 是（ i ， j ′ ） 区间的最优点，不是（ i ， j ） 区间的最优点，所以有：

c （ i ， j ） ≤ c z （ i ， j ） = w （ i ， j ） + c （ i ， z − 1 ） + c （ z ， j ）

在两边加上c （ j ， j ′ ）

c （ i ， j ） + c （ j ， j ′ ） ≤ w （ i ， j ） + c （ i ， z − 1 ） + c （ z ， j ） + c （ j ， j ′ ）

≤ w （ i ， j ′ ） + c （ i ， z − 1 ） + c （ z ， j ′ ）

= c （ i ， j ′ ）

上面的推导时利用了下面2条：

1w 的单调性，有w i ， j ≤ w i ， j ′ 。

2公式6-4的归纳假设：假设z ≤ j ≤ j ′ 时成立，递推出i < j < j ′ 时公式6-4也成立。观察下面的图，有c z ， j + c j ， j ′ ≤ c z ， j ′ ，它满足反三角形不等式。

case A2）.z ≥ j 。是A1）的对称情况。

case B.i < i ′ < j < j ′

假设公式（6-3）右边的小区间c （ i ′ ， j ） 和大区间c （ i ， j ′ ） 分别在k = y 和k = z处有最小值，记为：

c （ i ′ ， j ） = c y （ i ′ ， j ）

c （ i ， j ′ ） = c z （ i ， j ′ ）

同样有2个对称情况B1）和B2）

case B1. z ≤ y

有 c （ i ′ ， j ′ ） ≤ c y （ i ′ ， j ′ ）

和 c （ i ， j ） ≤ c z （ i ， j ）

两式相加得：

c （ i ， j ） + c （ i ′ ， j ′ ）

≤ c z （ i ， j ） + c y （ i ′ ， j ′ ）

= w （ i ， j ） + w （ i ′ ， j ′ ） + c （ i ， z − 1 ） + c （ z ， j ） + c （ i ′ ， y − 1 ） + c （ y ， j ′ ） （6 −5）

公式（6-5）的进一步推导利用了下面2条：

1根据w 的四边形不等式，有w i ， j + w i ′ ， j ′ ≤ w i ′ ， j + w i ， j ′ 。

2根据公式6-3的归纳假设，即假设z ≤ y < j < j ′ 时成立。观察下图，有c z ， j + c y ， j ′ ≤ c y ， j + c z ， j ′ ，满足反四边形不等式。

则公式（6-5）变为：

c （ i ， j ） + c （ i ′ ， j ′ ）

≤ w （ i ′ ， j ） + w （ i ， j ′ ） + c （ i ， z − 1 ） + c （ i ′ ， y − 1 ） + c （ y ， j ） + c （ z ， j ′ ）

≤ c y （ i ′ ， j ） + c z （ i ， j ′ ）

= c （ i ′ ， j ） + c （ i ， j ′ ）

case B2）. z ≥ y 。是B1）的对称情况。

引理1证毕。

用K c （ i ， j ）表示m a x { k ∣ ck（ i ， j ） = c （ i ， j ） } ，也就是使c （ i ， j ） 得到最小值的那些k 中，最大的那个是K c （ i ， j ） 。定义K c （ i ， i ） = i 。K c （ i ， j ） 就是前面例子中的s 【 i 】 【 j 】 。

引理2：K c （ i ， j ） ≤ K c （ i ， j + 1 ） ≤ K c （ i + 1 ， j + 1 ） （6−6）

下面是证明。

i = j时显然成立，下面假设i < j 。

先证明公式（6-6）的第一部分K c （ i ， j ） ≤ K c （ i ， j + 1 ） 。这等价于证明：对于i < k ≤ k ′ ≤ j ，有

c k ′ （ i ， j ） ≤ c k （ i ， j ） ⇒ c k ′ （ i ， j + 1 ） ≤ c k （ i ， j + 1 ） （6−7）

公式（6-7）的意思是：如果c k ′ （ i ， j ） ≤ c k （ i ， j ） 成立，那么c k ′ （ i ， j + 1 ） ≤ c k （ i ， j + 1 ） 也成立。c k ′ （ i ， j ） ≤ c k （ i ， j ）的含义是，在【 i ， j 】 区间，k ′ 是比k 更好的分割点，可以把k ′ 看成【 i ， j 】 的最优分割点。扩展到区间【 i ， j + 1 】 时，有c k ′ （ i ， j + 1 ） ≤ c k （ i ， j + 1 ） ，即k仍然是比k 更好的分割点。也就是说，区间【 i ， j + 1 】 的最优分割点肯定大于等于k ′ 。

下面证明公式（6-7）

根据四边形不等式，在k ≤ k ′ ≤ j < j + 1 时，有

c （ k ， j ） + c （ k ′ ， j + 1 ） ≤ c （ k ′ ， j ） + c （ k ， j + 1 ）

在两边加上 w （ i ， j ） + w （ i ， j + 1 ） + c （ i ， k − 1 ） + c （ i ， k ′ − 1 ） ，得：

c k （ i ， j ） + c k ′ （ i ， j + 1 ） ≤ c k ′ （ i ， j ） + c k （ i ， j + 1 ）

把 ck（i， j） 移到右边：

c k ′ （ i ， j + 1 ） ≤ c k ′ （ i ， j ） + c k （ i ， j + 1 ） − c k （ i ， j ） （ 6 − 8 ）

把（6-7）的c k ′ （ i ， j ） ≤ c k （ i ， j ） 的两边加上c k （ i ， j + 1 ） ：

c k ′ （ i ， j ） + c k （ i ， j + 1 ） ≤ c k （ i ， j ） + c k （ i ， j + 1 ）

c k ′ （ i ， j ） + c k （ i ， j + 1 ） − c k （ i ， j ） ≤ c k （ i ， j + 1 ）

结合（6-8）得c k ′ （ i ， j + 1 ） ≤ c k （ i ， j + 1 ） ，公式（6-7）成立。

同样可以证明，公式（6-6）的右半部分K c （ i ， j + 1 ） ≤ K c （ i + 1 ， j + 1 ） ，在i < i + 1 ≤ k ≤ k ′ 时成立。

引理2说明当i、j增大时，K c （ i ， j ） 是非递减的。

3. 证明四边形不等式定理

利用引理2，可推论出四边形不等式定理，即用DP计算所有的c （ i ， j ） 的时间复杂度是O（n 2 ）的。下面对这一结论进行说明。

用DP计算c （ i ， j ）时，是按δ = j − i = 0 ， 1 ， 2 ， . . . ， n − 1 的间距逐步增加进行递推计算的。具体过程请回顾前面第2节求dpij的代码。从c （ i ， j ）递推到c （ i ， j + 1 ） 时，只需要K c （ i + 1 ， j + 1 ） − K c （ i ， j ） 次最少限度的操作就够了。总次数是多少呢？对一个固定的δ ，计算所有的c （ i ， j ） ， 1 ≤ i ≤ n − δ ， j = i + δ ，次数是：

i = 1时：K c （ 1 + 1 ， 1 + δ + 1 ） − K c （ 1 ， δ + 1 ） = K c （ 2 ， δ + 2 ） − K c （ 1 ， δ + 1 ）

i = 2时：K c （ 2 + 1 ， 2 + δ + 1 ） − K c （ 2 ， δ + 2 ） = K c （ 3 ， δ + 3 ） − K c （ 2 ， δ + 2 ）

i = 3时：K c （ 3 + 1 ， 3 + δ + 1 ） − K c （ 3 ， δ + 3 ） = K c （ 4 ， δ + 4 ） − K c （ 3 ， δ + 3 ）

i = n − δ 时：K c （ n − δ + 1 ， n − δ + δ + 1 ） − K c （ n − δ ， δ + n − δ ） = K c （ n − δ + 1 ， n + 1 ） − K c （ n − δ ， n ）

以上式子相加，次数 = K c （ n − δ + 1 ， n + 1 ） − K c （ 1 ， δ + 1 ） ，小于n 。

对一个δ ，计算次数是O （ n ） 的；有n 个δ ，总计算复杂度是O （ n 2 ）的。

以上证明了四边形不等式定理。

4. min和max

前面讨论的都是min，如果是max，也可以进行四边形不等式优化。此时四边形不等式是“反”的：

w （ i ， j ） + w （ i ′ ， j ′ ） ≥ w （ i ′ ， j ） + w （ i ， j ′ ） i ≤ i ′ ≤ j ≤ j ′

定义：

c （ i ， j ） = w （ i ， j ） + m a x （ a （ i ， k ） + b （ k ， j ） ） i ≤ k ≤ j

引理3：若w、a、b都满足反四边形不等式，那么c cc也满足反四边形不等式。

引理4：如果a 和b 满足反四边形不等式，那么：

K c （ i ， j ） ≤ K c （ i ， j + 1 ） ≤ K c （ i + 1 ， j + 1 ）

i ≤ j

证明与引理1和引理2的证明类似。

一维决策单调性优化

上述的四边形不等式优化，是“二维决策单调性”优化。在“一维决策单调性”的情况下也能优化。

李煜东《算法竞赛进阶指南》“0x5B四边形不等式”指出：状态转移方程 F 【 i 】 = m i n 0 ≤ j < i { F 【 j 】 + v a l （ j ， i ） } ，若v a l 满足四边形不等式，则F 具有决策单调性，可以把DP计算F 【 i 】 的复杂度从O（N 2 ）优化到O（NlogN）

例题

拿到题目后，先判断w是否单调、是否满足四边形不等式，再使用四边形不等式优化DP。

1. 石子合并

题目描述：

在一个圆形操场的四周摆放N堆石子，现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法，计算出将 N 堆石子合并成1堆的最小得分和最大得分

输入：

数据的第 1 行是正整数 N，表示有 N 堆石子。

第 2 行有 N 个整数，第 i 个整数 ai表示第 i 堆石子的个数。

输出：

输出共 2 行，第 1 行为最小得分，第 2 行为最大得分。

样例输入：

样例输出：

题解：

1如果石子堆没有顺序，可以任意合并，用贪心法，每次选择最小的两堆合并。

2本题要求只能合并相邻的两堆，不能用贪心法。贪心操作是每次合并时找石子数相加最少的两堆相邻石子。例如环形石子堆开始是{2， 4， 7， 5， 4， 3}，下面用贪心得到最小值64，但是另一种方法得到63。

3用四边形优化DP求解石子合并的最小值，复杂度是On 2

状态转移矩阵d p 【 i 】 【 j 】 前文已有说明，这里不再赘述。

本题的石子堆是环状的，转换为线形的更方便处理。复制和原来一样的数据，头尾接起来，使n 的数列为2n的数列，变成线形的。

4这一题除了求最小值，还求最大值。虽然最大值也用DP求解，但是它不满足反四边形不等式的单调性要求，不能优化。而且也没有必要优化，可以用简单的推理得到：区间【 i ， j 】 的最大值，等于区间【 i ， j − 1 】和【 i + 1 ， j 】 中的最大值加上w i ， j 。

5石子合并问题的最优解法是GarsiaWachs算法，复杂度Onlogn读者可以参考“洛谷P5569 石子合并”这题N ≤ 40000 N ≤ 40000N≤40000，用DP会超时。

1. 最优二叉搜索树

最优二叉搜索树是Knuth（高纳德）解决的经典问题，是四边形不等式优化的起源。

Optimal Binary Search Tree

题目描述：

给定n 个不同元素的集合 S = （ e 1， e 2， . . . ， e n）有e 1 < e 2 < . . . < e n ，把S 的元素建一棵二叉搜索树，希望查询频率越高的元素离根越近。

访问树中元素e i 的成本cost（e i ）等于从根到该元素结点的路径边数。给定元素的查询频率f （ e 1 ） ， f （ e 2 ） ， . . . ， f （ e n ）定义一棵树的总成本是：

f （ e 1 ） ∗ c o s t （ e 1 ） + f （ e 2 ） ∗ c o s t （ e 2 ） + . . . + f （ e n ） ∗ c o s t （ e n ）

总成本最低的树就是最优二叉搜索树。

输入：

输入包含多个实例，每行一个。每行以1 ≤ n ≤ 250 开头，表示S 的大小。在n 之后，在同一行中，有n 个非负整数，它们表示元素的查询频率，0 ≤ f （ e i ） ≤ 100。

输出：

对于输入的每个实例，输出一行，打印最优二叉搜索树的总成本。

样例输入：

样例输出：

题解：

二叉搜索树（BST）的特点是每个结点的值，比它的左子树上所有结点的值大，比右子树上所有值小。二叉搜索树的中序遍历，是从小到大的排列。第3个样例的最优二叉搜索树的形状见下图，它的总成本是5∗2+10∗1=20。

▍图6 二叉搜索树

题目给的元素已经按照从小到大排列，可以方便地组成一棵BST。

设d p 【 i 】 【 j 】 是区间【 i ， j 】 的元素组成的BST的最小值。把区间【 i ， j 】 分成两部分【 i ， k − 1 】和【 k + 1 ， j 】 ，k 在i 和j 之间滑动。用区间【 i ， j 】建立的二叉树，k 是根结点。这是典型的区间DP，状态转移方程：

d p 【 i 】 【 j 】 = m i n { d p 【 i 】 【 k − 1 】 + d p 【 k + 1 】 【 j 】 + w （ i ， j ） − e 【 k 】 }

w （ i ， j ）是区间和，w （ i ， j ） = f i + f i + 1 + . . . + f j 。当把两棵左右子树连在根结点上时，本身的深度增加1，所以每个元素都多计算一次，这样就解决了cost（e i ）的计算。最后，因为根节点k 的层数是0，所以减去根节点的值e 【 k 】

w（i， j）符合四边形不等式优化的条件，所以d p 【 i 】 【 j 】 可以用四边形不等式优化。

参考书籍

算法竞赛入门到进阶

罗勇军 郭卫斌 编著

定价：59.8元

精彩文章回顾

算法竞赛专题解析A*搜索

算法竞赛专题解析广搜进阶

算法竞赛专题解析剪枝

算法竞赛专题解析搜索基础

算法竞赛专题解析简单数据机构

算法竞赛专题解析并查集

算法竞赛专题解析尺取法

算法竞赛专题解析二分法、三分法

Spark算法实例：词频统计

大数据集群的部署实例｜附

用Excel制作工资条实例｜附素材+

真题解析2017年蓝桥杯软件类省赛传统“送分题”

Java 15新增类Record的工作实例｜附代码

Dart应用Bloc设计模式实例｜附代码

从火种到能源，华为做AI的逻辑链

逻辑回归的MATLAB实践｜附代码

HTML5 实现黑白棋游戏 附代码

本文相关词条概念解析：

四边形

由不在同一直线上四条线段依次首尾相接围成的封闭的平面图形或立体图形叫四边形，由凸四边形和凹四边形组成。任意四边形上的中点连接起来，都是平行四边形。菱形里是矩形，矩形里是菱形，正方形里就是正方形。

石子

石子是广义上的说法，泛指白石子、彩色石子、黑色石子、碎石、砾石、卵石等，可根据自己的需要选用，一般白石子、彩色石子、黑色石子粒径较小，使用与装饰工程，而碎石、砾石、卵石适用于结构，市政，公路，铁路等范围。北魏贾思勰《齐民要术·笨曲并酒》：“受两石以下瓮子，以石子二三升蔽瓮底。”《水浒传》第七十回：“张清把左手虚提长枪，右手便向锦袋中摸出石子。《春渚纪闻·丁晋公石子砚》：“石既登岸，转仄之间若有涵水声。现为中国青年美术家协会副秘书长、中国国家画院张志民工作室画家。

标签：