算法设计与分析

Computer Algorithm Design & Analysis

吕志鹏
[Link]@[Link]
群名称：2023秋 算法设计与分析
群 号：
 Chapter 15
Dynamic Programming

动态规划
Advanced Design and Analysis Techniques
最优化问题：这一类问题的可行解可能有很多个。每个解都有
一个值，我们希望寻找具有最优值的解（最小值
或最大值）。

注：这里，我们称这个解为问题的一个最优解（an optimal
solution），而不是the optimal solution，因为最优解也可能

有多个。

—— 这种找最优解的问题通常称为最优化问题。
最优化问题的分类：
根据描述约束条件和目标函数的数学模型的特性和问题的
求解方法的不同，可分为：线性规划、整数规划、非线性规划、
动态规划等问题。而研究解决这些问题的科学一般就总称之为
最优化理论和方法。

在运筹学领域有对最优化理论更深入的研究

本章介绍动态规划（Dynamic Programming，简称DP）
动态规划算法的步骤
1. 刻画一个最优解的结构特征；

2. 递归地定义最优解的值；

3. 计算最优解的值；

4. 利用计算出的信息，构造一个最优解。

注：
1）前三步是动态规划算法求解问题的基础。如果仅需要一个最优解
的值，而非解本身，可以忽略步骤4。
2）如果确实要做步骤4，则有时需要在执行步骤3的过程中维护一些
额外的信息，以便用来构造一个最优解。
3）第三步通常采用自底向上的方法计算最优解；
15.1 钢条切割
Serling公司购买长钢条，将其切割为短钢条出售。不同的
切割方案，收益是不同的，怎么切割才能有最大的收益呢？
n 假设，切割工序本身没有成本支出。

n 假定出售一段长度为i英寸的钢条的价格为pi（i=1,2,…），下
面是一个价格表P。

长度为i英寸的钢条可以为公司带来pi美元的收益

2023-10-21 7
钢条切割问题：

给定一段长度为n英寸的钢条和一个价格表P，求切割钢条方
案，使得销售收益 rn 最大。

分析：如果长度为n英寸的钢条的价格pn足够大，则可能完全
不需要切割，出售整条钢条是最好的收益。

但由于每个pi不同，可能切割后出售会更好一些。

思考：先按pi最大出售，剩余的再按较小pj出售，是否就可以
获得最好的收益？或者按pi/i最大策略依次出售 （贪心策略）
考虑如下n=4的情况。

4英寸的钢条所有可能的切割方案。

最优方案：方案c，将4英寸的钢条切割为两段各长为2英寸的钢
条，此时可产生的收益为10，为最优解。
n 长度为n英寸的钢条共有2n-1种不同的切割方案。
Ø 每一英寸都可切割，共有n-1个切割点

n 如果一个最优解将总长度为n的钢条切割为k段，每段的长度
为ij（1≤j≤k），则有：n=i1+i2+…+ik
得到的最大收益为：rn=pi1+pi2+…+pik

如，从价格表可得以下基本方案：

r1=1，切割方案1=1（无切割） r6=17，切割方案6=6 （无切割）

r2=5，切割方案2=2（无切割） r7=18，切割方案7=1+6或7=2+2+3
r3=8，切割方案3=3（无切割） r8=22，切割方案8=2+6
r4=10，切割方案4=2+2 r9=25，切割方案9=3+6
r5=13，切割方案5=2+3 r10=30，切割方案10=10 （无切割）
10
 对于长度为n（n≥1）的钢条，设rn是最优切割的收益，那么
该如何获得该最优切割？
n 对最优切割，从左往右看，设首次切割在位置i，将钢条分成
长度为i和n-i的两段，令ri和rn-i分别是这两段的最优子切割
收益，则有：
rn= ri+ rn-i

n 一般情况，任意切割点j都将钢条分为两段，长度分别为j和
n-j，1≤j≤n。令rj和rn-j分别是这两段的最优切割收益，则
该切割可获得的最好收益是：r'n= rj+ rn-j

n j和i有什么关系呢？
11
n 这样的j有n种选择(包括不切割)，而最优切割是能够获得最
大收益的切割方案，所以有：

rn  max{r 1rn 1 ,r 2rn  2，

...r jrn j ,...,r n 1 r1 , p n }
j

n 即，首次切割后，将两段钢条看成两个独立的钢条切割问题
实例。若分别获得两段钢条的最优切割收益rj和rn-j，则原问
题的解就可以通过组合这两个相关子问题的最优子解获得。

n 这里体现了该问题最优解的一个重要性质：最优子结构性

Ø 如果rn= ri+ rn-i是最优切割收益，则ri、rn-i是相应子问

题的最优切割收益（为什么？）。
钢条切割问题的朴素递归求解过程：
对切割过程可做如下简化：将钢条从左边切割下长度为i的
一段，然后只对右边剩下的长度为n-i的一段继续进行切割（递
归求解），但对左边的一段不再进行切割。

此时有：
rn  max{p i  rn i }
1 i  n

即，此时，原问题的最优解只包含一个相关子问题（右端
剩余部分）的解，而不是两个。

一个自顶向下的递归求解过程可以描述如下：
 其中，p是价格数组，n是钢条长度。

若n=0，则收益为0。

该过程的效率很差：

n 存在一些相同的子问题，CUT-ROD反复地用一些相同的
参数做重复的递归调用。
 如n=4， CUT-ROD的递归执行过程可以用递归调用树表示为：
从父结点s到子结点t的
边表示从钢条左端切下 结点中的数
长度为s-t的一段，然后 字为对应子
继续递归求解剩余规模 问题的规模
为t的子问题。

一般来说，这棵递归调用树有2n个
结点，其中有2n-1个叶结点。
令T(n)表示对规模为n的问题， CUT-ROD的调用次数，则有：

n 可以证明： （练习15.1-1）
钢条切割问题的动态规划求解
动态规划方法将仔细安排求解顺序，对每个子问题只求解一
次，并将结果保存下来。如果再次需要此子问题的解，只需查找
保存的结果，而不必重新计算。
Ø 动态规划方法需要付出额外的空间保存子问题的解，是一种典
型的时空权衡（time-memory trade-off）。
n 动态规划求解的两种方法
（1）带备忘的自顶向下法（top-down with memoization）

Ø 依旧按照递归的形式编写过程，但处理过程中会保存每
个子问题的解。

Ø 当需要时，过程首先检查是否已经保存过此解。
u 如果是，则直接返回保存的值；

u 否则按照通常的方式计算该子问题。

带备忘：“记住”之前已经计算出来的结果。
通常保存在一个数组或散列表中。
18
辅助数组r[0…n]用于保存子问题的结果。
Ø 初始化为-∞;
Ø 当有新的结果时，r[n]保存结果q;
Ø 当r[n]≥0时，直接引用其中已保存
的值。
（2）自底向上法（bottom-up method）
Ø 将子问题按规模排序：
最小子问题、较小子问题、… 、较大子问题、原问题。
Ø 按由小到大的顺序顺次求解：

当求解某个子问题时，它所依赖的更小子问题都已求解完
毕，结果已经保存，故可以直接引用并组合出它自身的解
。
n 这里采用子问题的自然顺
序：若i<j，则规模为i的
子问题比规模为j的子问
题“更小”。
n 过程依次求解规模为
j=0,1,…,n的子问题。
20
n 对比：带备忘的自顶向下法 Vs 自底向上法

自顶向下
自底向上

2023-10-21 21
n MEMOIZED-CUT-ROD和BOTTOM-UP-CUT-ROD具有相同
的渐近运行时间：Θ(n2)。

证明：略，见P208.

n 通常，自顶向下法和自底向上法具有相同的渐近运行时间。

Ø 在某些特殊情况下，自顶向下法可能没有递归处理所有可能的
子问题（剪枝）。

Ø 由于自底向上法没有频繁的递归函数调用的开销，所以自底向
上法的时间复杂性函数通常具有更小的系数。
n 对比简单递归和动态规划
递归：“硬”求解。整个过
程对存在的重复子问题的重
复计算，造成效率低下。

动态规划：递归只是处理的一部
分。在求解的过程中记录了重复
子问题的解。通过“引用”以前
的计算结果，避免重复计算，提
高效率。
子问题图
当思考一个动态规划问题时，应该弄清楚所涉及的子问题与
子问题之间的依赖关系，可用子问题图描述：

子问题图：用于描述子问题与子问题之间的依赖关系。

Ø 子问题图是一个有向图，每个顶点唯
一地对应一个子问题。
Ø 若求子问题x的最优解时需要直接用
到子问题y的最优解，则在子问题图
中就会有一条从子问题x的顶点到子
问题y的顶点的有向边。
n=4时，钢条切割问题的子问题图。顶点的标号给出了子问题
的规模。有向边(x,y)表示当求解子问题x时需要子问题y的解。
n 子问题图是自顶向下递归调用树的“简化版”或“收缩版”

—— 递归树中所有对应相同子问题的结点合并为子问题图中
的一个单一顶点，相关的边都从父结点指向子结点。
n 自底向上的动态规划方法处理子问题图中顶点的顺序为：

对一个给定的子问题x，在求解它之前先求解邻接至它的
子问题。即，对于任何子问题，仅当它依赖的所有子问题都求
解完成了，才会求解它。

—— 逆拓扑序，深度优先原则进行处理。（22.4节）
基于子问题图“估算”算法的运行时间：
算法的运行时间等于所有子问题求解的时间之和。子问题
图中，子问题对应顶点，子问题的数目等于顶点数。一个子问
题的求解时间与子问题图中对应顶点的“出度”成正比。

因此，一般情况下，动态规划算法的运行时间与顶点和边
的数量至少呈线性关系。
n 重构解
CUT-ROD算法给出了最优收益，但怎么切割的、切割点在
哪里呢？通过扩展上述动态规划算法，在求出最优收益之后，
即可求出切割方案。 数组s用于记录对规模为j的
钢条切割出的第一段钢条的
长度s[j]。

扩展的BOTTOM-UP-CUT-ROD算
法，对长度为j的钢条不仅计
算出最大收益rj，同时记录
切割的第一段钢条的长度sj
n 输出完整的最优切割方案
对已知价格表p和钢条长度n，下述过程能够计算出长度数组
s[1..n]，并输出完整的最优切割方案：

实例：

Ø PRINT-CUT-ROD-SOLUTION(p,7)：1，6

Ø PRINT-CUT-ROD-SOLUTION(p,10)：10
15.2 矩阵链乘法

两个矩阵的乘积：
已知A为p×r的矩阵，B为r×q的矩阵，则A与B的乘积是一
个p×q的矩阵，记为C：
C＝Ap×r ╳ Br×q＝ (cij)p×q，
其中，

cij  a
1 k  r
b , i  1,2,..p, j  1,2,..., q
ik kj

每个cij的计算需要r次乘法（另有r-1次加法，这里仅考虑
元素的标量乘法），则计算C共需要pqr 次标量乘法运算。
n 一个标准的两矩阵乘算法如下：

注：只有两个矩阵"相容"
(compatible)才能相乘。

三重循环结构

2023-10-21 31
矩阵链相乘
n个要连续相乘的矩阵构成一个矩阵链<A1,A2,…,An>,要计
算这n个矩阵的连乘乘积：A1A2...An，称为矩阵链乘问题。

Ø 矩阵链乘满足结合律，不满足交换律。
Ø 矩阵链乘过程相当于在矩阵之间加适当的括号，从而根据
组合关系定义出矩阵链乘的计算模式。

如，已知四个矩阵A1,A2,A3,A4，乘积A1A2A3A4可用五种不同的加
括号方式完成：
(A1(A2(A3A4))) (A1((A2A3)A4))

((A1A2)(A3A4)) ((A1(A2A3))A4)

(((A1A2)A3)A4)
问题：不同的加括号方式代表不同的计算模式，而不同的计算
模式计算矩阵链乘积的代价是不同的。

如，设有三个矩阵的链<A1,A2,A3>，维数分别为10×100,100×5,5×50。
1）如果按((A1A2)A3)的次序完成乘法，则A1与A2乘需要10×100×5 =5000
次标量乘法运算，得一10×5的中间结果矩阵，再继续与A 3 相乘，又需要
10×5×50=2500次标量乘法运算，总共为7500次标量乘法运算。

2）如果按(A 1 (A 2 A 3 ))的次序完成乘法，则A 2 与A 3 乘需要100×5×50

=25000次标量乘法运算，得一100×50的中间结果矩阵，A1与之再次相乘，又
需要10×100×50=50000次标量乘法运算，总共为75000次标量乘法运算。

可见，上述两种方法的计算量相差10倍！

n 矩阵链中的矩阵怎么两两相乘才能使总的代价最小呢？
矩阵链乘法问题(matrix-chain multiplication problem )
给定n个矩阵的链，记为<A1,A2,…,An>，其中i=1,2,…,n，
矩阵Ai的维数为pi-1×pi。求一个完全“括号化方案”，使得计
算乘积A1A2…An所需的标量乘法次数最小。

n 显然，穷举所有可能的括号化方案是不可取的：
此时，可令p(n)表示n个矩阵的链相乘时，可供选择的括号化
方案的数量。则有：

可以证明：P(n)=Ω(2n)
1）最优括号化方案的结构特征
—— 寻找最优子结构

用记号Ai,j表示子问题AiAi+1…Aj通过加括号后得到的一个最
优计算模式，且该计算模式下的最大区间恰好在A k 与A k+1 之间分
开，则有：
(AiAi+1… Ak)(Ak+1 …Aj)

则必须有：(AiAi+1…Ak) 必是“前缀”子链AiAi+1…Ak的一个
最优的括号化子方案，记为Ai,k；同理(Ak+1Ak+2…Aj) 也必是“后
缀”子链Ak+1Ak+2…Aj的一个最优的括号化子方案，记为Ak+1,j。
证明：反证法
如若不然，设A'i,k是<Ai,Ai+1,…Ak>一个代价更小的计算模
式，则由A'i,k和Ak+1,j构造计算过程A'i,j，代价将比Ai,j小，这
与Ai,j是最优链乘模式相矛盾。
对Ak+1,j亦然。

——这一性质称为（该问题的）最优子结构性。
2. 递归求解方案
最优子结构性告诉我们：

整体的最优括号化方案可以通过寻找使最终标量乘

法次数最小的两个最优括号化子方案得到。

形如：(A1Ai+1… Ak)(Ak+1 …An)

到哪里找这样的一个k，使得上述计算的标量乘法次数最小
呢？
（1）递推关系式

令 m[i,j] 为计算矩阵链Ai,j所需的标量乘法运算次数的最小
值,则有

含义：

n 对任意的k(i≤k＜j)分开的子乘积，Ai,k是一个pi-1×pk的矩阵，Ak+1,j是一个
pk×pj的矩阵 。结果矩阵Ai,j是Ai,k和Ak+1,j最终相乘的结果。

n 对m[i,j]和任意k所分开的矩阵链乘<Ai,Ai+1,…, Aj>，m[i,j]等于计算子乘
积Ai,k最小代价m[i,k] + 计算子乘积Ak+1,j的最小代价m[k+1,j] + 这两个子矩
阵最后相乘的代价pi-1pkpj,而这样的k有j-i种可能性,取其中最小者。
n m[1,n]是计算A1,n的最小代价。
 再设s[i,j]，记录使m[i,j]取最小值的k，则可
以依靠s求出最优链乘模式。

下述过程MATRIX-CHAIN-ORDER采用自底向上表格
法计算n个矩阵链乘的最优模式。
 输入序列p=<p0,p1,...,pn>是n个矩阵的维数表示，
矩阵Ai的维数是pi-1×pi，i=1,2,...,n。

m[1,n]是计算A1,n的最小代价
m[1,3] = min{m[1,1]+m[2,3]+30×35×5,
m[1,2]+m[3,3]+30×15×5} m
= min{0+2625+5250，15750+0+2250} 6 1
= 7875 j i
5 15125
2
4 11875 10500 3
例，设 3 9375 7125 5375 4
矩阵 维数 2 7875 4375 2500 3500 5
1 15750 2625 750 1000 5000 6
A1 30×35
0 0 0 0 0 0
A2 35×15
A3 15×5 A1 A2 A3 A4 A5 A6
A4 5×10
A5 10×20 m[i,i] = 0 s
A6 20×25 m[i,i+1] = pi-1pipi+1 6 1
j i
s[i,i+1] = i 5 3 2
3 3 3
4
3 3 3 4
3
5
2 1 3 3 5
1 2 3 4 5
时间复杂度分析
算法的主体由一个三层循环构成。外循环执行n-1次，内层
循环至多执行n-1次，所以MATRIX-CHAIN-ORDER的算法复杂度是
O(n3)。
另，算法需要Θ(n2)的空间保存m和s。
(4)构造最优解
Ø s[i,j]记录了AiAi+1…Aj的最优括号化方案的“首个”分割点k。
u 基于s[i,j]，对AiAi+1…Aj的括号化方案是：

（AiAi+1…As[i,j]）（As[i,j]+1…Aj）

Ø A1…n的最优方案中最后一次矩阵乘运算是：
（A1…s[1,n]）（As[1,n]+1…n）

Ø 用递归的方法求出A1…s[1,n]、As[1,n]+1…n及其它所有子问题的最
优括号化方案。
 根据s求出矩阵链乘的最优计算模式：

例： PRINT-OPTIMAL-PARENS(s,1,6)

( ( A1 ( A2 A3 ) ) ( ( A4 A5 ) A6 ) )
利用动态规划求解问题的方法：
第一步：证明问题满足最优性原理

所谓“问题满足最优性原理”即：问题的最优决策序列具有
最优子结构性。
证明问题满足最优性原理是实施动态规划的必要条件：如果证明
了问题满足最优性原理，则说明用动态规划方法有可能解决该问题。

第二步：获得问题状态的递推关系式（即状态转移方程）

能否求得各阶段间状态变换的递推关系式是解决问题的关键。
f(x1,x2,…,xi) →xi+1 向后递推

或 f(xi,xi+1,…,xn)→xi-1 向前递推
2023-10-21
回顾：
1）不管是钢管切割问题还是矩阵链乘问题，我们都首先讨论了问题
最优解的结构特征，即证明问题的最优解具有最优子结构性：

Ø 钢管切割问题:若s(1,n)为最优切割方案，则第一次切割（假定切割点
在位置k）后得到的两段：s(1,k)和s(k+1,n)也必是最优的子方案。

Ø 矩阵链乘问题:设A1,n是最优括号化方案,“最大子括号”加在Ak后面，
则A1,k和Ak+1,n必是子矩阵链的最优括号化方案。

2）状态转移方程

Ø 钢管切割问题： rn  1max
i n
{p i  rn i }

Ø 矩阵链乘问题：
2023-10-21 46
 动态规划实质上是一种以空间换时间的技术，
它在实现的过程中，需要存储过程中产生的各种状
态（中间结果），所以它的空间复杂度要大于其它
的算法。

n 详见P218~220.
可以用子问题的总数和每个子问题需要考察多少种选择这两个
因素的乘积来粗略分析动态规划算法的运行时间。
n 对于钢条切割问题，共有Θ(n)个子问题，每个子问题最多需要考察n
种选择，因此运行时间为O (n2)。

n 对于矩阵链乘法问题共有Θ(n2)个子问题，每个子问题最多考察n-1
种选择，因此运行时间为Θ(n3)。

也可以用子问题图来做同样的分析。顶点对应一个子问题，需
要考察的选择对应关联至子问题的边。
n 钢条切割问题：n个顶点，每个顶点最多n条边。

n 矩阵链乘法问题n2个顶点，每个顶点最多n-1条边。

n 详见P217.
子问题无关性
能够用动态规划策略求解的问题，构成最优解的子问题间
必须是无关的
所谓子问题无关，是指同一个原问题的一个子问题的解不
影响另一个子问题的解，可以各自独立求解。

n 最长简单路径问题

Ø 子问题间相关，不能用动态规划策略求解。

n 最短路径问题

Ø 子问题不相关，满足最优子结构性，可以用动态规划问
题求解。
n 详见P217~218.
49
如何证明问题的最优解满足最优子结构性呢？
即证明：作为构成原问题最优解的组成部分，对应每个子问题
的部分应是该子问题的最优解。

“剪切-粘贴”（cut-and-paste）技术：
本质上是 反证法证明 ：假定原问题最优解中对应的某个子问题
的部分解不是该子问题的最优解，而存在“更优的子解”，那么我们
可以从原问题的解中“剪切”掉这一部分，而将“更优的子解”粘贴
进去，从而得到一个比最优解“更优”的解，这与最初的解是原问题
的最优解的前提假设相矛盾。因此，不可能存在“更优的子解”。

——所以，原问题的子问题的解必须是其最优解，最优子结构性
成立。
最优解的构造
通常再定义一个表，记录每个子问题所做的选择。当求出
最优解的值后，利用该表回推就可以求取最优方案。
Ø 如矩阵链乘法中的表s[1…n]。

备忘（查表）
为了避免对重复子问题的重复计算，在递归过程中加入备
忘机制。这样当第一次遇到子问题时，计算其解，并将结果存
储在备忘表中。而其后再遇到同一个子问题时，就只简单地查
表，返回其解即可，不用重复计算，节省了时间。
Ø 例：带有备忘的矩阵链乘法（见P220~221）
2023-10-21 51
15.4 最长公共子序列
一个应用背景：基因序列比对。
DNA（Deoxyribonucleic Acid，脱氧核糖核酸）是染色体的主要
组成成分。DNA又是由腺嘌呤(adenine)、鸟嘌呤(guanine)、胞嘧啶
(cytosine)、胸腺嘧啶(thymine)等四种碱基分子（canonical bases）
组成。用它们单词的首字母A、C、G、T来代表这四种碱基，

这样一条DNA上碱基分子的排列被表示为有穷字符集{A,C,G,T}上
的一个串进行表示。

如：两个有机体的DNA分别为
S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA

S2=GTCGTTCGGAATGCCGTTGCTCTGTAAA
 可以通过比较两个有机体的DNA来确定这两个有机体有多么
“相似”。这在生物学上叫做“基因序列比对”，而用计算机的
话讲就是把比较两个DNA相似性的操作看作是对两个由A、C、G
、T组成的字符串的比较。

n 度量DNA的相似性：
Ø 如果一个DNA螺旋是另一个DNA螺旋的子串，就说

这两个DNA（串）相似。

Ø 当两个DNA螺旋互不为对方子串的时候，怎么度量呢？

方法一：如果将其中一个转换成另一个所需改变的工作量小，

则可称其相似（参见 Edit distance 15-5）。

方法二：在S1和S2中找出第三个存在S3，使得S3中的基以同样的

先后顺序出现在S1和S2中，但不一定连续。

然后视S3的长度，确定S1和S2的相似度。S3越长，S1和S2的相
似度越大，反之越小。
Ø 如上面的两个DNA串中，最长的公共存在是

S3=GTCGTCGGAAGCCGGCCGAA。

S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA
S2=GTCGTTCGGAATGCCGTTGCTCTGTAAA

怎么找最长的公共存在——两个字符串的最长公共非连续子
串，称为最长公共子序列。
n
2）公共子序列
对给定的两个序列X和Y，若序列Z既是X的的子序列，也是Y

的子序列，则称Z是X和Y的公共子序列。
如，X=<A,B,C,B,D,A,B>,Y=<B,D,C,A,B,A>，则序列<B,C,A>是X和Y的
一个公共子序列。

3）最长公共子序列
两个序列的长度最大的公共子序列称为它们的最长公共子

序列。
如，<B,C,A>是上面X和Y的一个公共子序列，但不是X和Y的最长公共子
序列。最长公共子序列是<B,C,B,A>。

怎么求最长公共子序列？
2、最长公共子序列问题（Longest-Common-Subsequence,LCS）
——求（两个）序列的最长公共子序列

前缀：给定一个序列X=<x1,x2,...,xm>，对于i=0,1,...,m,
定义X的第i个前缀为Xi=<x1,x2,...,xi>，即前i个元素
构成的子序列。

如，X=<A,B,C,B,D,A,B>，则

X4=<A,B,C,B>。

X0=Φ。
1）LCS问题的最优子结构性
定理6.2 设有序列X=<x1,x2,...,xm>和Y=<y1,y2,...,yn>，并

设序列Z=<z1,z2,...,zk>为X和Y的任意一个LCS。

（1）若xm＝yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的一个LCS。

（2）若xm≠yn，则zk≠xm蕴含Z是Xm-1和Y的一个LCS。

（3）若xm≠yn，则zk≠yn蕴含Z是X和Yn-1的一个LCS。

子问题的定义：从“Xm和Yn的LCS”到“Xm-1和Yn-1的LCS”、
“Xm-1和Yn的LCS”、“Xm和Yn-1的LCS”
证明：
(1) 如果zk≠xm，则可以添加xm（也即yn）到Z中，从而可
以得到X和Y的一个长度为k+1的公共子序列。这与Z是X和Y的最
长公共子序列的假设相矛盾，故必有zk=xm=yn。

同时，如果Xm-1和Yn-1有一个长度大于k-1的公共子序列W（
W是Xm-1和Yn-1更长的一个公共子序列），则将xm （也即yn）添
加到W上就会产生一个X和Y的长度大于k的公共子序列，与Z是X
和Y的最长公共子序列的假设相矛盾，故Z k-1 必是X m-1 和Y n-1 的
LCS。
 (2) 若zk≠xm，设Xm-1和Y有一个长度大于k的公共子序列W（
Z不是Xm-1和Y的一个公共子序列），则W也应该是Xm和Y的一个公
共子序列。这与Z是X和Y的一个LCS的假设相矛盾。故Z是Xm-1和Y
的一个LCS。

(3) 同（2）。

（证毕）

上述定理说明，两个序列的一个LCS也包含了两个序列
的前缀的LCS，即LCS问题具有最优子结构性质。
2）递推关系式

记，c[i,j]为前缀序列Xi和Yj的一个LCS的长度。则有
0 如果 i  0或 j  0

c[i , j ]   c[i  1, j  1]  1 如果 i, j  0且 x i  y j
 max( c[i , j  1], c[i  1, j ]) 如果 i, j  0且 x  y
 i j

含义：
1）若i=0或j=0，即其中一个序列的长度为零，则二者的LCS的长度为0，LCS=Φ；
2）若xi=yj，则Xi和Yj的LCS是在Xi-1和Yj-1的LCS之后附加将xi （也即yj）得到的，所以
c[i,j]=c[i-1,j-1]+1；
3）若xi≠yj，则Xi和Yj的LCS的最后一个字符不会是xi或yj(不可能同时等于两者，或与两者都不同)，
此时该LCS应等于Xi-1和Yj的LCS与Xi和Yj-1的LCS之中的长者。所以
c[i,j]=max(c[i-1,j],c[i,j-1])；
3）LCS的求解

Xm和Yn的LCS是基于Xm-1和Yn-1的LCS、或Xm-1和Yn的LCS、
或Xm和Yn-1的LCS求解的。

下述过程LCS-LENGTH(X,Y)求序列X=<x1,x2,...,xm>和
Y=<y1,y2,...,yn>的LCS的长度，表c[1..m,1..n]中包含每一
阶段的LCS长度，c[m,n]等于X和Y的LCS的长度。

同时，还设置了一个表b[1..m,1..n]，记录当前c[i,j]
的计值情况，以此来构造该LCS。
LCS-LENGTH的时间复杂度为O(mn)
例，下图给出了在X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>上

运行LCS-LENGTH计算出的表。

j 0 1 2 3 4 5 6
说明：

i B D C A B A
1）第i行和第j列中的方块包含了c[i,j]的值
yj
0 xi 以及b[i,j]记录的箭头。
0 0 00 0 0 0
↑ ↑↑↖ ↖ 2）对于i,j＞0，项c[i,j]仅依赖于是否有
1 A 0 0 00 1 ←1 1
↖ ↑↖
2 B 0 ① ←1 ←1 1 2 ←2 xi=yj及项c[i-1,j]、c[i,j-1]、c[i-1,j-
↑ ↑↖ ↑ ↑
3 C 0 1 1 ② ←2 2 2 1]的值。
↖ ↑ ↑ ↑↖
4 B 0 1 1 2 2 ③ ←3 3）为了重构一个LCS，从右下角开始跟踪
↑↖ ↑ ↑ ↑ ↑
5 D 0 1 2 2 2 3 3
↑ ↑ ↑↖ ↑↖ b[i,j]箭头即可，即如图所示中的蓝色方
6 A 0 1 2 2 3 3 ④
↖ ↑ ↑ ↑↖ ↑ 块给出的轨迹。
7 B 0 1 2 2 3 4 4
4）图中，c[7,6]=4，
LCS(X,Y)=<B,C,B,A>（是不是唯一的？）
例，下图给出了在X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>上

运行LCS-LENGTH计算出的表。

j 0 1 2 3 4 5 6 0 如果 i  0或 j  0

i c[i , j ]   c[i  1, j  1]  1 如果 i, j  0且 x i  y j
yj B D C A B A  max( c[i , j  1], c[i  1, j ]) 如果 i, j  0且 x  y
 i j
0 xi 0 0 00 0 0 0
↑ ↑↑↖ ↖
1 A 0 0 00 1 ←1 1 c[0,j] = 0
↖ ↑↖
2 B 0 ① ←1 ←1 1 2 ←2
3 C
↑ ↑↖ ↑ ↑ c[i,0] = 0
0 1 1 ② ←2 2 2
↖ ↑ ↑ ↑↖
4 B 0 1 1 2 2 ③ ←3
↑↖ ↑ ↑ ↑ ↑
5 D 0 1 2 2 2 3 3
↑ ↑ ↑↖ ↑↖
6 A 0 1 2 2 3 3 ④
↖ ↑ ↑ ↑↖ ↑
7 B 0 1 2 2 3 4 4
例，下图给出了在X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>上

运行LCS-LENGTH计算出的表。

j 0 1 2 3 4 5 6 0 如果 i  0或 j  0

i c[i , j ]   c[i  1, j  1]  1 如果 i, j  0且 x i  y j
yj B D C A B A  max( c[i , j  1], c[i  1, j ]) 如果 i, j  0且 x  y
 i j
0 xi 0 0 00 0 0 0
1 A 0
↑
0
↑
0
↑↖
0
↖
1 ←1 1 c[0,j] = 0
↖ ↑↖
2 B 0 ① ←1 ←1 1 2 ←2
↑ ↑↖ ↑ ↑ c[i,0] = 0
3 C 0 1 1 ② ←2 2 2
↖ ↑ ↑ ↑↖
4 B 0 1 1 2 2 ③ ←3 i = 1, j = 1 x1≠y1
↑↖ ↑ ↑ ↑ ↑
5 D 0 1 2 2 2 3 3
↑ ↑ ↑↖ ↑↖ c[1,1] = max{c[1,0], c[0,1]}
6 A 0 1 2 2 3 3 ④ = max{0,0}
↖ ↑ ↑ ↑↖ ↑
7 B 0 1 2 2 3 4 4 = 0
b[1,1] = ‘↑’
例，下图给出了在X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>上

运行LCS-LENGTH计算出的表。

j 0 1 2 3 4 5 6 0 如果 i  0或 j  0

i c[i , j ]   c[i  1, j  1]  1 如果 i, j  0且 x i  y j
yj B D C A B A  max( c[i , j  1], c[i  1, j ]) 如果 i, j  0且 x  y
 i j
0 xi 0 0 00 0 0 0
1 A 0
↑
0
↑
0
↑↖
0
↖
1 ←1 1 c[0,j] = 0
↖ ↑↖
2 B 0 ① ←1 ←1 1 2 ←2
↑ ↑↖ ↑ ↑ c[i,0] = 0
3 C 0 1 1 ② ←2 2 2
↖ ↑ ↑ ↑↖
4 B 0 1 1 2 2 ③ ←3 i = 1, j = 2 x1≠y2
↑↖ ↑ ↑ ↑ ↑
5 D 0 1 2 2 2 3 3
↑ ↑ ↑↖ ↑↖ c[1,2] = max{c[1,1], c[0,2]}
6 A 0 1 2 2 3 3 ④ = max{0,0}
↖ ↑ ↑ ↑↖ ↑
7 B 0 1 2 2 3 4 4 = 0
b[1,2] = ‘↑’
例，下图给出了在X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>上

运行LCS-LENGTH计算出的表。

j 0 1 2 3 4 5 6 0 如果 i  0或 j  0

i c[i , j ]   c[i  1, j  1]  1 如果 i, j  0且 x i  y j
yj B D C A B A  max( c[i , j  1], c[i  1, j ]) 如果 i, j  0且 x  y
 i j
0 xi 0 0 00 0 0 0
1 A 0
↑
0
↑
0
↑↖
0
↖
1 ←1 1 c[0,j] = 0
↖ ↑↖
2 B 0 ① ←1 ←1 1 2 ←2
↑ ↑↖ ↑ ↑ c[i,0] = 0
3 C 0 1 1 ② ←2 2 2
↖ ↑ ↑ ↑↖
4 B 0 1 1 2 2 ③ ←3 i = 1, j = 3 x1≠y3
↑↖ ↑ ↑ ↑ ↑
5 D 0 1 2 2 2 3 3
↑ ↑ ↑↖ ↑↖ c[1,3] = max{c[1,2], c[0,3]}
6 A 0 1 2 2 3 3 ④ = max{0,0}
↖ ↑ ↑ ↑↖ ↑
7 B 0 1 2 2 3 4 4 = 0
b[1,3] = ‘↑’
例，下图给出了在X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>上

运行LCS-LENGTH计算出的表。

j 0 1 2 3 4 5 6 0 如果 i  0或 j  0

i c[i , j ]   c[i  1, j  1]  1 如果 i, j  0且 x i  y j
yj B D C A B A  max( c[i , j  1], c[i  1, j ]) 如果 i, j  0且 x  y
 i j
0 xi 0 0 00 0 0 0
1 A 0
↑
0
↑
0
↑↖
0
↖
1 ←1 1 c[0,j] = 0
↖ ↑↖
2 B 0 ① ←1 ←1 1 2 ←2
↑ ↑↖ ↑ ↑ c[i,0] = 0
3 C 0 1 1 ② ←2 2 2
↖ ↑ ↑ ↑↖
4 B 0 1 1 2 2 ③ ←3 i = 1, j = 4 x1 = y4
↑↖ ↑ ↑ ↑ ↑
5 D 0 1 2 2 2 3 3
↑ ↑ ↑↖ ↑↖ c[1,4] = c[0,3] + 1
6 A 0 1 2 2 3 3 ④ =0+1
↖ ↑ ↑ ↑↖ ↑
7 B 0 1 2 2 3 4 4 =1
b[1,4] = ‘↖’
例，下图给出了在X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>上

运行LCS-LENGTH计算出的表。

j 0 1 2 3 4 5 6 0 如果 i  0或 j  0

i c[i , j ]   c[i  1, j  1]  1 如果 i, j  0且 x i  y j
yj B D C A B A  max( c[i , j  1], c[i  1, j ]) 如果 i, j  0且 x  y
 i j
0 xi 0 0 00 0 0 0
1 A 0
↑
0
↑
0
↑↖
0
↖
1 ←1 1 c[0,j] = 0
↖ ↑↖
2 B 0 ① ←1 ←1 1 2 ←2
↑ ↑↖ ↑ ↑ c[i,0] = 0
3 C 0 1 1 ② ←2 2 2
↖ ↑ ↑ ↑↖
4 B 0 1 1 2 2 ③ ←3 i = 1, j = 5 x1≠y5
↑↖ ↑ ↑ ↑ ↑
5 D 0 1 2 2 2 3 3
↑ ↑ ↑↖ ↑↖ c[1,5] = max{c[1,4], c[0,5]}
6 A 0 1 2 2 3 3 ④ = max{1,0}
↖ ↑ ↑ ↑↖ ↑
7 B 0 1 2 2 3 4 4 = 0
b[1,5] = ‘←’
例，下图给出了在X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>上

运行LCS-LENGTH计算出的表。

j 0 1 2 3 4 5 6 0 如果 i  0或 j  0

i c[i , j ]   c[i  1, j  1]  1 如果 i, j  0且 x i  y j
yj B D C A B A  max( c[i , j  1], c[i  1, j ]) 如果 i, j  0且 x  y
 i j
0 xi 0 0 00 0 0 0
1 A 0
↑
0
↑
0
↑↖
0
↖
1 ←1 1 c[0,j] = 0
↖ ↑↖
2 B 0 ① ←1 ←1 1 2 ←2
↑ ↑↖ ↑ ↑ c[i,0] = 0
3 C 0 1 1 ② ←2 2 2
↖ ↑ ↑ ↑↖
4 B 0 1 1 2 2 ③ ←3 i = 1, j = 6 x1 = y6
↑↖ ↑ ↑ ↑ ↑
5 D 0 1 2 2 2 3 3
↑ ↑ ↑↖ ↑↖ c[1,6] = c[0,5] + 1
6 A 0 1 2 2 3 3 ④ = 0+1
↖ ↑ ↑ ↑↖ ↑
7 B 0 1 2 2 3 4 4 =1
b[1,6] = ‘↖’
例，下图给出了在X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>上

运行LCS-LENGTH计算出的表。

j 0 1 2 3 4 5 6 0 如果 i  0或 j  0

i c[i , j ]   c[i  1, j  1]  1 如果 i, j  0且 x i  y j
yj B D C A B A  max( c[i , j  1], c[i  1, j ]) 如果 i, j  0且 x  y
 i j
0 xi 0 0 00 0 0 0
1 A 0
↑
0
↑
0
↑↖
0
↖
1 ←1 1 c[0,j] = 0
↖ ↑↖
2 B 0 ① ←1 ←1 1 2 ←2
↑ ↑↖ ↑ ↑ c[i,0] = 0
3 C 0 1 1 ② ←2 2 2
↖ ↑ ↑ ↑↖
4 B 0 1 1 2 2 ③ ←3 i = 2, j = 1 x2 = y2
↑↖ ↑ ↑ ↑ ↑
5 D 0 1 2 2 2 3 3
↑ ↑ ↑↖ ↑↖ c[2,1] = c[1,0] + 1
6 A 0 1 2 2 3 3 ④ = 0 +1
↖ ↑ ↑ ↑↖ ↑
7 B 0 1 2 2 3 4 4 =1
b[2,1] = ‘↖’
例，下图给出了在X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>上

运行LCS-LENGTH计算出的表。

j 0 1 2 3 4 5 6 0 如果 i  0或 j  0

i c[i , j ]   c[i  1, j  1]  1 如果 i, j  0且 x i  y j
yj B D C A B A  max( c[i , j  1], c[i  1, j ]) 如果 i, j  0且 x  y
 i j
0 xi 0 0 00 0 0 0
1 A 0
↑
0
↑
0
↑↖
0
↖
1 ←1 1 c[0,j] = 0
↖ ↑↖
2 B 0 ① ←1 ←1 1 2 ←2
↑ ↑↖ ↑ ↑ c[i,0] = 0
3 C 0 1 1 ② ←2 2 2
↖ ↑ ↑ ↑↖
4 B 0 1 1 2 2 ③ ←3 i = 2, j = 5 x2 = y5
↑↖ ↑ ↑ ↑ ↑
5 D 0 1 2 2 2 3 3
↑ ↑ ↑↖ ↑↖ c[2,5] = c[1,4] + 1
6 A 0 1 2 2 3 3 ④ = 1+1
↖ ↑ ↑ ↑↖ ↑
7 B 0 1 2 2 3 4 4 =2
b[2,5] = ‘↖’
构造一个LCS
表b用来构造序列X=<x1,x2,...,xm>和Y=<y1,y2,...,yn>的一
个LCS：

反序，从b[m,n]处开始，沿箭头在表格中向上跟踪。每当
在表项b[i,j]中：

Ø 遇到一个“↖”时，意味着xi=yj是LCS的一个元素，下一步

继续在b[i-1,j-1]中寻找上一个元素；

Ø 遇到“←”时，下一步到b[i,j-1]中寻找上一个元素；

Ø 遇到“↑”时，下一步到b[i-1,j]中寻找上一个元素。
过程PRINT-LCS按照上述规则输出X和Y的LCS

由于每一次循环使i或j减1，最终m=0，n=0，算法结束，所
以PRINT-LCS的时间复杂度为O(m+n)
 PRINT-LCS(b,X,7,6）

PRINT-LCS(b,X,6,6） print A
j 0 1 2 3 4 5 6

i PRINT-LCS(b,X,5,5）
yj B D C A B A

0 xi 0 0 00 0 0 0 PRINT-LCS(b,X,4,5） print B
↑ ↑↑↖ ↖
1 A 0 0 00 1 ←1 1
↖ ↑↖ PRINT-LCS(b,X,3,4）
2 B 0 ① ←1 ←1 1 2 ←2
↑ ↑↖ ↑ ↑
3 C 0 1 1 ② ←2 2 2 PRINT-LCS(b,X,3,3） print C
↖ ↑ ↑ ↑↖
4 B 0 1 1 2 2 ③ ←3
↑↖ ↑ ↑ ↑ ↑ PRINT-LCS(b,X,2,2）
5 D 0 1 2 2 2 3 3
↑ ↑ ↑↖ ↑↖
6 A 0 1 2 2 3 3 ④ PRINT-LCS(b,X,2,1） print B
↖ ↑ ↑ ↑↖ ↑
7 B 0 1 2 2 3 4 4
PRINT-LCS(b,X,1,0） 结束
4）算法的改进

（1）可以去掉表b，直接基于c求LCS。
（2）算法中，每个c[i,j]的计算仅需c的两行的数据：
正在被计算的一行和前面的一行。
15.5 最优二叉搜索树

n 场景：语言翻译，从英语到法语，对给定的单词，在单词表

里找到该词。

n 方法：创建一棵二叉搜索树，以英语单词作为关键字构建树。

n 目标：尽快地找到英语单词，使“总”的搜索时间尽量少。

n 思路：频繁使用的单词，如the，应尽可能靠近根；而不经常

出现的单词可以离根远一些。
Ø 思考：如果反之会怎样？

2023-10-21 78
最优二叉搜索树的定义
假设所有元素互异

（1）二叉搜索树（二分检索树）
二叉搜索树Ｔ是一棵二元树，它或者为空，或者其每个结
点含有一个可以比较大小的数据元素，且有：

·Ｔ的左子树的所有元素比根结点中的元素小；

·Ｔ的右子树的所有元素比根结点中的元素大；

·Ｔ的左子树和右子树也是二叉搜索树。

2023-10-21 79
（2）最优二叉搜索树
给定一个n个关键字的已排序的序列K=<k1,k2,…,kn>（不失
一般性，设 k1<k2<…<kn），对每个关键字ki，都有一个概率pi表
示其被搜索的频率。根据ki和pi构建一个二叉搜索树T，每个ki对
应树中的一个结点。

对搜索对象x，在T中可能找到、也可能找不到：

Ø 若x等于某个ki，则一定可以在T中找到结点ki，称为成功
搜索。

u 成功搜索的情况一共有n种，分别是x恰好等于某个ki。

2023-10-21 80
n 若x<k1 、或 x>kn 、或 ki<x<ki+1 (1≤i<n), 则在T中搜索x将
失败，称为失败搜索。

Ø 为此引入外部结点d0,d1,…,dn，用来表示不在K中的值,称
为伪关键字。

Ø 伪关键字在T中对应外部结点，共有n+1个。
——扩展二叉树：内结点表示关键字ki，外结点(叶子结点)表示di。

Ø 这里每个di代表一个区间。
u d0表示所有小于k1的值， dn表示所有大于kn的值，对于i=1,…,n-
1，di表示所有在ki和ki+1之间的值。

Ø 每个di也有一个概率qi，表示搜索对象x恰好落入区间di的
频率。
例：设有n=5个关键字的集合，每个ki的概率pi和相di的概率qi如表所示：

这里有：

基于该集合，两棵可能的二叉搜索树如下所示。

每个ki对应一个内结点，共有n个，
每个di对应一个外部结点，有
用圆形结点表示，代表成功检索的
n+1个，用矩形框表示，代表
位置。
失败检索的情况。
二叉搜索树的期望搜索代价

Ø 一次搜索的代价等于从根结点开始访问结点的数量(包括外部结点)。

u 从根结点开始访问结点的数量等于结点在T中的深度+1；

u 记depthT(i)为结点i在T中的深度。

Ø 二叉搜索树T的期望代价为
例：n=5，

Ø (a)的期望搜索代价为2.80。
Ø (b)的期望搜索代价为2.75。

显然，树b的期望代价小于树a。事实上，树b是当前问题
实例的一棵最优二叉搜索树
n=5，

(a)的期望搜索代价为2.80
最优二叉搜索树的定义：

对于给定的关键字及其概率集合，期望搜索代价
最小的二叉搜索树称为其最优二叉搜索树。

n 对给定的关键字和概率集合，怎么构造最优二叉搜索树？

n 关键问题：确定谁是树根
Ø 树根不一定是概率最高的关键字；
Ø 树也不一定是最矮的树；
Ø 但该树的期望搜索代价必须是最小的。
用动态规划策略构造最优二叉搜索树
（1）证明最优二叉搜索树的最优子结构
如果T是一棵相对于关键字k1,…,kn和伪关键字d0, …,dn的
最优二叉搜索树，则T中一棵包含关键字ki,…,kj的子树T’必然
是相对于关键字ki,…,kj（和伪关键字di-1, …,dj）的最优二叉
搜索子树。

证明：用剪切-粘贴法证明
对关键字ki,…,kj和伪关键字di-1,…,dj，如果存在子树T”，其
期望搜索代价比T’低，那么将T’从T中删除，将T”粘贴到相应位置
上，则可以得到一棵比T期望搜索代价更低的二叉搜索树，与T是最优
的假设矛盾。
（2）构造最优二叉搜索树

利用最优二叉搜索树的最优子结构性来构造最优
二叉搜索树。

分析：
对给定的关键字k i ,…,k j ，若其最优二叉搜索（子）树的
根结点是kr（i≤r≤j），则kr的左子树中包含关键字ki,…,kr-1
及伪关键字di-1 , …,dr-1，右子树中将含关键字ki+1,…,kj及伪
关键字dr,…,dj。

谁可能是这个根呢？
计算过程：求解包含关键字ki,…,kj的最优二叉搜索树，其中
i≥1，j≤n 且 j≥i-1。

定义e[i,j]：为包含关键字ki,…,kj的最优二叉搜索树的期望搜索代价
Ø e[1,n]为问题的最终解的期望搜索代价。

（1）当i≤j时，从ki,…,kj中选择出根结点kr。
Ø 其左子树包含关键字ki,…,kr-1且是最优二叉搜索子树；

Ø 其右子树包含关键字kr+1,…, kj且同样为最优二叉搜索子树。
kr

由ki,…,kr-1构成的 由kr+1,…,kj构成的
最优二叉搜索树 最优二叉搜索树
2023-10-21 89
当一棵树成为另一个结点的子树时，有以下变化：
kr
深度+1

由ki,…,kr-1构成的最 由kr+1,…,kj构成的
优二叉搜索树 最优二叉搜索树

Ø 子树的每个结点的深度增加1。

Ø 根据搜索代价期望值计算公式，子树对根为kr的树的期望搜索
代价的贡献是其期望搜索代价+其所含所有结点的概率之和。

u 对于包含关键字ki,…,kj的子树，所有结点的概率之和为

（包含外部结点）： 90
 若kr为包含关键字ki,…,kj的最优二叉搜索树的根，则其期望
搜索代价e[i,j]与左、右子树的期望搜索代价e[i,r-1]和e[r+1,j]的递
推关系为：

其中，w(i,r-1)和w(r+1,j)是左右子树所有结点的概率之和。且有：

故有：

因此，求kr的递归公式为：

2023-10-21 91
（2）边界条件
公式

存在e[i, i-1]和e[j+1, j]的边界情况。

Ø 此时，子树不包含实际的关键字，而只包含伪关键字di-1，其期望
搜索代价仅为：

（3）构造最优二叉搜索树
定义root[i,j]，保存计算e[i, j]时，使e[i, j]取得最小值的r，kr即
为关键字ki,…,kj的最优二叉搜索（子）树的树根。

在求出e[1,n]后，利用root即可构造出最终的最优二叉搜索树。

92
计算最优二叉搜索树的期望值
定义三个表（数组）：

n e[1..n+1,0..n]：用于记录所有e[i,j]的值。
Ø 注：e[n+1,n]对应伪关键字dn的子树；
e[1,0]对应伪关键字d0的子树。

n root[1..n,1..n]：用于记录所有最优二叉搜索子树的根结点
Ø 包括整棵最优二叉搜索树的根。

n w[1..n+1,0..n]：用于保存子树的结点概率之和，且有

2023-10-21
这样，每个w[i,j]的计算时间仅为Θ(1)。
93
 过程OPTIMAL-BST利用概率列表p和q，对n个关键字计算最优
二叉搜索树的表e和root。

自
底
向
上
的
时间复杂
迭 度Θ(n3)
代
计
算

94
n 例： n=5，

qi

2023-10-21 95
n 例： n=5，

qi
e[1,0] = q0 = 0.05
e[2,1] = q1 = 0.10
w[1,0] = q0 = 0.05
w[1,1] = w[1,0] + p1+q1 = 0.3
e[1,1] = min{e[1,0]+e[2,1]+w[1,1]}
= 0.45
r[1,1] = 1
2023-10-21 96
n 例： n=5，

qi
e[1,0] = q0 = 0.05
e[1,1] = 0.45
e[2,2] = 0.4
e[3,2] = q2 = 0.05
w[1,1] = 0.3
w[1,2] = w[1,1] + p2+q2 = 0.45
e[1,2] = min{e[1,0]+e[2,2]+w[1,2],
e[1,1]+e[3,2]+w[1,2]}
= 0.9
2023-10-21 r[1,2] = 1 97
 n=5，

qi

课堂练习：计算
（1）w[2,3]
e[2,3]
r[2,3]
（2）w[1,5]
e[1,5]
2023-10-21
r[1,5] 98
动态规划作业：
n 计算题：
Ø 15.2-1
Ø 15.4-1
Ø 15.5-2

n 算法设计题：
Ø 15.1-3
Ø 15-9
Ø 15-11

n 证明题：
Ø 15.2-5
Ø 15.3-6：提示 基于以下数据讨论第二问，