文档介绍：1
第7章动态规划
本章我们学****一种强有力的算法设计技术－动态规划，该技术被广泛用于组合优化问题。使用该技术的算法并不像分治策略那样递归地调用自身，动态规划使用自底向上的方式，将中间的运算结果保存以备后面使用的方式来求J1tom
[i,j]JL[i-1,j-1]+1
ij
10．ElseL[i,j]Jmax{L[i,j-1],L[i-1,j]}
11．Endif
12．Endfor
13．Endfor
14．ReturnL[n,m]
我们使用一个(n+1)X(m+1)的表格来进行计算。只需要逐行填满表格,问题就得到解决。例：A=zxyxyz,B=xyyzx
7
首先，将零行、零列填0。…
时间复杂度为T(n)二O(nm)
假定我们要将3个矩阵相乘MMM，3个矩阵的维数分别为
123
2x10,10x2,2x10。如果我们依次相乘，那么，所需要的乘法次数为：
2x10x2+2x2x10=80
假如，我们使用这样的相乘次序M(MM)，那么需要的乘法次数
123
为：10x2x10+2x10x10二400
也就是说，多个矩阵相乘时，乘的顺序不同，时间复杂性大不相
同。那么如何找到最佳的相乘次序(最少的乘法次数)呢？当然，我们可以使用枚举的方法来求解。
定义f(n)是n个矩阵MMM…M连乘所有可能的组合，下面我
123n
们想办法求出f(n)的解析解。
(MMM…M)x(M…M)，那么MMM…M有f(k)种组合方式。
123kk+1n123k
(M…M)共有f(n-k)种组合方式。那么，f(n)=*f(k)f(n-k)。又因k+1n
k=1
为f(1)=1,f⑵=1,f⑶=2。因此有f(n)=nC2n-2。
Stirling公式：n!2^7(n,])n
9
所以f(n)=(2n-2)!沁上，也就是说f(n)=0(兰)，时间复杂n((n-1)!)“
度为指数形式。下面我们使用动态规划的方法来求解：
先来观察一下对于其中任意相邻的两个矩阵，前
123n
一矩阵的列数必定等于后一矩阵的行数。为此，我们定义
r1,r2,仝…r,r1，其中[，£分别表示矩阵M(1<i<n)的行数和列
123nn+1LL十1i
数。令M=MM…M，设C[i,j]为计算M的最优乘法次数。
ijii1jij
那么M可以按照如下方式来计算：Mk_1=MMi+1…Mk_1
i,j
M=MMM这里1<i<j。
k,jkk1j
而MM的乘法次数为rrr。因此，C[i,j]可以递归的表示为：
i,k-1k,jikj+1
C[i,j]=min{C[i,k-1]+C[k,j]+rrr}。
1<k<nikj1
同样，如果我们直接使用递归的方法来求解，那么其中会存在大
量的重复调用，增加了时间复杂性。下面我们使用动态规划来求解之：
输入:n个矩阵的链的维数对应于正整数数组r[1...n+1],其中r[1...n]
是n个矩阵的行数，r[n+1]是m的列数。
n
输出：n个矩阵相乘的数量乘法的最小次数
foriJ1ton
C[i,i]J0
endfor
fordJ1ton-1
foriJ1ton-d
jJi+d
comment:下列三行计算C[i,j]
C[i,j]Jg
10
forkJi+1toj
C[i,j]=min{CmjMC[i，k—1]+C[k,j]+rrr}。
1<k<nikj1
endfor
endfor
endfor
returnC[1..n]
算法的分析：
T(n)=£生"dp=®(n3)
d=1i=1k=1
例：M1：5*10；M2：10*4；M3：4*6；M4：6*10；M5：10*2
C[1,1]=0
C[l,2]=
C[1,3]=
C[l,4]=
C[l,5]=
C[2,2]=0
C[2,3]=
C[2,4]=
C[2,5]=
C[3,3]=0
C[3,4]=
C[3,5]=
C[4,4]=0
C[4,5]=
C[5,5]=0
动态规划的发展及研究内容
动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著DynamicProgramming这是该领域的第一本著作