1
第 3章 动态规划
2
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题
n
T(n/2) T(n/2) T(n/2) T(n/2)
T(n) =
3
算法总体思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题
n
T(n/2) T(n/2) T(n/2) T(n/2)
T(n) =
4
但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。
算法总体思想
nT(n) =
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
5
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。
算法总体思想
n=
n/2
T(n/4) T(n/4) T(n/4) T(n/4)
n/2 n/2
T(n/4)T(n/4)
n/2
T(n/4) T(n/4) T(n/4)T(n/4) T(n/4)
T(n)Those who cannot remember the past
are doomed to repeat it,
-----George Santayana,
The life of Reason,
Book I,Introduction and
Reason in Common
Sense (1905)
6
动态规划基本步骤
找出最优解的性质，并刻划其结构特征。
递归地定义最优值。
以自底向上的方式计算出最优值。
根据计算最优值时得到的信息，构造最优解。
7
完全加括号的矩阵连乘积
（ 1）单个矩阵是完全加括号的；
（ 2）矩阵连乘积 是完全加括号的，则 可表示为 2个完全加括号的矩阵连乘积 和的乘积并加括号，即
A A
B C
)(BCA?
DCBA,,,
1050A 4010B 3040C 530D
)))((( DBCA
)))( ( ( DCAB )))((( DBCA
) ) )((( CDBA )))((( CDAB
16000,10500,36000,87500,34500
完全加括号的矩阵连乘积可递归地定义为：
设有四个矩阵,它们的维数分别是：
总共有五中完全加括号的方式
8
矩阵连乘问题
给定 n个矩阵,其中 与 是可乘的,。考察这 n个矩阵的连乘积
由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用 2个矩阵相乘的标准算法计算出矩阵连乘积
},.,,,,{ 21 nAAA iA 1?iA
1,.,,,2,1 ni
nAAA,..21
9
矩阵连乘问题给定 n个矩阵｛ A1,A2,…,An｝，其中 Ai与 Ai+1是可乘的，
i=1,2,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
穷举法,列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。
算法复杂度分析：
对于 n个矩阵的连乘积，设其不同的计算次序为 P(n)。
由于每种加括号方式都可以分解为两个子矩阵的加括号问题：
(A1...Ak)(Ak+1…An)可以得到关于 P(n)的递推式如下：
)/4()(11)()(
1
)( 2/31
1
nnPnnknPkPnP nn
k
10
矩阵连乘问题
穷举法
动态规划将矩阵连乘积 简记为 A[i:j],这里 i≤j
jii AAA,..1?
考察计算 A[i:j]的最优计算次序。设这个计算次序在矩阵
Ak和 Ak+1之间将矩阵链断开,i≤k<j，则其相应完全加括号方式为
).,,)(.,,( 211 jkkkii AAAAAA
计算量,A[i:k]的计算量加上 A[k+1:j]的计算量，再加上
A[i:k]和 A[k+1:j]相乘的计算量
11
分析最优解的结构
特征：计算 A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和 A[k+1:j]的次序也是最优的。
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为 最优子结构性质 。
问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。
12
建立递归关系
设计算 A[i:j],1≤i≤j≤n，所需要的最少数乘次数
m[i,j]，则原问题的最优值为 m[1,n]
当 i=j时,A[i:j]=Ai，因此,m[i,i]=0,i=1,2,…,n
当 i<j时，
可以递归地定义 m[i,j]为：
jki pppjkmkimjim 1],1[],[],[
这里 的维数为
iA ii pp1
jipppjkmkim
ji
jim
jki }],1[],[{m in
0
],[
1jki
的位臵只有 种 可能k ij?
13
计算最优值
对于 1≤i≤j≤n不同的有序对 (i,j)对应于不同的子问题。
因此，不同子问题的个数最多只有
由此可见，在递归计算时,许多子问题被重复计算多次 。这也是该问题可用动态规划算法求解的又一显著特征。
用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法
)(2 2nnn
14
用动态规划法求最优解
public static void matrixChain(int [] p,int [][] m,int [][] s)
{
int n=p.length-1;
for (int i = 1; i <= n; i++) m[i][i] = 0;
for (int r = 2; r <= n; r++)
for (int i = 1; i <= n - r+1; i++) {
int j=i+r-1;
m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];
s[i][j] = i;
for (int k = i+1; k < j; k++) {
int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (t < m[i][j]) {
m[i][j] = t;
s[i][j] = k;}
}
}
}
A1 A2 A3 A4 A5 A6
30?35 35?15 15?5 5?10 10?20 20?25
1 1 3 7 520103504 3 7 5]5][5[]4][2[
7 1 2 5205351 0 0 02 6 2 5]5][4[]3][2[
1 3 0 0 02015352 5 0 00]5][3[]2][2[
m i n]5][2[
541
531
521
pppmm
pppmm
pppmm
m
算法复杂度分析：
算法 matrixChain的主要计算量取决于算法中对 r，
i和 k的 3重循环。循环体内的计算量为 O(1)，而 3重循环的总次数为 O(n3)。因此算法的计算时间上界为 O(n3)。算法所占用的空间显然为 O(n2)。
15
动态规划算法的基本要素一、最优子结构
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为 最优子结构性质 。
在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
注意：同一个问题可以有多种 方式刻划 它 的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）
16
二、重叠子问题
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。 这种性质称为 子问题的重叠性质 。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
17
三、备忘录方法
备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。
m?0
private static int lookupChain(int i,int j)
{
if (m[i][j] > 0) return m[i][j];
if (i == j) return 0;
int u = lookupChain(i+1,j) + p[i-1]*p[i]*p[j];
s[i][j] = i;
for (int k = i+1; k < j; k++) {
int t = lookupChain(i,k) + lookupChain(k+1,j) + p[i-1]*p[k]*p[j];
if (t < u) {
u = t; s[i][j] = k;}
}
m[i][j] = u;
return u;
}
18
最长公共子序列
若给定序列 X={x1,x2,…,x m}，则另一序列 Z={z1,z2,…,z k}，
是 X的子序列是指存在一个严格递增下标序列 {i1,i2,…,i k}
使得对于所有 j=1,2,…,k 有,zj=xij。例如，序列 Z={B,C，
D,B}是序列 X={A,B,C,B,D,A,B}的子序列，
相应的递增下标序列为 {2,3,5,7}。
给定 2个序列 X和 Y，当另一序列 Z既是 X的子序列又是 Y
的子序列时，称 Z是序列 X和 Y的 公共子序列 。
给定 2个序列 X={x1,x2,…,xm}和 Y={y1,y2,…,yn}，找出 X
和 Y的最长公共子序列。
19
最长公共子序列的结构设序列 X={x1,x2,…,x m}和 Y={y1,y2,…,y n}的最长公共子序列为
Z={z1,z2,…,z k},则
(1)若 xm=yn，则 zk=xm=yn，且 zk-1是 xm-1和 yn-1的最长公共子序列。
(2)若 xm≠yn且 zk≠xm，则 Z是 xm-1和 Y的最长公共子序列。
(3)若 xm≠yn且 zk≠yn，则 Z是 X和 yn-1的最长公共子序列。
由此可见,2个序列的最长公共子序列包含了这 2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有 最优子结构性质 。
20
子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用 c[i][j]记录序列和的最长公共子序列的长度。
其中,Xi={x1,x2,…,x i}； Yj={y1,y2,…,y j}。当 i=0或 j=0时，空序列是 Xi和 Yj的最长公共子序列。故此时 C[i][j]=0。其他情况下，
由最优子结构性质可建立递归关系如下：
ji
ji
yxji
yxji
ji
jicjic
jicjic;0,;0,
0,0
]}][1[],1][[m a x {
1]1][1[
0
]][[
21
计算最优值由于在所考虑的子问题空间中，总共有 θ(mn)个不同的子问题，
因此，用动态规划算法自底向上地计算最优值能提高算法的效率。
Algorithm lcsLength(x,y,b)
1,m?x.length-1;
2,n?y.length-1;
3,c[i][0]=0; c[0][i]=0;
4,for (int i = 1; i <= m; i++)
5,for (int j = 1; j <= n; j++)
6,if (x[i]==y[j])
7,c[i][j]=c[i-1][j-1]+1;
8,b[i][j]=1;
9,else if (c[i-1][j]>=c[i][j-1])
10,c[i][j]=c[i-1][j];
11,b[i][j]=2;
12,else
13,c[i][j]=c[i][j-1];
14,b[i][j]=3;
构造最长公共子序列
Algorithm lcs(int i,int j,char [] x,int [][] b)
{
if (i ==0 || j==0) return;
if (b[i][j]== 1){
lcs(i-1,j-1,x,b);
System.out.print(x[i]);
}
else if (b[i][j]== 2) lcs(i-1,j,x,b);
else lcs(i,j-1,x,b);
}
22
算法的改进
在算法 lcsLength和 lcs中，可进一步将数组 b省去。
事实上，数组元素 c[i][j]的值仅由 c[i-1][j-1],c[i-1][j]和
c[i][j-1]这 3个数组元素的值所确定。对于给定的数组元素 c[i][j]，可以不借助于数组 b而仅借助于 c本身在时间内确定 c[i][j]的值是由 c[i-1][j-1],c[i-1][j]和 c[i][j-1]中哪一个值所确定的。
如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算 c[i][j]时，只用到数组 c的第 i行和第 i-1行。因此，用 2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至 O(min(m,n))。
23
凸多边形最优三角剖分
用多边形顶点的逆时针序列表示凸多边形，即 P={v0,v1,…,v n-1}
表示具有 n条边的凸多边形。
若 vi与 vj是多边形上不相邻的 2个顶点，则线段 vivj称为多边形的一条弦。弦将多边形分割成 2个多边形 {vi,vi+1,…,v j}和 {vj,vj+1,…v i}。
多边形的三角剖分 是将多边形分割成互不相交的三角形的弦的集合 T。
给定凸多边形 P，以及定义在由多边形的边和弦组成的三角形上的权函数 w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。
24
三角剖分的结构及其相关问题
一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积
((A1(A2A3))(A4(A5A6)))所相应的语法树如图 (a)所示。
凸多边形 {v0,v1,…v n-1}的三角剖分也可以用语法树表示。例如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树表示。
矩阵连乘积中的每个矩阵 Ai对应于凸 (n+1)边形中的一条边
vi-1vi。三角剖分中的一条弦 vivj,i<j，对应于矩阵连乘积
A[i+1:j]。
25
最优子结构性质
凸多边形的最优三角剖分问题有最优子结构性质。
事实上，若凸 (n+1)边形 P={v0,v1,…,v n-1}的最优三角剖分 T包含三角形 v0vkvn,1≤k≤n-1，则 T
的权为 3个部分权的和：三角形 v0vkvn的权，
子多边形 {v0,v1,…,v k}和 {vk,vk+1,…,v n}的权之和。
可以断言，由 T所确定的这 2个子多边形的三角剖分也是最优的。因为若有 {v0,v1,…,v k}或
{vk,vk+1,…,v n}的更小权的三角剖分将导致 T不是最优三角剖分的矛盾。
26
最优三角剖分的递归结构
定义 t[i][j],1≤i<j≤n为凸子多边形 {vi-1,vi,…,vj} 的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形 {vi-1,vi}具有权值 0。据此定义，要计算的凸 (n+1)边形 P的最优权值为 t[1][n]。
t[i][j]的值可以利用最优子结构性质递归地计算。当 j-i≥1时，凸子多边形至少有 3个顶点。由最优子结构性质,t[i][j]的值应为
t[i][k]的值加上 t[k+1][j]的值，再加上三角形 vi-1vkvj的权值，其中
i≤k≤j-1。由于在计算时还不知道 k的确切位臵，而 k的所有可能位臵只有 j-i个，因此可以在这 j-i个位臵中选出使 t[i][j]值达到最小的位臵。由此,t[i][j]可递归地定义为：
ji
ji
vvvwjktkitjit jki
jki
)}(]][1[]][[{m in
0
]][[
1
27
多边形游戏多边形游戏是一个单人玩的游戏，开始时有一个由 n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符,+”或,*”。所有边依次用整数从 1到 n编号。
游戏第 1步，将一条边删除。
随后 n-1步按以下方式操作：
(1)选择一条边 E以及由 E连接着的 2个顶点 V1和 V2；
(2)用一个新的顶点取代边 E以及由 E连接着的 2个顶点 V1和 V2。
将由顶点 V1和 V2的整数值通过边 E上的运算得到的结果赋予新顶点。
最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。
问题,对于给定的多边形，计算最高得分。
28
最优子结构性质
在所给多边形中，从顶点 i(1≤i≤n)开始，长度为 j(链中有 j个顶点 )
的顺时针链 p(i,j) 可表示为 v[i],op[i+1],…,v[i+j-1]。
如果这条链的最后一次合并运算在 op[i+s]处发生 (1≤s≤j-1)，则可在 op[i+s]处将链分割为 2个子链 p(i,s)和 p(i+s,j-s)。
设 m1是对子链 p(i,s)的任意一种合并方式得到的值，而 a和 b
分别是在所有可能的合并中得到的最小值和最大值。 m2是
p(i+s,j-s)的任意一种合并方式得到的值，而 c和 d分别是在所有可能的合并中得到的最小值和最大值。依此定义有 a≤m1≤b，
c≤m2≤d
(1)当 op[i+s]='+'时，显然有 a+c≤m≤b+d
(2)当 op[i+s]='*'时，有 min{ac,ad,bc,bd}≤m≤max{ac,ad，
bc,bd}
换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。
29
图像压缩图像的变位压缩存储格式将所给的象素点序列
{p1,p2,…,pn},0≤pi≤255 分割成 m个连续段 S1,S2,…,Sm 。第 i
个象素段 Si中 (1≤i≤m)，有 l[i]个象素,且该段中每个象素都只用
b[i]位表示。设 则第 i个象素段 Si为设,则 hi?b[i]?8。因此需要用 3位表示 b[i],
如果限制 1?l[i]?255，则需要用 8位表示 l[i]。因此，第 i个象素段所需的存储空间为 l[i]*b[i]+11位。按此格式存储象素序列
{p1,p2,…,pn},需要 位的存储空间。
图像压缩问题要求确定象素序列 {p1,p2,…,pn}的最优分段，
使得依此分段所需的存储空间最少。每个分段的长度不超过
256位。
1
1
][][ i
k
klit
1m a xlo g ][][1][ kilitkiti ph
mibilm
i
11][*][
1
30
图像压缩设 l[i],b[i]，是 {p1,p2,…,pn} 的最优分段。显而易见,l[1],b[1]
是 {p1,…,p l[1]}的最优分段，且 l[i],b[i]，是 {pl[1]+1,…,p n}的最优分段。即图像压缩问题满足最优子结构性质。
设 s[i],1≤i≤n，是象素序列 {p1,…,pn} 的最优分段所需的存储位数。由最优子结构性质易知：
其中
11)},1m a x (b*][{m in][ }256,m i n {1 ikikkisis ik
1}{m a xlo g),b m a x ( kjki pji
算法复杂度分析：
由于算法 compress中对 k的循环次数不超这 256，故对每一个确定的 i，可在时间 O(1)内完成的计算。因此整个算法所需的计算时间为 O(n)。
31
电路布线在一块电路板的上、下 2端分别有 n个接线柱。根据电路设计，
要求用导线 (i,π(i))将上端接线柱与下端接线柱相连，如图所示。
其中 π(i)是 {1,2,…,n} 的一个排列。导线 (i,π(i))称为该电路板上的第 i条连线。对于任何 1≤i<j≤n，第 i条连线和第 j条连线相交的充分且必要的条件是 π(i)>π(j)。
电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集
Nets={(i,π(i)),1≤i≤n}的最大不相交子集。
32
记 。 N(i,j)的最大不相交子集为 MNS(i,j)。 Size(i,j)=|MNS(i,j)|。
(1)当 i=1时，
(2)当 i>1时，
2.1 j<π(i)。此时,。故在这种情况下，
N(i,j)=N(i-1,j)，从而 Size(i,j)=Size(i-1,j)。
2.2 j≥π(i),(i,π(i))∈ MNS(i,j) 。 则对任意 (t,π(t)) ∈ MNS(i,j)有
t<i且 π(t)<π(i)。在这种情况下 MNS(i,j)-{(i,π(i))}是 N(i-
1,π(i)-1)的最大不相交子集。
2.3 若,则对任意 (t,π(t)) ∈ MNS(i,j)有
t<i。从而 。因此,Size(i,j)≤Size(i-1,j)。
另一方面,故又有 Size(i,j)≥Size(i-1,j)，
从而 Size(i,j)=Size(i-1,j)。
电路布线
})(,,))(,(|{),( jtitN e t stttjiN
)1() ) }1(,1{(
)1(),1(),1(
j
jjNjM N S
),())(,( jiNii
),())(,( jiNii
),1(),( jiNjiM N S
),(),1( jiNjiM N S
(1)当 i=1时
(2)当 i>1时
)1(1
)1(0),1(
j
jjS iz e
)(
)(
}1)1)(,1(),,1(m a x {
),1(),(
ij
ij
iiS i z ejiS i z e
jiS i z ejiS i z e
33
流水作业调度
n个作业 {1,2,…,n}要在由 2台机器 M1和 M2组成的流水线上完成加工。每个作业加工的顺序都是先在 M1上加工，然后在
M2上加工。 M1和 M2加工作业 i所需的时间分别为 ai和 bi。
流水作业调度问题要求确定这 n个作业的最优加工顺序，使得从第一个作业在机器 M1上开始加工，到最后一个作业在机器 M2上加工完成所需的时间最少。
分析：
直观上，一个最优调度应使机器 M1没有空闲时间，且机器
M2的空闲时间最少。在一般情况下，机器 M2上会有机器空闲和作业积压 2种情况。
设全部作业的集合为 N={1,2,…,n}。 S?N是 N的作业子集。在一般情况下，机器 M1开始加工 S中作业时，机器 M2还在加工其他作业，要等时间 t后才可利用。将这种情况下完成
S中作业所需的最短时间记为 T(S,t)。流水作业调度问题的最优值为 T(N,0)。
34
流水作业调度设?是所给 n个流水作业的一个最优调度，它所需的加工时间为
a?(1)+T’。其中 T’是在机器 M2的等待时间为 b?(1)时，安排作业
(2),…,?(n)所需的时间。
记 S=N-{?(1)}，则有 T’=T(S,b?(1))。
证明,事实上，由 T的定义知 T’?T(S,b?(1))。若 T’>T(S,b?(1))，
设?’是作业集 S在机器 M2的等待时间为 b?(1)情况下的一个最优调度。则?(1),?’(2),…,?’(n)是 N的一个调度，且该调度所需的时间为 a?(1)+T(S,b?(1))<a?(1)+T’。这与?是 N的最优调度矛盾。故 T’?T(S,b?(1))。从而 T’=T(S,b?(1))。这就证明了流水作业调度问题具有最优子结构的性质。
由流水作业调度问题的最优子结构性质可知，
)}},{({m i n)0,( 1 iini biNTaNT
} ) }0,m a x {},{({m i n),( iiiSi atbiSTatST
35
Johnson不等式对递归式的深入分析表明，算法可进一步得到简化。
设?是作业集 S在机器 M2的等待时间为 t时的任一最优调度。若
(1)=i,?(2)=j。则由动态规划递归式可得,
T(S,t)=ai+T(S-{i},bi+max{t-ai,0})=ai+aj+T(S-{i,j},tij)
其中，
},,m a x {
}0,,m a x {
}},0,m a x { m a x {
}0,}0,m a x {m a x {
iijiijij
ijijij
ijijij
jiijij
abaataabb
baatabb
baatabb
aatbbt
如果作业 i和 j满足 min{bi,aj}≥ min{bj,ai}，则称作业 i和 j满足 Johnson不等式 。
36
流水作业调度的 Johnson法则交换作业 i和作业 j的加工顺序，得到作业集 S的另一调度，它所需的加工时间为 T’(S,t)=ai+aj+T(S-{i,j},tji)
其中，
当作业 i和 j满足 Johnson不等式时，有由此可见当作业 i和作业 j不满足 Johnson不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度?，使得作业?(i)和?(i+1)满足 Johnson不等式。进一步还可以证明，调度满足 Johnson法则当且仅当对任意 i<j有由此可知,所有满足 Johnson法则的调度均为最优调度。
},,m a x { jjjiijijji abaataabbt
},,m a x { iijiijijij abaataabbt
},,m a x {},,m a x {
},m a x {},m a x {
},m a x {},m a x {
},m a x {},m a x {
jjjiiiji
jjjiiiji
ijjijiji
ijji
abaatabaat
abaaabaa
abaaabaa
abab
},m i n {},m i n { )()()()( ijji abab
37
算法描述流水作业调度问题的 Johnson算法
(1)令
(2)将 N1中作业依 ai的非减序排序；将 N2中作业依 bi的非增序排序；
(3)N1中作业接 N2中作业构成满足 Johnson法则的最优调度。
};|{},|{ 21 iiii baiNbaiN
算法复杂度分析：
算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为 O(nlogn)。所需的空间为 O(n)。
38
0-1背包问题
n
i
ii xv
1
m a x
nix
Cxw
i
n
i
ii
1},1,0{
1
给定 n种物品和一背包。物品 i的重量是 wi，其价值为 vi，背包的容量为 C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
0-1背包问题是一个特殊的整数规划问题。
39
0-1背包问题设所给 0-1背包问题的子问题
n
ik
kk xvm a x
nkix
jxw
k
n
ik
kk
},1,0{
的最优值为 m(i,j)，即 m(i,j)是背包容量为 j，可选择物品为 i，
i+1,…,n时 0-1背包问题的最优值。由 0-1背包问题的最优子结构性质，可以建立计算 m(i,j)的递归式如下。
i
iii
wj
wj
jim
vwjimjimjim
0),1(
}),1(),,1(m a x {),(
n
nn
wj
wjvjnm
00),(
算法复杂度分析：
从 m(i,j)的递归式容易看出，算法需要 O(nc)计算时间。当背包容量 c很大时，算法需要的计算时间较多。
例如，当 c>2n时，算法需要 Ω(n2n)计算时间。
40
算法改进由 m(i,j)的递归式容易证明，在一般情况下，对每一个确定的
i(1≤i≤n)，函数 m(i,j)是关于变量 j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数 m(i,j)由其全部跳跃点惟一确定。如图所示。
对每一个确定的 i(1≤i≤n)，用一个表 p[i]存储函数 m(i,j)的全部跳跃点。表 p[i]可依计算 m(i,j)的递归式递归地由表 p[i+1]计算，
初始时 p[n+1]={(0,0)}。
41
典型 例子 （ 一）
n=3,c=6,w={4,3,2},v={5,2,1}。
x(0,0)
m(4,x)
x
(2,1)
m(4,x-2)+1
x
(0,0) (2,1)
m(3,x)
(3,2)
x
m(3,x-3)+2(5,3)
x
(0,0) (2,1)
m(2,x)
(3,2) (5,3)
x
m(2,x-4)+5
(4,5) (6,6)
(7,7) (9,8)
x
(0,0) (2,1)
m(1,x)
(3,2) (5,3)
(4,5)(6,6)
(7,7) (9,8)
x
(0,0) (2,1)
m(3,x)
x
(0,0) (2,1)
m(2,x)
(3,2) (5,3)
42
算法改进
函数 m(i,j)是由函数 m(i+1,j)与函数 m(i+1,j-wi)+vi作 max运算得到的。因此，函数 m(i,j)的全部跳跃点包含于函数 m(i+1,j)的跳跃点集 p[i+1]与函数 m(i+1,j-wi)+vi的跳跃点集 q[i+1]的并集中。
易知,(s,t)?q[i+1]当且仅当 wi?s?c且 (s-wi,t-vi)?p[i+1]。因此，
容易由 p[i+1]确定跳跃点集 q[i+1]如下
q[i+1]=p[i+1]?(wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))?p[i+1]}
另一方面，设 (a,b)和 (c,d)是 p[i+1]?q[i+1]中的 2个跳跃点，
则当 c?a且 d<b时,(c,d)受控于 (a,b)，从而 (c,d)不是 p[i]中的跳跃点。除受控跳跃点外,p[i+1]?q[i+1]中的其他跳跃点均为 p[i]中的跳跃点。
由此可见，在递归地由表 p[i+1]计算表 p[i]时，可先由 p[i+1]计算出 q[i+1]，然后合并表 p[i+1]和表 q[i+1]，并清除其中的受控跳跃点得到表 p[i]。
43
典型 例子 （ 二）
n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}。
初始时 p[6]={(0,0)},(w5,v5)=(4,6)。因此，
q[6]=p[6]?(w5,v5)={(4,6)}。
p[5]={(0,0),(4,6)}。
q[5]=p[5]?(w4,v4)={(5,4),(9,10)}。从跳跃点集 p[5]与 q[5]的并集
p[5]?q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳跃点 (5,4)受控于跳跃点 (4,6)。将受控跳跃点 (5,4)清除后，得到
p[4]={(0,0),(4,6),(9,10)}
q[4]=p[4]?(6,5)={(6,5),(10,11)}
p[3]={(0,0),(4,6),(9,10),(10,11)}
q[3]=p[3]?(2,3)={(2,3),(6,9)}
p[2]={(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)}
q[2]=p[2]?(2,6)={(2,6),(4,9),(6,12),(8,15)}
p[1]={(0,0),(2,6),(4,9),(6,12),(8,15)}
p[1]的最后的那个跳跃点 (8,15)给出所求的最优值为 m(1,c)=15。
44
算法复杂度分析上述算法的主要计算量在于计算跳跃点集
p[i](1≤i≤n)。由于 q[i+1]=p[i+1]?(wi,vi)，故计算
q[i+1]需要 O(|p[i+1]|)计算时间。合并 p[i+1]和
q[i+1]并清除受控跳跃点也需要 O(|p[i+1]|)计算时间。从跳跃点集 p[i]的定义可以看出,p[i]中的跳跃点相应于 xi,…,x n的 0/1赋值。因此,p[i]中跳跃点个数不超过 2n-i+1。由此可见，算法计算跳跃点集 p[i]所花费的计算时间为从而，改进后算法的计算时间复杂性为 O(2n)。当所给物品的重量 wi(1≤i≤n)是整数时,|p[i]|≤c+1，
(1≤i≤n)。在这种情况下，改进后算法的计算时间复杂性为 O(min{nc,2n})。
nn
i
inn
i
OOipO 22|]1[|
22
45
最优二叉搜索树
什么是二叉搜索树？
（ 1）若它的左子树不空，则左子树上 所有节点的值 均小于 它的根节点的值；
（ 2）若它的右子树不空，则右子树上 所有节点的值 均大于 它的根节点的值；
（ 3 它的左,右子树也分别为二叉排序树
45
12 53
3 37
24
100
61
90
78
在随机的情况下，二叉查找树的平均查找长度和 是等数量级的nlog
46
二叉查找树的期望耗费
查找成功与不成功的概率
二查找树的期望耗费
有 个节点的二叉树的个数为：
穷举搜索法的时间复杂度为指数级
1
1 0
n
i
n
i
ii qp
n
i
iiT
n
i
iiT
n
i
iiT
n
i
iiT
qdpk
qdpk
TE
01
01
)(d e p t h)(d e p t h1
)1)(d e p t h()1)(d e p t h(
) inc o s t s e a r c h(
n )/4( 2/3nn?
0d 1d
2d 3d
4d
5d
1k
2k
3k
4k
5k
47
二叉查找树的期望耗费示例
2,8 0 T o t a l
0,4 0 0,1 0 3
0,2 0 0,0 5 3
0,2 0 0,0 5 3
0,2 0 0,0 5 3
0,3 0 0,1 0 2
0,1 5 0,0 5 2
0,6 0 0,2 0 2
0,2 0 0,1 0 1
0,1 5 0,0 5 2
0,1 0 0,1 0 0
0,3 0 0,1 5 1
onc o n t r i b u t iy p r o b a b i l i t d e p t h n o d e
5
4
3
2
1
0
5
4
3
2
1
d
d
d
d
d
d
k
k
k
k
k
0d 1d
2d 3d 4d 5d
1k
2k
3k
4k
5k
48
最优二叉搜索树最优二叉搜索树 Tij的平均路长为 pij，则所求的最优值为 p1,n。
由最优二叉搜索树问题的最优子结构性质可建立计算 pij的递归式如下记 wi,jpi,j为 m(i,j)，则 m(1,n)=w1,np1,n=p1,n为所求的最优值。计算 m(i,j)的递归式为注意到，
可以得到 O(n2)的算法
}{m in,1,11,1,,,,jkjkkikijkijijiji pwpwwpw
niiim
jijkmkimwjim
jkiji
1,0)1,(
) },,1()1,({m i n),(,
)},1()1,({m in)},1()1,({m in ]][1[]1][[ jkmkimjkmkim jiskjisjki
第 3章 动态规划
2
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题
n
T(n/2) T(n/2) T(n/2) T(n/2)
T(n) =
3
算法总体思想
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题
n
T(n/2) T(n/2) T(n/2) T(n/2)
T(n) =
4
但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。
算法总体思想
nT(n) =
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
n/2
T(n/4)T(n/4)T(n/4)T(n/4)
5
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。
算法总体思想
n=
n/2
T(n/4) T(n/4) T(n/4) T(n/4)
n/2 n/2
T(n/4)T(n/4)
n/2
T(n/4) T(n/4) T(n/4)T(n/4) T(n/4)
T(n)Those who cannot remember the past
are doomed to repeat it,
-----George Santayana,
The life of Reason,
Book I,Introduction and
Reason in Common
Sense (1905)
6
动态规划基本步骤
找出最优解的性质，并刻划其结构特征。
递归地定义最优值。
以自底向上的方式计算出最优值。
根据计算最优值时得到的信息，构造最优解。
7
完全加括号的矩阵连乘积
（ 1）单个矩阵是完全加括号的；
（ 2）矩阵连乘积 是完全加括号的，则 可表示为 2个完全加括号的矩阵连乘积 和的乘积并加括号，即
A A
B C
)(BCA?
DCBA,,,
1050A 4010B 3040C 530D
)))((( DBCA
)))( ( ( DCAB )))((( DBCA
) ) )((( CDBA )))((( CDAB
16000,10500,36000,87500,34500
完全加括号的矩阵连乘积可递归地定义为：
设有四个矩阵,它们的维数分别是：
总共有五中完全加括号的方式
8
矩阵连乘问题
给定 n个矩阵,其中 与 是可乘的,。考察这 n个矩阵的连乘积
由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。
若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用 2个矩阵相乘的标准算法计算出矩阵连乘积
},.,,,,{ 21 nAAA iA 1?iA
1,.,,,2,1 ni
nAAA,..21
9
矩阵连乘问题给定 n个矩阵｛ A1,A2,…,An｝，其中 Ai与 Ai+1是可乘的，
i=1,2,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
穷举法,列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。
算法复杂度分析：
对于 n个矩阵的连乘积，设其不同的计算次序为 P(n)。
由于每种加括号方式都可以分解为两个子矩阵的加括号问题：
(A1...Ak)(Ak+1…An)可以得到关于 P(n)的递推式如下：
)/4()(11)()(
1
)( 2/31
1
nnPnnknPkPnP nn
k
10
矩阵连乘问题
穷举法
动态规划将矩阵连乘积 简记为 A[i:j],这里 i≤j
jii AAA,..1?
考察计算 A[i:j]的最优计算次序。设这个计算次序在矩阵
Ak和 Ak+1之间将矩阵链断开,i≤k<j，则其相应完全加括号方式为
).,,)(.,,( 211 jkkkii AAAAAA
计算量,A[i:k]的计算量加上 A[k+1:j]的计算量，再加上
A[i:k]和 A[k+1:j]相乘的计算量
11
分析最优解的结构
特征：计算 A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和 A[k+1:j]的次序也是最优的。
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为 最优子结构性质 。
问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。
12
建立递归关系
设计算 A[i:j],1≤i≤j≤n，所需要的最少数乘次数
m[i,j]，则原问题的最优值为 m[1,n]
当 i=j时,A[i:j]=Ai，因此,m[i,i]=0,i=1,2,…,n
当 i<j时，
可以递归地定义 m[i,j]为：
jki pppjkmkimjim 1],1[],[],[
这里 的维数为
iA ii pp1
jipppjkmkim
ji
jim
jki }],1[],[{m in
0
],[
1jki
的位臵只有 种 可能k ij?
13
计算最优值
对于 1≤i≤j≤n不同的有序对 (i,j)对应于不同的子问题。
因此，不同子问题的个数最多只有
由此可见，在递归计算时,许多子问题被重复计算多次 。这也是该问题可用动态规划算法求解的又一显著特征。
用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法
)(2 2nnn
14
用动态规划法求最优解
public static void matrixChain(int [] p,int [][] m,int [][] s)
{
int n=p.length-1;
for (int i = 1; i <= n; i++) m[i][i] = 0;
for (int r = 2; r <= n; r++)
for (int i = 1; i <= n - r+1; i++) {
int j=i+r-1;
m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];
s[i][j] = i;
for (int k = i+1; k < j; k++) {
int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (t < m[i][j]) {
m[i][j] = t;
s[i][j] = k;}
}
}
}
A1 A2 A3 A4 A5 A6
30?35 35?15 15?5 5?10 10?20 20?25
1 1 3 7 520103504 3 7 5]5][5[]4][2[
7 1 2 5205351 0 0 02 6 2 5]5][4[]3][2[
1 3 0 0 02015352 5 0 00]5][3[]2][2[
m i n]5][2[
541
531
521
pppmm
pppmm
pppmm
m
算法复杂度分析：
算法 matrixChain的主要计算量取决于算法中对 r，
i和 k的 3重循环。循环体内的计算量为 O(1)，而 3重循环的总次数为 O(n3)。因此算法的计算时间上界为 O(n3)。算法所占用的空间显然为 O(n2)。
15
动态规划算法的基本要素一、最优子结构
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为 最优子结构性质 。
在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
注意：同一个问题可以有多种 方式刻划 它 的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）
16
二、重叠子问题
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。 这种性质称为 子问题的重叠性质 。
动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。
17
三、备忘录方法
备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。
m?0
private static int lookupChain(int i,int j)
{
if (m[i][j] > 0) return m[i][j];
if (i == j) return 0;
int u = lookupChain(i+1,j) + p[i-1]*p[i]*p[j];
s[i][j] = i;
for (int k = i+1; k < j; k++) {
int t = lookupChain(i,k) + lookupChain(k+1,j) + p[i-1]*p[k]*p[j];
if (t < u) {
u = t; s[i][j] = k;}
}
m[i][j] = u;
return u;
}
18
最长公共子序列
若给定序列 X={x1,x2,…,x m}，则另一序列 Z={z1,z2,…,z k}，
是 X的子序列是指存在一个严格递增下标序列 {i1,i2,…,i k}
使得对于所有 j=1,2,…,k 有,zj=xij。例如，序列 Z={B,C，
D,B}是序列 X={A,B,C,B,D,A,B}的子序列，
相应的递增下标序列为 {2,3,5,7}。
给定 2个序列 X和 Y，当另一序列 Z既是 X的子序列又是 Y
的子序列时，称 Z是序列 X和 Y的 公共子序列 。
给定 2个序列 X={x1,x2,…,xm}和 Y={y1,y2,…,yn}，找出 X
和 Y的最长公共子序列。
19
最长公共子序列的结构设序列 X={x1,x2,…,x m}和 Y={y1,y2,…,y n}的最长公共子序列为
Z={z1,z2,…,z k},则
(1)若 xm=yn，则 zk=xm=yn，且 zk-1是 xm-1和 yn-1的最长公共子序列。
(2)若 xm≠yn且 zk≠xm，则 Z是 xm-1和 Y的最长公共子序列。
(3)若 xm≠yn且 zk≠yn，则 Z是 X和 yn-1的最长公共子序列。
由此可见,2个序列的最长公共子序列包含了这 2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有 最优子结构性质 。
20
子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用 c[i][j]记录序列和的最长公共子序列的长度。
其中,Xi={x1,x2,…,x i}； Yj={y1,y2,…,y j}。当 i=0或 j=0时，空序列是 Xi和 Yj的最长公共子序列。故此时 C[i][j]=0。其他情况下，
由最优子结构性质可建立递归关系如下：
ji
ji
yxji
yxji
ji
jicjic
jicjic;0,;0,
0,0
]}][1[],1][[m a x {
1]1][1[
0
]][[
21
计算最优值由于在所考虑的子问题空间中，总共有 θ(mn)个不同的子问题，
因此，用动态规划算法自底向上地计算最优值能提高算法的效率。
Algorithm lcsLength(x,y,b)
1,m?x.length-1;
2,n?y.length-1;
3,c[i][0]=0; c[0][i]=0;
4,for (int i = 1; i <= m; i++)
5,for (int j = 1; j <= n; j++)
6,if (x[i]==y[j])
7,c[i][j]=c[i-1][j-1]+1;
8,b[i][j]=1;
9,else if (c[i-1][j]>=c[i][j-1])
10,c[i][j]=c[i-1][j];
11,b[i][j]=2;
12,else
13,c[i][j]=c[i][j-1];
14,b[i][j]=3;
构造最长公共子序列
Algorithm lcs(int i,int j,char [] x,int [][] b)
{
if (i ==0 || j==0) return;
if (b[i][j]== 1){
lcs(i-1,j-1,x,b);
System.out.print(x[i]);
}
else if (b[i][j]== 2) lcs(i-1,j,x,b);
else lcs(i,j-1,x,b);
}
22
算法的改进
在算法 lcsLength和 lcs中，可进一步将数组 b省去。
事实上，数组元素 c[i][j]的值仅由 c[i-1][j-1],c[i-1][j]和
c[i][j-1]这 3个数组元素的值所确定。对于给定的数组元素 c[i][j]，可以不借助于数组 b而仅借助于 c本身在时间内确定 c[i][j]的值是由 c[i-1][j-1],c[i-1][j]和 c[i][j-1]中哪一个值所确定的。
如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算 c[i][j]时，只用到数组 c的第 i行和第 i-1行。因此，用 2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至 O(min(m,n))。
23
凸多边形最优三角剖分
用多边形顶点的逆时针序列表示凸多边形，即 P={v0,v1,…,v n-1}
表示具有 n条边的凸多边形。
若 vi与 vj是多边形上不相邻的 2个顶点，则线段 vivj称为多边形的一条弦。弦将多边形分割成 2个多边形 {vi,vi+1,…,v j}和 {vj,vj+1,…v i}。
多边形的三角剖分 是将多边形分割成互不相交的三角形的弦的集合 T。
给定凸多边形 P，以及定义在由多边形的边和弦组成的三角形上的权函数 w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。
24
三角剖分的结构及其相关问题
一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积
((A1(A2A3))(A4(A5A6)))所相应的语法树如图 (a)所示。
凸多边形 {v0,v1,…v n-1}的三角剖分也可以用语法树表示。例如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树表示。
矩阵连乘积中的每个矩阵 Ai对应于凸 (n+1)边形中的一条边
vi-1vi。三角剖分中的一条弦 vivj,i<j，对应于矩阵连乘积
A[i+1:j]。
25
最优子结构性质
凸多边形的最优三角剖分问题有最优子结构性质。
事实上，若凸 (n+1)边形 P={v0,v1,…,v n-1}的最优三角剖分 T包含三角形 v0vkvn,1≤k≤n-1，则 T
的权为 3个部分权的和：三角形 v0vkvn的权，
子多边形 {v0,v1,…,v k}和 {vk,vk+1,…,v n}的权之和。
可以断言，由 T所确定的这 2个子多边形的三角剖分也是最优的。因为若有 {v0,v1,…,v k}或
{vk,vk+1,…,v n}的更小权的三角剖分将导致 T不是最优三角剖分的矛盾。
26
最优三角剖分的递归结构
定义 t[i][j],1≤i<j≤n为凸子多边形 {vi-1,vi,…,vj} 的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形 {vi-1,vi}具有权值 0。据此定义，要计算的凸 (n+1)边形 P的最优权值为 t[1][n]。
t[i][j]的值可以利用最优子结构性质递归地计算。当 j-i≥1时，凸子多边形至少有 3个顶点。由最优子结构性质,t[i][j]的值应为
t[i][k]的值加上 t[k+1][j]的值，再加上三角形 vi-1vkvj的权值，其中
i≤k≤j-1。由于在计算时还不知道 k的确切位臵，而 k的所有可能位臵只有 j-i个，因此可以在这 j-i个位臵中选出使 t[i][j]值达到最小的位臵。由此,t[i][j]可递归地定义为：
ji
ji
vvvwjktkitjit jki
jki
)}(]][1[]][[{m in
0
]][[
1
27
多边形游戏多边形游戏是一个单人玩的游戏，开始时有一个由 n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符,+”或,*”。所有边依次用整数从 1到 n编号。
游戏第 1步，将一条边删除。
随后 n-1步按以下方式操作：
(1)选择一条边 E以及由 E连接着的 2个顶点 V1和 V2；
(2)用一个新的顶点取代边 E以及由 E连接着的 2个顶点 V1和 V2。
将由顶点 V1和 V2的整数值通过边 E上的运算得到的结果赋予新顶点。
最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。
问题,对于给定的多边形，计算最高得分。
28
最优子结构性质
在所给多边形中，从顶点 i(1≤i≤n)开始，长度为 j(链中有 j个顶点 )
的顺时针链 p(i,j) 可表示为 v[i],op[i+1],…,v[i+j-1]。
如果这条链的最后一次合并运算在 op[i+s]处发生 (1≤s≤j-1)，则可在 op[i+s]处将链分割为 2个子链 p(i,s)和 p(i+s,j-s)。
设 m1是对子链 p(i,s)的任意一种合并方式得到的值，而 a和 b
分别是在所有可能的合并中得到的最小值和最大值。 m2是
p(i+s,j-s)的任意一种合并方式得到的值，而 c和 d分别是在所有可能的合并中得到的最小值和最大值。依此定义有 a≤m1≤b，
c≤m2≤d
(1)当 op[i+s]='+'时，显然有 a+c≤m≤b+d
(2)当 op[i+s]='*'时，有 min{ac,ad,bc,bd}≤m≤max{ac,ad，
bc,bd}
换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。
29
图像压缩图像的变位压缩存储格式将所给的象素点序列
{p1,p2,…,pn},0≤pi≤255 分割成 m个连续段 S1,S2,…,Sm 。第 i
个象素段 Si中 (1≤i≤m)，有 l[i]个象素,且该段中每个象素都只用
b[i]位表示。设 则第 i个象素段 Si为设,则 hi?b[i]?8。因此需要用 3位表示 b[i],
如果限制 1?l[i]?255，则需要用 8位表示 l[i]。因此，第 i个象素段所需的存储空间为 l[i]*b[i]+11位。按此格式存储象素序列
{p1,p2,…,pn},需要 位的存储空间。
图像压缩问题要求确定象素序列 {p1,p2,…,pn}的最优分段，
使得依此分段所需的存储空间最少。每个分段的长度不超过
256位。
1
1
][][ i
k
klit
1m a xlo g ][][1][ kilitkiti ph
mibilm
i
11][*][
1
30
图像压缩设 l[i],b[i]，是 {p1,p2,…,pn} 的最优分段。显而易见,l[1],b[1]
是 {p1,…,p l[1]}的最优分段，且 l[i],b[i]，是 {pl[1]+1,…,p n}的最优分段。即图像压缩问题满足最优子结构性质。
设 s[i],1≤i≤n，是象素序列 {p1,…,pn} 的最优分段所需的存储位数。由最优子结构性质易知：
其中
11)},1m a x (b*][{m in][ }256,m i n {1 ikikkisis ik
1}{m a xlo g),b m a x ( kjki pji
算法复杂度分析：
由于算法 compress中对 k的循环次数不超这 256，故对每一个确定的 i，可在时间 O(1)内完成的计算。因此整个算法所需的计算时间为 O(n)。
31
电路布线在一块电路板的上、下 2端分别有 n个接线柱。根据电路设计，
要求用导线 (i,π(i))将上端接线柱与下端接线柱相连，如图所示。
其中 π(i)是 {1,2,…,n} 的一个排列。导线 (i,π(i))称为该电路板上的第 i条连线。对于任何 1≤i<j≤n，第 i条连线和第 j条连线相交的充分且必要的条件是 π(i)>π(j)。
电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集
Nets={(i,π(i)),1≤i≤n}的最大不相交子集。
32
记 。 N(i,j)的最大不相交子集为 MNS(i,j)。 Size(i,j)=|MNS(i,j)|。
(1)当 i=1时，
(2)当 i>1时，
2.1 j<π(i)。此时,。故在这种情况下，
N(i,j)=N(i-1,j)，从而 Size(i,j)=Size(i-1,j)。
2.2 j≥π(i),(i,π(i))∈ MNS(i,j) 。 则对任意 (t,π(t)) ∈ MNS(i,j)有
t<i且 π(t)<π(i)。在这种情况下 MNS(i,j)-{(i,π(i))}是 N(i-
1,π(i)-1)的最大不相交子集。
2.3 若,则对任意 (t,π(t)) ∈ MNS(i,j)有
t<i。从而 。因此,Size(i,j)≤Size(i-1,j)。
另一方面,故又有 Size(i,j)≥Size(i-1,j)，
从而 Size(i,j)=Size(i-1,j)。
电路布线
})(,,))(,(|{),( jtitN e t stttjiN
)1() ) }1(,1{(
)1(),1(),1(
j
jjNjM N S
),())(,( jiNii
),())(,( jiNii
),1(),( jiNjiM N S
),(),1( jiNjiM N S
(1)当 i=1时
(2)当 i>1时
)1(1
)1(0),1(
j
jjS iz e
)(
)(
}1)1)(,1(),,1(m a x {
),1(),(
ij
ij
iiS i z ejiS i z e
jiS i z ejiS i z e
33
流水作业调度
n个作业 {1,2,…,n}要在由 2台机器 M1和 M2组成的流水线上完成加工。每个作业加工的顺序都是先在 M1上加工，然后在
M2上加工。 M1和 M2加工作业 i所需的时间分别为 ai和 bi。
流水作业调度问题要求确定这 n个作业的最优加工顺序，使得从第一个作业在机器 M1上开始加工，到最后一个作业在机器 M2上加工完成所需的时间最少。
分析：
直观上，一个最优调度应使机器 M1没有空闲时间，且机器
M2的空闲时间最少。在一般情况下，机器 M2上会有机器空闲和作业积压 2种情况。
设全部作业的集合为 N={1,2,…,n}。 S?N是 N的作业子集。在一般情况下，机器 M1开始加工 S中作业时，机器 M2还在加工其他作业，要等时间 t后才可利用。将这种情况下完成
S中作业所需的最短时间记为 T(S,t)。流水作业调度问题的最优值为 T(N,0)。
34
流水作业调度设?是所给 n个流水作业的一个最优调度，它所需的加工时间为
a?(1)+T’。其中 T’是在机器 M2的等待时间为 b?(1)时，安排作业
(2),…,?(n)所需的时间。
记 S=N-{?(1)}，则有 T’=T(S,b?(1))。
证明,事实上，由 T的定义知 T’?T(S,b?(1))。若 T’>T(S,b?(1))，
设?’是作业集 S在机器 M2的等待时间为 b?(1)情况下的一个最优调度。则?(1),?’(2),…,?’(n)是 N的一个调度，且该调度所需的时间为 a?(1)+T(S,b?(1))<a?(1)+T’。这与?是 N的最优调度矛盾。故 T’?T(S,b?(1))。从而 T’=T(S,b?(1))。这就证明了流水作业调度问题具有最优子结构的性质。
由流水作业调度问题的最优子结构性质可知，
)}},{({m i n)0,( 1 iini biNTaNT
} ) }0,m a x {},{({m i n),( iiiSi atbiSTatST
35
Johnson不等式对递归式的深入分析表明，算法可进一步得到简化。
设?是作业集 S在机器 M2的等待时间为 t时的任一最优调度。若
(1)=i,?(2)=j。则由动态规划递归式可得,
T(S,t)=ai+T(S-{i},bi+max{t-ai,0})=ai+aj+T(S-{i,j},tij)
其中，
},,m a x {
}0,,m a x {
}},0,m a x { m a x {
}0,}0,m a x {m a x {
iijiijij
ijijij
ijijij
jiijij
abaataabb
baatabb
baatabb
aatbbt
如果作业 i和 j满足 min{bi,aj}≥ min{bj,ai}，则称作业 i和 j满足 Johnson不等式 。
36
流水作业调度的 Johnson法则交换作业 i和作业 j的加工顺序，得到作业集 S的另一调度，它所需的加工时间为 T’(S,t)=ai+aj+T(S-{i,j},tji)
其中，
当作业 i和 j满足 Johnson不等式时，有由此可见当作业 i和作业 j不满足 Johnson不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度?，使得作业?(i)和?(i+1)满足 Johnson不等式。进一步还可以证明，调度满足 Johnson法则当且仅当对任意 i<j有由此可知,所有满足 Johnson法则的调度均为最优调度。
},,m a x { jjjiijijji abaataabbt
},,m a x { iijiijijij abaataabbt
},,m a x {},,m a x {
},m a x {},m a x {
},m a x {},m a x {
},m a x {},m a x {
jjjiiiji
jjjiiiji
ijjijiji
ijji
abaatabaat
abaaabaa
abaaabaa
abab
},m i n {},m i n { )()()()( ijji abab
37
算法描述流水作业调度问题的 Johnson算法
(1)令
(2)将 N1中作业依 ai的非减序排序；将 N2中作业依 bi的非增序排序；
(3)N1中作业接 N2中作业构成满足 Johnson法则的最优调度。
};|{},|{ 21 iiii baiNbaiN
算法复杂度分析：
算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为 O(nlogn)。所需的空间为 O(n)。
38
0-1背包问题
n
i
ii xv
1
m a x
nix
Cxw
i
n
i
ii
1},1,0{
1
给定 n种物品和一背包。物品 i的重量是 wi，其价值为 vi，背包的容量为 C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
0-1背包问题是一个特殊的整数规划问题。
39
0-1背包问题设所给 0-1背包问题的子问题
n
ik
kk xvm a x
nkix
jxw
k
n
ik
kk
},1,0{
的最优值为 m(i,j)，即 m(i,j)是背包容量为 j，可选择物品为 i，
i+1,…,n时 0-1背包问题的最优值。由 0-1背包问题的最优子结构性质，可以建立计算 m(i,j)的递归式如下。
i
iii
wj
wj
jim
vwjimjimjim
0),1(
}),1(),,1(m a x {),(
n
nn
wj
wjvjnm
00),(
算法复杂度分析：
从 m(i,j)的递归式容易看出，算法需要 O(nc)计算时间。当背包容量 c很大时，算法需要的计算时间较多。
例如，当 c>2n时，算法需要 Ω(n2n)计算时间。
40
算法改进由 m(i,j)的递归式容易证明，在一般情况下，对每一个确定的
i(1≤i≤n)，函数 m(i,j)是关于变量 j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数 m(i,j)由其全部跳跃点惟一确定。如图所示。
对每一个确定的 i(1≤i≤n)，用一个表 p[i]存储函数 m(i,j)的全部跳跃点。表 p[i]可依计算 m(i,j)的递归式递归地由表 p[i+1]计算，
初始时 p[n+1]={(0,0)}。
41
典型 例子 （ 一）
n=3,c=6,w={4,3,2},v={5,2,1}。
x(0,0)
m(4,x)
x
(2,1)
m(4,x-2)+1
x
(0,0) (2,1)
m(3,x)
(3,2)
x
m(3,x-3)+2(5,3)
x
(0,0) (2,1)
m(2,x)
(3,2) (5,3)
x
m(2,x-4)+5
(4,5) (6,6)
(7,7) (9,8)
x
(0,0) (2,1)
m(1,x)
(3,2) (5,3)
(4,5)(6,6)
(7,7) (9,8)
x
(0,0) (2,1)
m(3,x)
x
(0,0) (2,1)
m(2,x)
(3,2) (5,3)
42
算法改进
函数 m(i,j)是由函数 m(i+1,j)与函数 m(i+1,j-wi)+vi作 max运算得到的。因此，函数 m(i,j)的全部跳跃点包含于函数 m(i+1,j)的跳跃点集 p[i+1]与函数 m(i+1,j-wi)+vi的跳跃点集 q[i+1]的并集中。
易知,(s,t)?q[i+1]当且仅当 wi?s?c且 (s-wi,t-vi)?p[i+1]。因此，
容易由 p[i+1]确定跳跃点集 q[i+1]如下
q[i+1]=p[i+1]?(wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))?p[i+1]}
另一方面，设 (a,b)和 (c,d)是 p[i+1]?q[i+1]中的 2个跳跃点，
则当 c?a且 d<b时,(c,d)受控于 (a,b)，从而 (c,d)不是 p[i]中的跳跃点。除受控跳跃点外,p[i+1]?q[i+1]中的其他跳跃点均为 p[i]中的跳跃点。
由此可见，在递归地由表 p[i+1]计算表 p[i]时，可先由 p[i+1]计算出 q[i+1]，然后合并表 p[i+1]和表 q[i+1]，并清除其中的受控跳跃点得到表 p[i]。
43
典型 例子 （ 二）
n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}。
初始时 p[6]={(0,0)},(w5,v5)=(4,6)。因此，
q[6]=p[6]?(w5,v5)={(4,6)}。
p[5]={(0,0),(4,6)}。
q[5]=p[5]?(w4,v4)={(5,4),(9,10)}。从跳跃点集 p[5]与 q[5]的并集
p[5]?q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳跃点 (5,4)受控于跳跃点 (4,6)。将受控跳跃点 (5,4)清除后，得到
p[4]={(0,0),(4,6),(9,10)}
q[4]=p[4]?(6,5)={(6,5),(10,11)}
p[3]={(0,0),(4,6),(9,10),(10,11)}
q[3]=p[3]?(2,3)={(2,3),(6,9)}
p[2]={(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)}
q[2]=p[2]?(2,6)={(2,6),(4,9),(6,12),(8,15)}
p[1]={(0,0),(2,6),(4,9),(6,12),(8,15)}
p[1]的最后的那个跳跃点 (8,15)给出所求的最优值为 m(1,c)=15。
44
算法复杂度分析上述算法的主要计算量在于计算跳跃点集
p[i](1≤i≤n)。由于 q[i+1]=p[i+1]?(wi,vi)，故计算
q[i+1]需要 O(|p[i+1]|)计算时间。合并 p[i+1]和
q[i+1]并清除受控跳跃点也需要 O(|p[i+1]|)计算时间。从跳跃点集 p[i]的定义可以看出,p[i]中的跳跃点相应于 xi,…,x n的 0/1赋值。因此,p[i]中跳跃点个数不超过 2n-i+1。由此可见，算法计算跳跃点集 p[i]所花费的计算时间为从而，改进后算法的计算时间复杂性为 O(2n)。当所给物品的重量 wi(1≤i≤n)是整数时,|p[i]|≤c+1，
(1≤i≤n)。在这种情况下，改进后算法的计算时间复杂性为 O(min{nc,2n})。
nn
i
inn
i
OOipO 22|]1[|
22
45
最优二叉搜索树
什么是二叉搜索树？
（ 1）若它的左子树不空，则左子树上 所有节点的值 均小于 它的根节点的值；
（ 2）若它的右子树不空，则右子树上 所有节点的值 均大于 它的根节点的值；
（ 3 它的左,右子树也分别为二叉排序树
45
12 53
3 37
24
100
61
90
78
在随机的情况下，二叉查找树的平均查找长度和 是等数量级的nlog
46
二叉查找树的期望耗费
查找成功与不成功的概率
二查找树的期望耗费
有 个节点的二叉树的个数为：
穷举搜索法的时间复杂度为指数级
1
1 0
n
i
n
i
ii qp
n
i
iiT
n
i
iiT
n
i
iiT
n
i
iiT
qdpk
qdpk
TE
01
01
)(d e p t h)(d e p t h1
)1)(d e p t h()1)(d e p t h(
) inc o s t s e a r c h(
n )/4( 2/3nn?
0d 1d
2d 3d
4d
5d
1k
2k
3k
4k
5k
47
二叉查找树的期望耗费示例
2,8 0 T o t a l
0,4 0 0,1 0 3
0,2 0 0,0 5 3
0,2 0 0,0 5 3
0,2 0 0,0 5 3
0,3 0 0,1 0 2
0,1 5 0,0 5 2
0,6 0 0,2 0 2
0,2 0 0,1 0 1
0,1 5 0,0 5 2
0,1 0 0,1 0 0
0,3 0 0,1 5 1
onc o n t r i b u t iy p r o b a b i l i t d e p t h n o d e
5
4
3
2
1
0
5
4
3
2
1
d
d
d
d
d
d
k
k
k
k
k
0d 1d
2d 3d 4d 5d
1k
2k
3k
4k
5k
48
最优二叉搜索树最优二叉搜索树 Tij的平均路长为 pij，则所求的最优值为 p1,n。
由最优二叉搜索树问题的最优子结构性质可建立计算 pij的递归式如下记 wi,jpi,j为 m(i,j)，则 m(1,n)=w1,np1,n=p1,n为所求的最优值。计算 m(i,j)的递归式为注意到，
可以得到 O(n2)的算法
}{m in,1,11,1,,,,jkjkkikijkijijiji pwpwwpw
niiim
jijkmkimwjim
jkiji
1,0)1,(
) },,1()1,({m i n),(,
)},1()1,({m in)},1()1,({m in ]][1[]1][[ jkmkimjkmkim jiskjisjki
