算法设计与分析 1
第四章
动态规划
算法设计与分析 2
矩阵连乘问题
? 给定 n个矩阵,A1,A2,…,A n，其中 Ai与 Ai+1是
可乘的。确定一种连乘的顺序，使得矩阵连
乘的计算量为最小。
? 设 A和 B分别是 p× q和 q× r的两个矩阵，则乘
积 C=AB为 p× r的矩阵，计算量为 pqr次数乘。
? 但是对于多于 2个以上的矩阵连乘，连乘的顺
序却非常重要，因为不同的顺序的总计算量
将会有很大的差别。
算法设计与分析 3
不同计算顺序的差别
? 设矩阵 A1,A2和 A3分别为 10× 100,100× 5和
5× 50的矩阵，现要计算 A1A2A3 。
? 若按 ((A1A2)A3)来计算，则需要的数乘次数为
10× 100× 5 + 10× 5× 50 = 7500
? 若按 (A1(A2 A3))来计算，则需要的数乘次数为
100 × 5 × 50+ 10× 100× 50 = 75000
? 后一种计算顺序的计算量竟是前者的 10倍！
? 所以，求多个矩阵的连乘积时，计算的结合
顺序是十分重要的。
算法设计与分析 4
不同计算顺序的数量
? 设 n个矩阵的连乘积有 P(n)个不同的计算顺序。
? 先在第 k个和第 k+1个矩阵之间将原矩阵序列
分成两个矩阵子序列,k=1,…, n；再分别
对两个子序列完全加括号，最后对结果加括
号，便得到原序列的一种完全加括号方式。
由此可得出关于 P(n)的递归式：
P(n) = 1 n = 1n–1∑P(k) P(n–k) n＞ 1
k=1
? 解此递归方程可得 P(n) = C(n–1)，其中
C(n) = 1n+1 2nn = Ω(4n/n3/2)
? 所以 P(n)随 n的增长呈指数增长。因而穷举搜
索法不是有效的算法。
算法设计与分析 5
分解最优解的结构
? 将矩阵连乘积 AiAi+1…A j记为 A[i,j]。
? 若 A[1,n] 的一个最优解是在矩阵 Ak和 Ak+1处
断开的，即 A[1,n] = (A[1,k] A[k+1,n])，则
A[1,k]和 A[k+1,n]也分别是最优解。
? 事实上，若 A[1,k]的一个计算次序所需计算量
更少的话，则用此计算次序替换原来的次序，
则得到 A[1,n]一个更少的计算量，这是一个矛
盾。同理 A[k+1,n]也是最优解。
? 最优子结构性质：最优解的子结构也最优的。
算法设计与分析 6
建立递归关系
? 令 m[i][j],1≤i,j≤n，为计算 A[i,j] 的最少数乘
次数，则原问题为 m[1][n]。
? 当 i = j时,A[i,j]为单一矩阵,m[i][j] = 0；
? 当 i＜ j时，利用最优子结构性质有：
m[i][j] = min{m[i][k] + m[k+1][j] + pi–1pkpj}i≤k＜ j
其中矩阵 Ai, 1≤i≤n，的维数为 pi–1× pi。
? 根据此递归式就可以直接用递归程序来实现。
算法设计与分析 7
直接递归的时间复杂性
? 根据前面的递归式不难得出的时间复杂性为
n–11 + ∑(T(k) + T(n–k) + 1)
k=1
T(n) ≥
n–1= 1 + (n –1) +∑(T(k) + T(n–k))
k=1
n–1 n–1= n +∑T(k) + ∑T(n–k)
k=1 k=1
? 可用数学归纳法证明 T(n)≥2n–1 = Ω(2n)。
? 直接递归算法的时间复杂性随 n的指数增长。
n–1 = n + 2∑T(k)
k=1
算法设计与分析 8
直接递归中有大量重复计算
? 直接递归中有大量重复计算，如 A[1,4]计算中：
1,4
1,1 2,4
1,2 3,4
1,3 4,4
2,2 3,4 2,3 4,4
1:1 2,2 3,3 4,4
1,1 2,3 1,2 3,3
3,3 4,4 2,2 3,3 2,2 3,3 1,1 2,2
图中红框标出的
都是重复计算。
算法设计与分析 9
消除重复的计算
? 要消除重复计算，可在在计算过程中保存已解
决的子问题的答案。这样，每个子问题只计算
一次，而在后面需要时只要简单查一下，从而
避免重复计算。
? 计算方式可依据递归式自底向上地进行。
? 注意到在此问题中,不同的有序对 (i,j)就对应
不同的子问题，因此 不同的子问题个数个数最
多只有 Cn2+ n = ?(n2)个。
? 这样便可以得到多项式时间的算法。
算法设计与分析 10
自底向上的计算
? 例如对于 A1A2A3A4,依据递归式以自底向上的
方式计算出各个子问题，其过程如下：
m[1][1] m[2][2] m[3][3] m[4][4]
m[1][2] m[2][3] m[3][4]
m[1][3] m[2][4]
m[2][4] 其中
m[i][i] = 0
m[i][i+1] = pi–1pipi+1
m[i][j] = mini≤k＜ j
{m[i][k]+m[k+1][j]+pi–1pkpj}
例如,m[1][3] =
min m[1][1]+m[2][3]+p0p1p3m[1][2]+m[3][3]+p
0p2p3
算法设计与分析 11
消除重复的矩阵连乘算法
? Void MatrixChain(int p,int n,int **m,int **s)
? { for (int i = 1; i <= n; i++) m[i][i] = 0;
? //将对角线元素赋值为零，即单个矩阵计算量为 0
? for (int r = 2; r <= n; r++)
? for (int i = 1; i <= n – r +1; i++) {
? int j = i + r – 1;
? (5) m[i][j] = m[i+1][j] + p[i–1]*p[i]*p[j];
? //计算 A[i,j] = A[i,i] A[i+1,j]
? s[i][j] = i; //记下断点 i
? (7) for (int k = i + 1; k < j; k++) {
? int t = m[i][k] + m[k+1][j] + p[i–1]*p[k]*p[j];
? //对 i<k<j,逐个计算 A[i,j] = A[i,k] A[k+1,j]
? if (t < m[i][j]) {m[i][j] = t; s[i][j] = k;}
? //记下较小的 m[i][j]及相应的断点 k
? }}}
第 (5)步与第 (7)步
能否合在一起?
能。此处分开是为
了给 m[i][j]赋初值。
算法设计与分析 12
MatrixChain的运行举例
设要计算矩阵连乘积 A1A2A3A4A5A6，其维数分别
为 35× 35,35× 15,15× 5,5× 10,10× 20,20× 25,
即 p0=35,p1=35,p2=15,p3=5,p4=10,p5=20,p6=25。
MatrixChain用矩阵 m[i][j],s[i][j]存放子问题 A[i,j]
的最小计算量以及相应的断点。
1
2
3
4
5
6
1 2 3 4 5 6
m[i][j]
1
2
3
4
5
6
1 2 3 4 5 6
s[i][j]
trix hain将如下面红色箭头所示的过程逐个计算
子问题 A[i,j]：
执行 for (int i = 1; i <= n; i++) m[i][i] = 0后将对角线元素全
部置零，即子问题 A[i][i] = 0。
0
0
0
0
0
0
当 r=2，执行 第 (5)句 完成了相邻矩阵 [i][i+1]=p[i–1]*p[i]*p[j]
的计算，并在 s[i][j]中添入了相应的断点。其中的 第 (7)句 因
为 j = i+1(k=i+1)而被跳过去了，实际并没有执行。
15750
2625
750
1000
5000
1
2
3
4
5
当 r=3,i=1时，执行 第 (5)句 计算 A[1:1][2:3],m[1][3] =
m[2][3] + p[0]*p[1]*p[3] = 2625 +30*35*5 = 7875
7875 1
执行 第 (7)句 计算 A[1:2][3:3],t = m[1][2] + m[3][3] +
p[0]*p[2]*p[3] = 15750+0+35*15*5 = 18375＞ 7875，所以
m[1][3]不变，断点仍为 1。
当, =2时，执行 第 句 计算 2:2] 3:4],[2][4] =
3] 4] 1] 2] 4] = 750 +35*15*10 = 6000
6000 2
执行 第 (7)句 计算 A[2:3][4:4],t = m[2][3]+m[4][4]+
p[1]*p[3]*p[4] = 2625+0+35*5*10 = 4375＜ 6000，所以
m[2][4]改为 4375，断点改为 3。
4375 3
当 r=3,i=3时，执行 第 (5)句 计算 [3:3][4:5],3] 5]
[4][5] + p[2]*p[3]*p[5] = 1000 +15*5*20 = 2500
2500 3
执行 第 (7)句 计算 [3:4][5:5],t = m[3][4] [5][5]+
p[2]*p[4]*p[5] = 750+0+15*10*20 = 3750＞ 2500，所以
[3][5]仍为 2500，断点仍为 3。
当 r=3,i=4时，执行 第 (5)句 计算 A[4:4][5:6],m[4][6] =
m[5][6] + p[3]*p[4]*p[6] = 5000 +5*10*25 = 6250
6250 4
执行 第 ( 句 计算 [4:5][6:6],[4][5] [6][6]
3] 5] 6] = 1000+0+5*20*25 = 3500＜ 6250，所以
[4][6]改为 3500，断点改为 5。
3500 5
类似的，当 r=4,5,6时，可以计算出相应的 [i][j]及其相
应的断点 s[i][j]，如下图中所示：
9375 3
7125 3
5375 3
11875 3
10500 3
15125 3
由 m[1][6]=15125可知这 6个矩阵连乘积的最小运算次数为
15125。由 s[1][6] = 3可知 A[1,6]的最优计算次序为 A[1,3]
A[4,6]；由 s[1][3]=1可知 A[1,3]的最优计算次序为 A[1,1]
A[2,3]；由 s[4][6]=5可知 A[4,6]的最优计算次序为 A[4,5]
A 6,6]；因此最优计算次序为,(A1(A2A3))((A4A5)A6)。
算法设计与分析 13
MatrixChain的时间复杂性
? 算法 MatrixChain的主要计算取决于程序
中对 r,i和 k的三重循环。循环体内的计
算量为 O(1),1≤ r,i,k≤n，三重循环的
总次数为 O(n3)。因此该算法时间复杂性
的上界为 O(n3)，比直接递归算法要有效
得多。算法使用空间显然为 O(n2)。
? 这种算法称为动态规划。
算法设计与分析 14
动态规划的基本思想
? 将原问题分解为若干个子问题，先求子问题的
解，然后从这些子问题的解得到原问题的解。
? 这些子问题的解往往不是相互独立的。在求解
的过程中，许多子问题的解被反复地使用。为
了避免重复计算，动态规划算法采用了填表来
保存子问题解的方法。
? 在算法中用表格来保存已经求解的子问题的解，
无论它是否会被用到。当以后遇到该子问题时
即可查表取出其解，避免了重复计算。
算法设计与分析 15
动态规划的基本要素
? 最优子结构：问题的最优解是由其子问题的最
优解所构成的。
? 重叠子问题：子问题之间并非相互独立的，而
是彼此有重叠的。
最优子结构性质使我们能够以自底向上的方式
递归地从子结构的最优解构造出问题的最优解。
因为子问题重叠，所以存在着重复计算。这样
就可以用填表保存子问题解的方法来提高效率。
算法设计与分析 16
动态规划的基本方法
? 动态规划通常可以按以下几个步骤进行：
? (1)找出最优解的性质，并刻画其结构特征；
? (2)递归地定义最优值；
? (3)以自底向上的方式计算出各子结构的最优值
并添入表格中保存；
? (4)根据计算最优值时得到的信息，构造最优解。
? 步骤 1~3是动态规划算法的基本步骤。若需要
最优解，则必须执行第 4步,为此还需要在第 3
步中记录构造最优解所必需的信息 。
算法设计与分析 17
动态规划的备忘录方法
? 动态规划中采用自底向上的方式。但是在递归
定义中往往是自上而下的描述。备忘录方法就
采用与递归定义一致的自上而下的方式。
? 备忘录方法同样用表格来保存已解子问题的信
息。每个子问题初始化时都标记为尚未求解。
在递归求解过程中，对每个待解子问题，先查
看它是否已求解。若未求解，则计算其解并填
表保存。若已求解，则查表取出相应的结果。
? 备忘录方法同样避免了子问题的重复计算，因
而和动态规划算法具有同样效率。
算法设计与分析 18
凸多边形最优三角剖分
? 凸多边形的三角剖分是将一个凸多边形分割成
互不相交的三角形的弦的集合 T。
? 下面是一个凸 7边形的 2个不同的三角剖分：
v0v
1
v2
v3 v4
v5
v6
v0v
1
v2
v3 v4
v5
v6
在凸多边形的一个三角剖分 T中，各弦互不相
交，且 T已达到最大，即任何一条不在 T中的弦
必与 T中某弦相交。
? 在有 n个顶点的凸多边形的中三角剖分中，恰
有 n–3条弦和 n–2个三角形。
? 凸多边形的最优三角剖分问题：给定凸多边形
P={v0,v1,…,v n–1},以及定义在由凸多边形的
边和弦组成的三角形上的权函数 w。要求确定
该凸多边形的一个三角剖分，使得该剖分中诸
三角形上权之和为最小。
? 可定义三角形上各种各样的权函数 w。
? 例如 w(vivjvk) = |vivj| + |vjvk| + |vkvi|，其中 |vivj|是
点 vi到 vj的欧氏距离。相应于此权函数的最优三
角剖分即为最小弦长三角剖分。
算法设计与分析 19
三角剖分与矩阵连乘积同构
? 三角剖分问题和矩阵连乘积问题都对应于一个
完全二叉树，也称为表达式的语法树。
0
1 2
3A1 A4 4
A2 A3 A5 A6
((A1(A2A3))(A4(A5A6))
所对应的二叉树
v1
v0
v2
v3 v4
v5
v60
1
2
A1
3A2
A3
A4
4
A5
A6
凸多边形 v0v1v2v3v4v5v6
一个三角剖分所对应
的二叉树
? n个矩阵连乘积计算顺序同构于 n个叶子的完全
二叉树，凸 (n+1)边形三角剖分同构于 n个叶子
的完全二叉树，所以 n个矩阵连乘积的计算顺
序问题同构于凸 (n+1)边形的三角剖分问题。
? 事实上，矩阵连乘积最优计算顺序问题相当于
是凸多边形最优三角剖分问题中一种特殊定义
的权函数的情形。
算法设计与分析 20
最优子结构性质
? 能应用动态规划求解的问题应具有最优子结构
性质。凸多边形最优三角剖分问题具有最优子
结构性质。
? 事实上，若 凸 (n+1)边形 P={v0,v1,…,v n}的一个
最优三角剖分 T包含了三角形 v0vkvn,1≤k＜ n，
则 T的权为三角形 v0vkvn，多边形 {v0,v1,…,v k}
和多边形 {vk,vk+1,…,v n}的权之和。显然这两
个子多边形的三角剖分也是最优的。
? 因为，其中若有一个子多边形的三角剖分不是
最优的将导致 T不是最优三角剖分的矛盾。
算法设计与分析 21
最优三角剖分的递归结构
? 定义 t[i][j],1≤i<j≤n,为子多边形 {vi–1,vi,…,v j}的
最优三角剖分所对应的权函数值，并为方便起
见，设退化的多边形 {vi–1,vi}的权值为 0。
? 于是凸 (n+1)边形的最优三角剖分为 t[1][n]
? 易知,t[i][j]可递归定义为
? 当 i = j时，为退化多边形 {vi–1,vi},t[i][j] = 0；
? 当 i＜ j时，利用最优子结构性质有：
t[i][j] = min{t[i][k] + t[k+1][j] + w(vi–1vkvj)}i≤k＜ j
与矩阵连乘积问题相对比：
m[i][j] = min{m[i][k] + m[k+1][j] + pi–1pkpj}i≤k＜ j
? 显然，矩阵连乘积的最优计算顺序与 凸多边形
最优三角剖分具有完全相同的递归结构。
算法设计与分析 22
最优三角剖分的算法
? 由于凸多边形最优三角剖分与矩阵连乘
积的最优计算顺序具有完全相同的递归
结构，其区别仅在于权函数的不同，所
以只需要修改求矩阵连乘积的最优计算
顺序的算法中的权函数计算便可得到凸
多边形最优三角剖分的算法。
? 显然该算法的时间复杂性也是 O(n3)。
? Void MinWeightTriangulation(int n,Type **t,int **s)
? { for (int i = 1; i <= n; i++) t[i][i] = 0;
? for (int r = 2; r <= n; r++)
? for (int i = 1; i <= n – r +1; i++) {
? int j = i + r – 1;
? t[i][j] = t[i+1][j] + w(i–1,i,j);
? s[i][j] = i;
? for (int k = i + 1; k < j; k++) {
? int u = t[i][k] + t[k+1][j] + w(i–1,k,j);
? if (u < t[i][j]) {t[i][j] = u; s[i][j] = k;}
? }}} //程序中红色的部分为改动的地方
算法设计与分析 23
多边形游戏
? 有一个 n边形，每个顶点被赋予一整数值，每
条边上被赋予一个运算符,+”或,*”。
? 游戏的第 1步，将一条边删去；
? 随后的 n–1步按以下方式操作：
? (1)选择一条边 E及其所连接的两个顶点 v1和 v2；
? (2) 用一个新顶点取代边 E以及顶点 v1和 v2，赋
予新顶点的值为顶点 v1和 v2的值通过 边 E上的
运算所得到的值。
? 最后所有的边被删去，所剩顶点的值即为得分。
算法设计与分析 24
多边形游戏的表达
? 设所有的边依次从 1到 n编号，按顺时针序列为
op[1],v[1],op[2],v[2],…,op[n],v[n]
其中 op[i]为边 i上的运算符,v[i]顶点 i上的值。
? 将多边形中始于顶点 i (1≤i≤n)，长度为 j 的顺时
针链 v[i],op[i+1],…,v[i+j –1]表示为 p(i,j)。
? 若链 p(i,j)最后一次合并在 op[i+s](1≤s≤j–1)处发
生，则被分割为两个子链 p(i,s)和 p(i+s,j–s)
算法设计与分析 25
多边形游戏的最优子结构性质
? 若链 p(i,j)取最优值的最后一次合并是在 op[i+s]
处发生的，则子链 p(i,s)和 p(i+s,j–s)也是最优。
? 因为若子链 p(i,s)和 p(i+s,j–s)不是最优的，则
可推出链 p(i,j)也不是最优的矛盾。所以多边形
游戏具有最优子结构性质。
? 但是这里的最优子结构要稍微地复杂一点。若 p(i,j)的最后合并的边 op[i+s] =“+”，子链 p(i,
s)和 p(i+s,s)应该取最大值，
? 若 p(i,j)的最后合并的边 op[i+s] =“*”，子链 p(i,s)
和 p(i+s,j–s)是否仍然取最大值呢？ 不见得！
算法设计与分析 26
多边形游戏的最优子结构分析
? 设 m1是对子链 p(i,s)的任意合并方式得到的值，
a和 b是其最小值和最大值,m2是对子链 p(i+s,
j–s)的任意合并方式得到的值,c和 d分别是最
小值和最大值，即 a≤m1≤b,c≤m2≤d。
? 若 op[i+s] =“+”，则 a+c≤m≤b+d。可见 p(i,s)的最
小、最大值分别对应于子链的最小、最大值。
? 若 op[i+s] =“*”，由于 v[i]可取负整数，所以
min{ac,ad,bc,bd}≤m≤max{ac,ad,bc,bd}。
? 即主链最小、最大值亦来自子链最小、最大值。
算法设计与分析 27
多边形游戏的递归求解
? 由前面的分析可知，为了求链合并的最大值，
必须同时求子链合并的最大值和最小值。因此
整个计算过程中应同时计算最大值和最小值。
设链 p(i,j)合并的最大、最小值分别是 m[i,j,0]
和 m[i,j,1]，最优合并处是在 op[i+s],且长度
小于 j的子链的最大、最小值均已算出，且记：
? a = m[i,i+s,0],b = m[i,i+s,1],c = m[i+s,j–s,0]，
d = m[i+s,j–s,1]，则
? ⑴当 op[i+s] =,+”时，
m[i,j,0] = a + c,m[i,j,1] = b + d
? ⑵ 当 op[i+s] =,*”时，
m[i,j,0] = min{ac,ad,bc,bd}
m[i,j,1] = max{ac,ad,bc,bd}
算法设计与分析 28
多边形游戏的递归求解
? 令 p(i,j)在 op[i+s]断开的最大值和最小值分别为
maxf(i,j,s)和 minf(i,j,s),综合上面的讨论则
minf(i,j,s) = a + c op[i+s] =,+”min{ac,ad,bc,bd} op[i+s] =,*”
maxf(i,j,s) = b + d op[i+s] =,+”max{ac,ad,bc,bd} op[i+s] =,*”
? 由于 p(i,j)的最优断开位置 s有 1≤s≤j–1的 j–1中情
况，于是便可得到求解多边形游戏的递归式：
算法设计与分析 29
求解多边形游戏的递归式
? 由于多边形是封闭的，当 i+s＞ n时，顶点 i+s实
际编号应为 (i+s)mod n。
? 多边形游戏的最大得分即为 m[i,n,1]。
m[i,j,0] = min{minf (i,j,s) },1≤i,j≤n
1≤s≤j
m[i,j,1] = max{maxf (i,j,s) },1≤i,j≤n
1≤s≤j
初始边界值为：
m[i,1,0] = m[i,1,1] = v[i],1≤i≤n,j = 1
算法设计与分析 30
多边形游戏的动态规划算法
? 依据上述讨论以及所得的递归式，不难写出多
边形游戏动态规划算法。请同学们自己编写。
? 算法的主程序为 Poly_Max，它包含了一个子程
序 MIN_MAX。子程序 MIN_MAX负责对确定 s
的 minf (i,j,s)和 maxf (i,j,s)的计算。而对任意
链的最大值 m[i,j,1]和最小值 m[i,j,0]的计算则
是在主程序 Poly_Max中进行的。
? 算法的时间复杂性显然仍为 O(n3)。
算法设计与分析 31
DNA序列的相似性
? 将序列 A,B表示 为对偶 (a,b)的序列。其中若：
? 1,a?A和 b?B称为替换,a = b称为匹配，否则
称为不匹配，其得分为 σ (a,b)；
? 2,a?A,b是空位为删除空白；
? 3,a是空位,b?B为插入空白；
? 对于长度为 k的空位，其得分为 –(q + k ? r)。
? 这里，参数 σ (a,b),q和 r由用户确定。
? 两个序列 A,B的相似性为所有这样的对偶序
列中最高的得分。
算法设计与分析 32
DNA序列的相似性
? 若给定两个 DNA序列：
AGCTACGTACACTACC
AGCTATCGTACTAGC
? 下面是其一个相似性序列：
AGCTA–CGTACACTACC
AGCTATCGTAC– –TAGC
? 其中有 13个匹配,1个不匹配、一个长度为 1的
插入空白和一个长度为 2的删除空白。
若,a = b时 σ (a,b) = 10； a ? b时 σ (a,b) = –20；
q = 40； r = 2。该相似性序列的得分为
10 * 13 – 20 – (40 + 2) – (40 + 2 * 2) = 24
算法设计与分析 33
递归求序列相似性
? 设 A = a1a2…a m,B = b1b2…b n。令 S(m,n)为 A和
B的相似性，即各种对偶序列最大的得分。
? 为了采用递归方法来求解此问题，我们从序列
尾部来考虑，那么有三种方案：
? ①尾部用替换，即最后一个对偶为 (am,bn)；
? ②尾部用删除空白，即最后一个对偶为 (am,–)；
? ③尾部用插入空白，即最后一个对偶为 (–,bn)。
? 令 S(m,n),D(m,n)和 I(m,n)分别为三种方案的
得分，则 其相似性应为三种方案的最大得分。
算法设计与分析 34
递归求序列相似性
S(m,n) = S(m – 1,n – 1) + σ(am,bn)。
?若用方案①，即尾部用替换，则
D(m,n) = S(m – 1,n) – q – r
或者,D(m,n) = D(m – 1,n) – r
?若用方案②，即尾部用删除空白，则
I(m,n) = S(m,n – 1) – q – r
或者,I(m,n) = I(m,n – 1) – r
?若用方案③，即尾部用插入空白，则
算法设计与分析 35
递归求序列相似性
? 现在考虑非递归分支：
S(0,0) = 0,S(m,0) = D(m,0),S(0,n) = I(0,n)。
?对方案①，有
D(m,0) = D(m – 1,0) – r,D(0,n) = S(0,n) – q。
?对方案②，有
I(m,0) = S(m,0) – q,I(0,n) = S(0,n – 1) – q。
?对方案③，有
算法设计与分析 36
递归求序列相似性
? S(m,n) =
0 m = 0,n = 0
D(m,0) for n ? 0
I(0,n) for m ? 0
max{S(m–1,n–1)+σ(am,bn),D(m,n),I(m,n)}
? D(m,n) =
S(0,n) – q for n ? 0
D(m – 1,0) – r for m ? 0
max{S(m–1,n) – q - r,D(m – 1,n) – r}
? I(m,n) =
S(m,0) – q for m ? 0
I(0,n – 1) – r for n ? 0
max{S(m,n–1) – q - r,I(m – 1,n) – r}
算法设计与分析 37
动态规划求序列相似性
? 如果用递归算法求序列的相似性，其时间复杂
性显然是指数级的。
? 考虑采用动态规划法。为此，需要
? ⑴用矩阵 S[0:m,0:n],D[0:m,0:n]和 I[0:m,0,n]
来分别记载对应于子序列 Ai和 Bj的得分 S(i,j)、
D(i,j)和 I(i,j),0 ? i ? m,0 ? j ? n。
? ⑵从 (0,0)开始逐个计算 S(i,j),D(i,j)和 I(i,j)并
将结果记入 S[i,j],D[i,j]和 I[i,j]。
? ⑶必要时，是用辅助矩阵记载每步的方案。
算法设计与分析 38
动态规划法的递归式
? S(i,j) =
0 m = 0,n = 0
D(i,0) for j ? 0
I(0,j) for i ? 0
max{S(i–1,j–1)+σ(ai,bj),D(i,j),I(i,j)}
? D(i,j) =
S(0,j) – q for j ? 0
D(i – 1,0) – r for i ? 0
max{S(i–1,j) – q - r,D(i – 1,j) – r}
? I(i,j) =
S(i,0) – q for i ? 0
I(0,j – 1) – r for j ? 0
max{S(i,j–1) – q - r,I(i – 1,j) – r}
算法设计与分析 39
动态规划法求序列相似性
? Alignment(int m,int n,char A[m],char B[n])
? int S[m][n],D[m][n],I[m][n];
? {
? 初始化；
? 从 (i,j) = (1,1)到 (m,n)逐个计算并填写
D[i,j], I[i,j]和 S[i,j]；
? 输出 S(m,n);
? }
算法设计与分析 40
递归式中的数据依赖
? 由递归式
可知 S(i,j)依赖于 S(i–1,j–1),D(i,j)和 I(i,j)。
S(i,j) =
0 m = 0,n = 0
D(i,0) for j ? 0
I(0,j) for i ? 0
max{S(i–1,j–1)+σ(ai,bj),D(i,j),I(i,j)}
S(i–1,j–1) D(i,j) I(i,j)
S(i,j)
由递归式
可知 D(i,j)依赖于 S(i – 1,j),D(i – 1,j) 。
D(i,j) =
S(0,j) – q for j ? 0
D(i – 1,0) – r for i ? 0
max{S(i–1,j) – q - r,D(i – 1,j) – r}
S(i–1,j) D(i–1,j)
D(i,j)
由递归式
可知 (i,j)依赖于 S(i – 1,j),(i – 1,j) 。
I(i,j) =
S(i 0) for i ? 0
I(0,j – 1) – r for j ? 0
ax{S(i,j – 1) – q - r,I(i – 1,j) – r}
S(i,j–1) I(i–1,j)
I(i,j)
? 递归式中的数据依赖关系如下面的三个
图所示。在用循环程序实现这些递归式
时，必须要保证在计算的过程中能够满
足这里的数据依赖关系。
算法设计与分析 41
递归式中的数据依赖
S(i–1,j–1) D(i,j) I(i,j)
S(i,j)
S(i–1,j) D(i–1,j)
D(i,j)
S(i,j–1) I(i–1,j)
I(i,j)
0 j
i
S[m,n]
0 j
i
D[m,n]
0 j
i
I[m,n]
S[i,j] D[i,j] I[i,j]
? 由数据依赖关系可知，：在 i和 j方向上按 D[i,j]、
I[i,j],S[i,j]逐个进行是可行的计算。
算法设计与分析 42
初始化的工作
? Initialization ( ){
? S[0][0] = 0; D[0][0] = –q; I[0][0] = –q
? for (int i = 1; i <= m; i++)
? {D[i][0] = D[i –1][0] – r; S[i][0] = D[i][0];
? I[i][0] = S[i][0] – q;}
? for (int j = 1; j <= n; j++)
? {I[0][j] = I[0][j –1] – r; S[0][j] = I[0][j];
? D[0][j] = S[0][j] – q;}
? }
算法设计与分析 43
S[i,j],D[i,j]和 I[i,j]的计算
? while (i <=m && j <= n) do {
? for (int t = j; t <= n; t++)
? {D[i][t] = max{D[i–1][t] – r,S[i–1][t] – q – r};
? I[i][t] = max{I[i][t–1] – r,S[i][t–1] – q – r};
? S[i][t] = max{S[i –1][t–1] +σ(ai,bt),D[i][t],I[i][t]};}
? for (int t = i; t <= m; t++)
? D[i][t] = max{D[i–1][t] – r,S[i–1][t] – q – r};
? I[i][t] = max{I[i][t–1] – r,S[i][t–1] – q – r};
? S[i][t] = max{S[i –1][t–1] +σ(ai,bt),D[i][t],I[i][t]};}
? i++; j ++}
算法设计与分析 44
动态规划总结
? 与分治法相比，相同之处是也将原问题分解为
若干子问题，再递归求解；不同之处是所分解
的子问题彼此并不独立，而是互有重叠。
? 基本思想是造表记录已解的子问题，再次遇到
时仅查表即可，避免了重复计算，提高效率。
? 通常用于求解具有最优性质的问题，而且其子
问题也具有最优性质 (最优子结构性质 )。
? 实现方法通常为自底向上的递归形式，但也可
以采用自上而下的形式 (备忘录方法 )。
第四章
动态规划
算法设计与分析 2
矩阵连乘问题
? 给定 n个矩阵,A1,A2,…,A n，其中 Ai与 Ai+1是
可乘的。确定一种连乘的顺序，使得矩阵连
乘的计算量为最小。
? 设 A和 B分别是 p× q和 q× r的两个矩阵，则乘
积 C=AB为 p× r的矩阵，计算量为 pqr次数乘。
? 但是对于多于 2个以上的矩阵连乘，连乘的顺
序却非常重要，因为不同的顺序的总计算量
将会有很大的差别。
算法设计与分析 3
不同计算顺序的差别
? 设矩阵 A1,A2和 A3分别为 10× 100,100× 5和
5× 50的矩阵，现要计算 A1A2A3 。
? 若按 ((A1A2)A3)来计算，则需要的数乘次数为
10× 100× 5 + 10× 5× 50 = 7500
? 若按 (A1(A2 A3))来计算，则需要的数乘次数为
100 × 5 × 50+ 10× 100× 50 = 75000
? 后一种计算顺序的计算量竟是前者的 10倍！
? 所以，求多个矩阵的连乘积时，计算的结合
顺序是十分重要的。
算法设计与分析 4
不同计算顺序的数量
? 设 n个矩阵的连乘积有 P(n)个不同的计算顺序。
? 先在第 k个和第 k+1个矩阵之间将原矩阵序列
分成两个矩阵子序列,k=1,…, n；再分别
对两个子序列完全加括号，最后对结果加括
号，便得到原序列的一种完全加括号方式。
由此可得出关于 P(n)的递归式：
P(n) = 1 n = 1n–1∑P(k) P(n–k) n＞ 1
k=1
? 解此递归方程可得 P(n) = C(n–1)，其中
C(n) = 1n+1 2nn = Ω(4n/n3/2)
? 所以 P(n)随 n的增长呈指数增长。因而穷举搜
索法不是有效的算法。
算法设计与分析 5
分解最优解的结构
? 将矩阵连乘积 AiAi+1…A j记为 A[i,j]。
? 若 A[1,n] 的一个最优解是在矩阵 Ak和 Ak+1处
断开的，即 A[1,n] = (A[1,k] A[k+1,n])，则
A[1,k]和 A[k+1,n]也分别是最优解。
? 事实上，若 A[1,k]的一个计算次序所需计算量
更少的话，则用此计算次序替换原来的次序，
则得到 A[1,n]一个更少的计算量，这是一个矛
盾。同理 A[k+1,n]也是最优解。
? 最优子结构性质：最优解的子结构也最优的。
算法设计与分析 6
建立递归关系
? 令 m[i][j],1≤i,j≤n，为计算 A[i,j] 的最少数乘
次数，则原问题为 m[1][n]。
? 当 i = j时,A[i,j]为单一矩阵,m[i][j] = 0；
? 当 i＜ j时，利用最优子结构性质有：
m[i][j] = min{m[i][k] + m[k+1][j] + pi–1pkpj}i≤k＜ j
其中矩阵 Ai, 1≤i≤n，的维数为 pi–1× pi。
? 根据此递归式就可以直接用递归程序来实现。
算法设计与分析 7
直接递归的时间复杂性
? 根据前面的递归式不难得出的时间复杂性为
n–11 + ∑(T(k) + T(n–k) + 1)
k=1
T(n) ≥
n–1= 1 + (n –1) +∑(T(k) + T(n–k))
k=1
n–1 n–1= n +∑T(k) + ∑T(n–k)
k=1 k=1
? 可用数学归纳法证明 T(n)≥2n–1 = Ω(2n)。
? 直接递归算法的时间复杂性随 n的指数增长。
n–1 = n + 2∑T(k)
k=1
算法设计与分析 8
直接递归中有大量重复计算
? 直接递归中有大量重复计算，如 A[1,4]计算中：
1,4
1,1 2,4
1,2 3,4
1,3 4,4
2,2 3,4 2,3 4,4
1:1 2,2 3,3 4,4
1,1 2,3 1,2 3,3
3,3 4,4 2,2 3,3 2,2 3,3 1,1 2,2
图中红框标出的
都是重复计算。
算法设计与分析 9
消除重复的计算
? 要消除重复计算，可在在计算过程中保存已解
决的子问题的答案。这样，每个子问题只计算
一次，而在后面需要时只要简单查一下，从而
避免重复计算。
? 计算方式可依据递归式自底向上地进行。
? 注意到在此问题中,不同的有序对 (i,j)就对应
不同的子问题，因此 不同的子问题个数个数最
多只有 Cn2+ n = ?(n2)个。
? 这样便可以得到多项式时间的算法。
算法设计与分析 10
自底向上的计算
? 例如对于 A1A2A3A4,依据递归式以自底向上的
方式计算出各个子问题，其过程如下：
m[1][1] m[2][2] m[3][3] m[4][4]
m[1][2] m[2][3] m[3][4]
m[1][3] m[2][4]
m[2][4] 其中
m[i][i] = 0
m[i][i+1] = pi–1pipi+1
m[i][j] = mini≤k＜ j
{m[i][k]+m[k+1][j]+pi–1pkpj}
例如,m[1][3] =
min m[1][1]+m[2][3]+p0p1p3m[1][2]+m[3][3]+p
0p2p3
算法设计与分析 11
消除重复的矩阵连乘算法
? Void MatrixChain(int p,int n,int **m,int **s)
? { for (int i = 1; i <= n; i++) m[i][i] = 0;
? //将对角线元素赋值为零，即单个矩阵计算量为 0
? for (int r = 2; r <= n; r++)
? for (int i = 1; i <= n – r +1; i++) {
? int j = i + r – 1;
? (5) m[i][j] = m[i+1][j] + p[i–1]*p[i]*p[j];
? //计算 A[i,j] = A[i,i] A[i+1,j]
? s[i][j] = i; //记下断点 i
? (7) for (int k = i + 1; k < j; k++) {
? int t = m[i][k] + m[k+1][j] + p[i–1]*p[k]*p[j];
? //对 i<k<j,逐个计算 A[i,j] = A[i,k] A[k+1,j]
? if (t < m[i][j]) {m[i][j] = t; s[i][j] = k;}
? //记下较小的 m[i][j]及相应的断点 k
? }}}
第 (5)步与第 (7)步
能否合在一起?
能。此处分开是为
了给 m[i][j]赋初值。
算法设计与分析 12
MatrixChain的运行举例
设要计算矩阵连乘积 A1A2A3A4A5A6，其维数分别
为 35× 35,35× 15,15× 5,5× 10,10× 20,20× 25,
即 p0=35,p1=35,p2=15,p3=5,p4=10,p5=20,p6=25。
MatrixChain用矩阵 m[i][j],s[i][j]存放子问题 A[i,j]
的最小计算量以及相应的断点。
1
2
3
4
5
6
1 2 3 4 5 6
m[i][j]
1
2
3
4
5
6
1 2 3 4 5 6
s[i][j]
trix hain将如下面红色箭头所示的过程逐个计算
子问题 A[i,j]：
执行 for (int i = 1; i <= n; i++) m[i][i] = 0后将对角线元素全
部置零，即子问题 A[i][i] = 0。
0
0
0
0
0
0
当 r=2，执行 第 (5)句 完成了相邻矩阵 [i][i+1]=p[i–1]*p[i]*p[j]
的计算，并在 s[i][j]中添入了相应的断点。其中的 第 (7)句 因
为 j = i+1(k=i+1)而被跳过去了，实际并没有执行。
15750
2625
750
1000
5000
1
2
3
4
5
当 r=3,i=1时，执行 第 (5)句 计算 A[1:1][2:3],m[1][3] =
m[2][3] + p[0]*p[1]*p[3] = 2625 +30*35*5 = 7875
7875 1
执行 第 (7)句 计算 A[1:2][3:3],t = m[1][2] + m[3][3] +
p[0]*p[2]*p[3] = 15750+0+35*15*5 = 18375＞ 7875，所以
m[1][3]不变，断点仍为 1。
当, =2时，执行 第 句 计算 2:2] 3:4],[2][4] =
3] 4] 1] 2] 4] = 750 +35*15*10 = 6000
6000 2
执行 第 (7)句 计算 A[2:3][4:4],t = m[2][3]+m[4][4]+
p[1]*p[3]*p[4] = 2625+0+35*5*10 = 4375＜ 6000，所以
m[2][4]改为 4375，断点改为 3。
4375 3
当 r=3,i=3时，执行 第 (5)句 计算 [3:3][4:5],3] 5]
[4][5] + p[2]*p[3]*p[5] = 1000 +15*5*20 = 2500
2500 3
执行 第 (7)句 计算 [3:4][5:5],t = m[3][4] [5][5]+
p[2]*p[4]*p[5] = 750+0+15*10*20 = 3750＞ 2500，所以
[3][5]仍为 2500，断点仍为 3。
当 r=3,i=4时，执行 第 (5)句 计算 A[4:4][5:6],m[4][6] =
m[5][6] + p[3]*p[4]*p[6] = 5000 +5*10*25 = 6250
6250 4
执行 第 ( 句 计算 [4:5][6:6],[4][5] [6][6]
3] 5] 6] = 1000+0+5*20*25 = 3500＜ 6250，所以
[4][6]改为 3500，断点改为 5。
3500 5
类似的，当 r=4,5,6时，可以计算出相应的 [i][j]及其相
应的断点 s[i][j]，如下图中所示：
9375 3
7125 3
5375 3
11875 3
10500 3
15125 3
由 m[1][6]=15125可知这 6个矩阵连乘积的最小运算次数为
15125。由 s[1][6] = 3可知 A[1,6]的最优计算次序为 A[1,3]
A[4,6]；由 s[1][3]=1可知 A[1,3]的最优计算次序为 A[1,1]
A[2,3]；由 s[4][6]=5可知 A[4,6]的最优计算次序为 A[4,5]
A 6,6]；因此最优计算次序为,(A1(A2A3))((A4A5)A6)。
算法设计与分析 13
MatrixChain的时间复杂性
? 算法 MatrixChain的主要计算取决于程序
中对 r,i和 k的三重循环。循环体内的计
算量为 O(1),1≤ r,i,k≤n，三重循环的
总次数为 O(n3)。因此该算法时间复杂性
的上界为 O(n3)，比直接递归算法要有效
得多。算法使用空间显然为 O(n2)。
? 这种算法称为动态规划。
算法设计与分析 14
动态规划的基本思想
? 将原问题分解为若干个子问题，先求子问题的
解，然后从这些子问题的解得到原问题的解。
? 这些子问题的解往往不是相互独立的。在求解
的过程中，许多子问题的解被反复地使用。为
了避免重复计算，动态规划算法采用了填表来
保存子问题解的方法。
? 在算法中用表格来保存已经求解的子问题的解，
无论它是否会被用到。当以后遇到该子问题时
即可查表取出其解，避免了重复计算。
算法设计与分析 15
动态规划的基本要素
? 最优子结构：问题的最优解是由其子问题的最
优解所构成的。
? 重叠子问题：子问题之间并非相互独立的，而
是彼此有重叠的。
最优子结构性质使我们能够以自底向上的方式
递归地从子结构的最优解构造出问题的最优解。
因为子问题重叠，所以存在着重复计算。这样
就可以用填表保存子问题解的方法来提高效率。
算法设计与分析 16
动态规划的基本方法
? 动态规划通常可以按以下几个步骤进行：
? (1)找出最优解的性质，并刻画其结构特征；
? (2)递归地定义最优值；
? (3)以自底向上的方式计算出各子结构的最优值
并添入表格中保存；
? (4)根据计算最优值时得到的信息，构造最优解。
? 步骤 1~3是动态规划算法的基本步骤。若需要
最优解，则必须执行第 4步,为此还需要在第 3
步中记录构造最优解所必需的信息 。
算法设计与分析 17
动态规划的备忘录方法
? 动态规划中采用自底向上的方式。但是在递归
定义中往往是自上而下的描述。备忘录方法就
采用与递归定义一致的自上而下的方式。
? 备忘录方法同样用表格来保存已解子问题的信
息。每个子问题初始化时都标记为尚未求解。
在递归求解过程中，对每个待解子问题，先查
看它是否已求解。若未求解，则计算其解并填
表保存。若已求解，则查表取出相应的结果。
? 备忘录方法同样避免了子问题的重复计算，因
而和动态规划算法具有同样效率。
算法设计与分析 18
凸多边形最优三角剖分
? 凸多边形的三角剖分是将一个凸多边形分割成
互不相交的三角形的弦的集合 T。
? 下面是一个凸 7边形的 2个不同的三角剖分：
v0v
1
v2
v3 v4
v5
v6
v0v
1
v2
v3 v4
v5
v6
在凸多边形的一个三角剖分 T中，各弦互不相
交，且 T已达到最大，即任何一条不在 T中的弦
必与 T中某弦相交。
? 在有 n个顶点的凸多边形的中三角剖分中，恰
有 n–3条弦和 n–2个三角形。
? 凸多边形的最优三角剖分问题：给定凸多边形
P={v0,v1,…,v n–1},以及定义在由凸多边形的
边和弦组成的三角形上的权函数 w。要求确定
该凸多边形的一个三角剖分，使得该剖分中诸
三角形上权之和为最小。
? 可定义三角形上各种各样的权函数 w。
? 例如 w(vivjvk) = |vivj| + |vjvk| + |vkvi|，其中 |vivj|是
点 vi到 vj的欧氏距离。相应于此权函数的最优三
角剖分即为最小弦长三角剖分。
算法设计与分析 19
三角剖分与矩阵连乘积同构
? 三角剖分问题和矩阵连乘积问题都对应于一个
完全二叉树，也称为表达式的语法树。
0
1 2
3A1 A4 4
A2 A3 A5 A6
((A1(A2A3))(A4(A5A6))
所对应的二叉树
v1
v0
v2
v3 v4
v5
v60
1
2
A1
3A2
A3
A4
4
A5
A6
凸多边形 v0v1v2v3v4v5v6
一个三角剖分所对应
的二叉树
? n个矩阵连乘积计算顺序同构于 n个叶子的完全
二叉树，凸 (n+1)边形三角剖分同构于 n个叶子
的完全二叉树，所以 n个矩阵连乘积的计算顺
序问题同构于凸 (n+1)边形的三角剖分问题。
? 事实上，矩阵连乘积最优计算顺序问题相当于
是凸多边形最优三角剖分问题中一种特殊定义
的权函数的情形。
算法设计与分析 20
最优子结构性质
? 能应用动态规划求解的问题应具有最优子结构
性质。凸多边形最优三角剖分问题具有最优子
结构性质。
? 事实上，若 凸 (n+1)边形 P={v0,v1,…,v n}的一个
最优三角剖分 T包含了三角形 v0vkvn,1≤k＜ n，
则 T的权为三角形 v0vkvn，多边形 {v0,v1,…,v k}
和多边形 {vk,vk+1,…,v n}的权之和。显然这两
个子多边形的三角剖分也是最优的。
? 因为，其中若有一个子多边形的三角剖分不是
最优的将导致 T不是最优三角剖分的矛盾。
算法设计与分析 21
最优三角剖分的递归结构
? 定义 t[i][j],1≤i<j≤n,为子多边形 {vi–1,vi,…,v j}的
最优三角剖分所对应的权函数值，并为方便起
见，设退化的多边形 {vi–1,vi}的权值为 0。
? 于是凸 (n+1)边形的最优三角剖分为 t[1][n]
? 易知,t[i][j]可递归定义为
? 当 i = j时，为退化多边形 {vi–1,vi},t[i][j] = 0；
? 当 i＜ j时，利用最优子结构性质有：
t[i][j] = min{t[i][k] + t[k+1][j] + w(vi–1vkvj)}i≤k＜ j
与矩阵连乘积问题相对比：
m[i][j] = min{m[i][k] + m[k+1][j] + pi–1pkpj}i≤k＜ j
? 显然，矩阵连乘积的最优计算顺序与 凸多边形
最优三角剖分具有完全相同的递归结构。
算法设计与分析 22
最优三角剖分的算法
? 由于凸多边形最优三角剖分与矩阵连乘
积的最优计算顺序具有完全相同的递归
结构，其区别仅在于权函数的不同，所
以只需要修改求矩阵连乘积的最优计算
顺序的算法中的权函数计算便可得到凸
多边形最优三角剖分的算法。
? 显然该算法的时间复杂性也是 O(n3)。
? Void MinWeightTriangulation(int n,Type **t,int **s)
? { for (int i = 1; i <= n; i++) t[i][i] = 0;
? for (int r = 2; r <= n; r++)
? for (int i = 1; i <= n – r +1; i++) {
? int j = i + r – 1;
? t[i][j] = t[i+1][j] + w(i–1,i,j);
? s[i][j] = i;
? for (int k = i + 1; k < j; k++) {
? int u = t[i][k] + t[k+1][j] + w(i–1,k,j);
? if (u < t[i][j]) {t[i][j] = u; s[i][j] = k;}
? }}} //程序中红色的部分为改动的地方
算法设计与分析 23
多边形游戏
? 有一个 n边形，每个顶点被赋予一整数值，每
条边上被赋予一个运算符,+”或,*”。
? 游戏的第 1步，将一条边删去；
? 随后的 n–1步按以下方式操作：
? (1)选择一条边 E及其所连接的两个顶点 v1和 v2；
? (2) 用一个新顶点取代边 E以及顶点 v1和 v2，赋
予新顶点的值为顶点 v1和 v2的值通过 边 E上的
运算所得到的值。
? 最后所有的边被删去，所剩顶点的值即为得分。
算法设计与分析 24
多边形游戏的表达
? 设所有的边依次从 1到 n编号，按顺时针序列为
op[1],v[1],op[2],v[2],…,op[n],v[n]
其中 op[i]为边 i上的运算符,v[i]顶点 i上的值。
? 将多边形中始于顶点 i (1≤i≤n)，长度为 j 的顺时
针链 v[i],op[i+1],…,v[i+j –1]表示为 p(i,j)。
? 若链 p(i,j)最后一次合并在 op[i+s](1≤s≤j–1)处发
生，则被分割为两个子链 p(i,s)和 p(i+s,j–s)
算法设计与分析 25
多边形游戏的最优子结构性质
? 若链 p(i,j)取最优值的最后一次合并是在 op[i+s]
处发生的，则子链 p(i,s)和 p(i+s,j–s)也是最优。
? 因为若子链 p(i,s)和 p(i+s,j–s)不是最优的，则
可推出链 p(i,j)也不是最优的矛盾。所以多边形
游戏具有最优子结构性质。
? 但是这里的最优子结构要稍微地复杂一点。若 p(i,j)的最后合并的边 op[i+s] =“+”，子链 p(i,
s)和 p(i+s,s)应该取最大值，
? 若 p(i,j)的最后合并的边 op[i+s] =“*”，子链 p(i,s)
和 p(i+s,j–s)是否仍然取最大值呢？ 不见得！
算法设计与分析 26
多边形游戏的最优子结构分析
? 设 m1是对子链 p(i,s)的任意合并方式得到的值，
a和 b是其最小值和最大值,m2是对子链 p(i+s,
j–s)的任意合并方式得到的值,c和 d分别是最
小值和最大值，即 a≤m1≤b,c≤m2≤d。
? 若 op[i+s] =“+”，则 a+c≤m≤b+d。可见 p(i,s)的最
小、最大值分别对应于子链的最小、最大值。
? 若 op[i+s] =“*”，由于 v[i]可取负整数，所以
min{ac,ad,bc,bd}≤m≤max{ac,ad,bc,bd}。
? 即主链最小、最大值亦来自子链最小、最大值。
算法设计与分析 27
多边形游戏的递归求解
? 由前面的分析可知，为了求链合并的最大值，
必须同时求子链合并的最大值和最小值。因此
整个计算过程中应同时计算最大值和最小值。
设链 p(i,j)合并的最大、最小值分别是 m[i,j,0]
和 m[i,j,1]，最优合并处是在 op[i+s],且长度
小于 j的子链的最大、最小值均已算出，且记：
? a = m[i,i+s,0],b = m[i,i+s,1],c = m[i+s,j–s,0]，
d = m[i+s,j–s,1]，则
? ⑴当 op[i+s] =,+”时，
m[i,j,0] = a + c,m[i,j,1] = b + d
? ⑵ 当 op[i+s] =,*”时，
m[i,j,0] = min{ac,ad,bc,bd}
m[i,j,1] = max{ac,ad,bc,bd}
算法设计与分析 28
多边形游戏的递归求解
? 令 p(i,j)在 op[i+s]断开的最大值和最小值分别为
maxf(i,j,s)和 minf(i,j,s),综合上面的讨论则
minf(i,j,s) = a + c op[i+s] =,+”min{ac,ad,bc,bd} op[i+s] =,*”
maxf(i,j,s) = b + d op[i+s] =,+”max{ac,ad,bc,bd} op[i+s] =,*”
? 由于 p(i,j)的最优断开位置 s有 1≤s≤j–1的 j–1中情
况，于是便可得到求解多边形游戏的递归式：
算法设计与分析 29
求解多边形游戏的递归式
? 由于多边形是封闭的，当 i+s＞ n时，顶点 i+s实
际编号应为 (i+s)mod n。
? 多边形游戏的最大得分即为 m[i,n,1]。
m[i,j,0] = min{minf (i,j,s) },1≤i,j≤n
1≤s≤j
m[i,j,1] = max{maxf (i,j,s) },1≤i,j≤n
1≤s≤j
初始边界值为：
m[i,1,0] = m[i,1,1] = v[i],1≤i≤n,j = 1
算法设计与分析 30
多边形游戏的动态规划算法
? 依据上述讨论以及所得的递归式，不难写出多
边形游戏动态规划算法。请同学们自己编写。
? 算法的主程序为 Poly_Max，它包含了一个子程
序 MIN_MAX。子程序 MIN_MAX负责对确定 s
的 minf (i,j,s)和 maxf (i,j,s)的计算。而对任意
链的最大值 m[i,j,1]和最小值 m[i,j,0]的计算则
是在主程序 Poly_Max中进行的。
? 算法的时间复杂性显然仍为 O(n3)。
算法设计与分析 31
DNA序列的相似性
? 将序列 A,B表示 为对偶 (a,b)的序列。其中若：
? 1,a?A和 b?B称为替换,a = b称为匹配，否则
称为不匹配，其得分为 σ (a,b)；
? 2,a?A,b是空位为删除空白；
? 3,a是空位,b?B为插入空白；
? 对于长度为 k的空位，其得分为 –(q + k ? r)。
? 这里，参数 σ (a,b),q和 r由用户确定。
? 两个序列 A,B的相似性为所有这样的对偶序
列中最高的得分。
算法设计与分析 32
DNA序列的相似性
? 若给定两个 DNA序列：
AGCTACGTACACTACC
AGCTATCGTACTAGC
? 下面是其一个相似性序列：
AGCTA–CGTACACTACC
AGCTATCGTAC– –TAGC
? 其中有 13个匹配,1个不匹配、一个长度为 1的
插入空白和一个长度为 2的删除空白。
若,a = b时 σ (a,b) = 10； a ? b时 σ (a,b) = –20；
q = 40； r = 2。该相似性序列的得分为
10 * 13 – 20 – (40 + 2) – (40 + 2 * 2) = 24
算法设计与分析 33
递归求序列相似性
? 设 A = a1a2…a m,B = b1b2…b n。令 S(m,n)为 A和
B的相似性，即各种对偶序列最大的得分。
? 为了采用递归方法来求解此问题，我们从序列
尾部来考虑，那么有三种方案：
? ①尾部用替换，即最后一个对偶为 (am,bn)；
? ②尾部用删除空白，即最后一个对偶为 (am,–)；
? ③尾部用插入空白，即最后一个对偶为 (–,bn)。
? 令 S(m,n),D(m,n)和 I(m,n)分别为三种方案的
得分，则 其相似性应为三种方案的最大得分。
算法设计与分析 34
递归求序列相似性
S(m,n) = S(m – 1,n – 1) + σ(am,bn)。
?若用方案①，即尾部用替换，则
D(m,n) = S(m – 1,n) – q – r
或者,D(m,n) = D(m – 1,n) – r
?若用方案②，即尾部用删除空白，则
I(m,n) = S(m,n – 1) – q – r
或者,I(m,n) = I(m,n – 1) – r
?若用方案③，即尾部用插入空白，则
算法设计与分析 35
递归求序列相似性
? 现在考虑非递归分支：
S(0,0) = 0,S(m,0) = D(m,0),S(0,n) = I(0,n)。
?对方案①，有
D(m,0) = D(m – 1,0) – r,D(0,n) = S(0,n) – q。
?对方案②，有
I(m,0) = S(m,0) – q,I(0,n) = S(0,n – 1) – q。
?对方案③，有
算法设计与分析 36
递归求序列相似性
? S(m,n) =
0 m = 0,n = 0
D(m,0) for n ? 0
I(0,n) for m ? 0
max{S(m–1,n–1)+σ(am,bn),D(m,n),I(m,n)}
? D(m,n) =
S(0,n) – q for n ? 0
D(m – 1,0) – r for m ? 0
max{S(m–1,n) – q - r,D(m – 1,n) – r}
? I(m,n) =
S(m,0) – q for m ? 0
I(0,n – 1) – r for n ? 0
max{S(m,n–1) – q - r,I(m – 1,n) – r}
算法设计与分析 37
动态规划求序列相似性
? 如果用递归算法求序列的相似性，其时间复杂
性显然是指数级的。
? 考虑采用动态规划法。为此，需要
? ⑴用矩阵 S[0:m,0:n],D[0:m,0:n]和 I[0:m,0,n]
来分别记载对应于子序列 Ai和 Bj的得分 S(i,j)、
D(i,j)和 I(i,j),0 ? i ? m,0 ? j ? n。
? ⑵从 (0,0)开始逐个计算 S(i,j),D(i,j)和 I(i,j)并
将结果记入 S[i,j],D[i,j]和 I[i,j]。
? ⑶必要时，是用辅助矩阵记载每步的方案。
算法设计与分析 38
动态规划法的递归式
? S(i,j) =
0 m = 0,n = 0
D(i,0) for j ? 0
I(0,j) for i ? 0
max{S(i–1,j–1)+σ(ai,bj),D(i,j),I(i,j)}
? D(i,j) =
S(0,j) – q for j ? 0
D(i – 1,0) – r for i ? 0
max{S(i–1,j) – q - r,D(i – 1,j) – r}
? I(i,j) =
S(i,0) – q for i ? 0
I(0,j – 1) – r for j ? 0
max{S(i,j–1) – q - r,I(i – 1,j) – r}
算法设计与分析 39
动态规划法求序列相似性
? Alignment(int m,int n,char A[m],char B[n])
? int S[m][n],D[m][n],I[m][n];
? {
? 初始化；
? 从 (i,j) = (1,1)到 (m,n)逐个计算并填写
D[i,j], I[i,j]和 S[i,j]；
? 输出 S(m,n);
? }
算法设计与分析 40
递归式中的数据依赖
? 由递归式
可知 S(i,j)依赖于 S(i–1,j–1),D(i,j)和 I(i,j)。
S(i,j) =
0 m = 0,n = 0
D(i,0) for j ? 0
I(0,j) for i ? 0
max{S(i–1,j–1)+σ(ai,bj),D(i,j),I(i,j)}
S(i–1,j–1) D(i,j) I(i,j)
S(i,j)
由递归式
可知 D(i,j)依赖于 S(i – 1,j),D(i – 1,j) 。
D(i,j) =
S(0,j) – q for j ? 0
D(i – 1,0) – r for i ? 0
max{S(i–1,j) – q - r,D(i – 1,j) – r}
S(i–1,j) D(i–1,j)
D(i,j)
由递归式
可知 (i,j)依赖于 S(i – 1,j),(i – 1,j) 。
I(i,j) =
S(i 0) for i ? 0
I(0,j – 1) – r for j ? 0
ax{S(i,j – 1) – q - r,I(i – 1,j) – r}
S(i,j–1) I(i–1,j)
I(i,j)
? 递归式中的数据依赖关系如下面的三个
图所示。在用循环程序实现这些递归式
时，必须要保证在计算的过程中能够满
足这里的数据依赖关系。
算法设计与分析 41
递归式中的数据依赖
S(i–1,j–1) D(i,j) I(i,j)
S(i,j)
S(i–1,j) D(i–1,j)
D(i,j)
S(i,j–1) I(i–1,j)
I(i,j)
0 j
i
S[m,n]
0 j
i
D[m,n]
0 j
i
I[m,n]
S[i,j] D[i,j] I[i,j]
? 由数据依赖关系可知，：在 i和 j方向上按 D[i,j]、
I[i,j],S[i,j]逐个进行是可行的计算。
算法设计与分析 42
初始化的工作
? Initialization ( ){
? S[0][0] = 0; D[0][0] = –q; I[0][0] = –q
? for (int i = 1; i <= m; i++)
? {D[i][0] = D[i –1][0] – r; S[i][0] = D[i][0];
? I[i][0] = S[i][0] – q;}
? for (int j = 1; j <= n; j++)
? {I[0][j] = I[0][j –1] – r; S[0][j] = I[0][j];
? D[0][j] = S[0][j] – q;}
? }
算法设计与分析 43
S[i,j],D[i,j]和 I[i,j]的计算
? while (i <=m && j <= n) do {
? for (int t = j; t <= n; t++)
? {D[i][t] = max{D[i–1][t] – r,S[i–1][t] – q – r};
? I[i][t] = max{I[i][t–1] – r,S[i][t–1] – q – r};
? S[i][t] = max{S[i –1][t–1] +σ(ai,bt),D[i][t],I[i][t]};}
? for (int t = i; t <= m; t++)
? D[i][t] = max{D[i–1][t] – r,S[i–1][t] – q – r};
? I[i][t] = max{I[i][t–1] – r,S[i][t–1] – q – r};
? S[i][t] = max{S[i –1][t–1] +σ(ai,bt),D[i][t],I[i][t]};}
? i++; j ++}
算法设计与分析 44
动态规划总结
? 与分治法相比，相同之处是也将原问题分解为
若干子问题，再递归求解；不同之处是所分解
的子问题彼此并不独立，而是互有重叠。
? 基本思想是造表记录已解的子问题，再次遇到
时仅查表即可，避免了重复计算，提高效率。
? 通常用于求解具有最优性质的问题，而且其子
问题也具有最优性质 (最优子结构性质 )。
? 实现方法通常为自底向上的递归形式，但也可
以采用自上而下的形式 (备忘录方法 )。
