算法设计第三章 动态规划

教学目标动态规划的原理理解多阶段决策过程及特点理解动态规划的术语熟悉最优值函数、最优值基本方程最优性定理和基本方程充分理解最优性定理熟记、理解两种动态规划的基本方程掌握动态规划求解的基本步骤动态规划特点、条件和步骤熟记动态规划的适用条件熟记逆序、正序递推法的可归纳为以下四个步骤第一页，共八十三页，2022年，8月28日1动态规划的原理(多阶段决策问题)

多阶段决策过程多阶段决策过程是活动过程可按时间或空间顺序分解成若干相互独立、相互联系的阶段，在每个阶段的状态下做出决策，整个过程的决策构成一个决策序列，则称多阶段决策过程为序贯决策过程。称问题为多阶段决策问题。状态1状态2状态3状态4状态5决策2决策3决策4决策1多阶段决策问题的特点过程可分为若干个相互联系的阶段；每一阶段都对应着一组可供选择的决策；每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。第二页，共八十三页，2022年，8月28日2动态规划的原理(单源最短路径)第1阶段第2阶段第3阶段第4阶段状态1状态2状态4状态5状态3决策1决策2决策4决策3动态规划把多阶段过程的问题转化为一系列单阶段的问题，逐个阶段求解的最优化数学方法。第三页，共八十三页，2022年，8月28日3动态规划的原理动态规划的术语阶段：将过程划分为k个阶段，1k

n。状态：第k个阶段的状态变量为

。为初态，为终态。状态集合：

允许的取值范围，记为

。决策：表示第k阶段状态的决策变量，简记为。允许决策集合：允许的取值范围。策略：一个按顺序排列的决策序列，记。状态转移方程：从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律，记为。子策略：称决策序列为k子过程策略。简称子策略，记为第四页，共八十三页，2022年，8月28日4动态规划的原理

当k=1时，成为全过程的一个策略，简称策略，简记为。阶段指标函数：指第k阶段从状态出发，采取决策时的效益，用表示。过程指标函数：从第k阶段的状态出发，采取子策略 获得最佳效益记为。最优性函数：若采用最优子策略，从第k阶段的出发获得最佳效益 第五页，共八十三页，2022年，8月28日5动态规划的原理其中opt可根据具体情况取max或min。是可分函数，具有可加性或可乘性最优性基本方程第六页，共八十三页，2022年，8月28日6最优性定理和基本方程

两种方式的动态规划初始状态出发到终止状态的正序寻优；从终止状态出发到初始状态逆序寻优。

动态规划求解的基本步骤

1.划分阶段2.定义决策变量，确定决策集合是最优策略的充要条件是：对任一k(1kn),当初状态为s1时,有即在最优策略，必然包含最优子策略。换句话说，问题的最优解必包含子问题的最优解。最优性定理第七页，共八十三页，2022年，8月28日7最优性定理和基本方程式中opt可根据题意取max或min。正序基本方程：此为逐段递推计算的依据，一般为：式中opt可根据题意取max或min。逆序基本方程：此为逐段递推计算的依据，一般为：3.确定阶段指标函数4.建立状态转移方程5.确定过程指标函数6.建立递归方程第八页，共八十三页，2022年，8月28日8动态规划实例计算逆序递推计算方法(单源最短路径)

用表示在第k阶段由初始状态到下一阶段的状态的距离。用表示从第k阶段的状态到终点E的最短距离。1．阶段k=4第4阶段有两个初始状态和。若全过程最短路径经过状态，则有=4；若全过程最短路径经过状态，则有=3。2．阶段k=3假设全过程最短路径在第3阶段经过状态，若由，则有。

3．，及其它阶段的计算类似。，最短路径为。第九页，共八十三页，2022年，8月28日9动态规划特点、条件和步骤动态规划的适用条件

适用动态规划的问题必须满足以下三个条件

最优化原理无后效性

子问题的重叠性动态规划特点优点离散性问题：使解析数学无用武之地；建模：可用计算机计算；缺点无统一处理方法：需要数学技巧与解题经验；组合爆炸：只能解决中小规模的问题第十页，共八十三页，2022年，8月28日10动态规划特点、条件和步骤最优性定理（最优子结构性质）

一个最优性策略具有这样的性质：不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优性原理又称其具有最优子结构性质。

无后向性

将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，只能通过当前给定的状态，直接影响未来的决策，而与以前各阶段的状态无关，这就是无后向性，又称为无后效性。换句话说，每个状态都是过去历史的一个完整总结。第十一页，共八十三页，2022年，8月28日11动态规划特点、条件和步骤子问题的重叠性

动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度可能要大于其它的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。

举例1：求二项式系数的计算(用分治递归)时间复杂性：T(n)=(2n)

第十二页，共八十三页，2022年，8月28日12动态规划特点、条件和步骤动态规划的逆序递推法的可归纳为以下四个步骤最优子结构：找出最优解的性质，并刻画其结构特征。最优值定义：递归定义最优值。计算最优值：自底向上或自顶向下计算出最优值。构造最优解：由计算最优值的信息，构造最优解。时间复杂性：T(n)=O(n-1)=1.61803，n1举例2：Fibonacci序列问题动态规划的正序递推法的步骤与逆序类似第十三页，共八十三页，2022年，8月28日13本节作业1.用动态规划方法，编写一个循环迭代算法计算如下的组合数。要求如下时间复杂性为(mn)空间复杂性为(m)思考：若用分治法计算同样的组合数，时间复杂性如何推导计算？第十四页，共八十三页，2022年，8月28日14第二节主要内容动态规划条件子问题的重叠性逆序、正序递推法的可归纳为以下四个步骤最优子结构：找出最优解的性质，并刻画其结构特征。最优值定义：递归定义最优值。计算最优值：自底向上或自顶向下计算出最优值。构造最优解：由计算最优值的信息，构造最优解。运用动态规划求解经典实例单源最短路径所有点对的最短路径第十五页，共八十三页，2022年，8月28日15教学目标动态规划适用条件充分理解子问题的重叠性理解动态规划的术语熟悉最优值函数、最优值基本方程动态规划的解题步骤熟练利用基本方程刻划最优子结构熟练利用基本方程递归定义最优值掌握自底向上方法计算最优值掌握用最优值相关信息，求最优解理解实例的解题步骤第十六页，共八十三页，2022年，8月28日16动态规划(单源最短路径)问题提出

G=<V，E>是一个多级图，如下图所示。第1阶段第2阶段第3阶段第4阶段状态1状态2状态4状态5状态3决策1决策2决策4决策3第十七页，共八十三页，2022年，8月28日17动态规划(单源最短路径)最优子结构

假设第

i+1级的状态集V

i+1中的任意一个顶点u到终点H的最短路径已经确定，第i级的状态集V

i中的任意一个顶点v到终点H的最短路径，是顶点v经过集V

i+1中某个顶点u到终点H的所有路径中最短的那条路径。这说明问题具有最优子结构性质。最优值定义

设过程共有k个级，即k1个阶段。又设Piv表示从V

i中的顶点v到H的一条最短路径，Cost(i,v)表示这条路径的代价，按照由后向前推进，可得：

第十八页，共八十三页，2022年，8月28日18动态规划(单源最短路径)计算最优值算法：Min_PathCost

输入：邻接矩阵A[1…n,1…n]

输出：从源点1到汇点n的最短路径长度在Cost[1]dist←Min_PathCost(A，n)过程：Min_PathCost(C，n)

1.fori←1ton12.Cost[i]←3.endfor4.Cost[n]←05.forj←n1downto16.设u使得(j,u)边集且C[j][u]+Cost[u]为最小7.Cost[j]←C[j][u]+Cost[u]8.D[j]←u9.endfor10.returnCost[1]第十九页，共八十三页，2022年，8月28日19动态规划(单源最短路径)构造最优解

计算最优值时用数组D[1…k]记录顶点u，因为(j,u)边集且C[j][u]+Cost[u]为最小，所以u是j的后继顶点。从而p[1]←1

p[k]←nforj←2tok1p[j]←D[p[j1]]endfor算法复杂性分析

时间复杂性：T(n)=(n2)空间复杂性：S(n)==(n)若A为邻接表：则T(n)=O(n+|E|)，其中n为顶点数，|E|为边集大小。第二十页，共八十三页，2022年，8月28日20动态规划(所有点对的最短路径)问题提出设G=<V，E>是一个简单有向图，其中每条边<i，j>长度w[i，j]0。若顶点i到顶点j没有边，则w[i，j]=，若i=j，则w[i，j]=0。G用邻接矩阵W表示。问题是找出每个顶点到其它所有顶点的最短路径。显然，邻接矩阵W本身表示V中每个顶点i到其它所有顶点j，而不经过任何中间顶点的最短路径，记为pij0。

定义pijk是顶点i到其它所有顶点j，且经过中间顶点序号不大于k的最短路径

。

pijn表示顶点i到其它所有顶点j，任意一个顶点都可作为最短路径上的中间顶点。

最优子结构由pijk定义知：当顶点i到其它所有顶点j，经过中间顶点序号不大于k1的最短路径恰好为pijk1，即有pijk=pijk1。第二十一页，共八十三页，2022年，8月28日21动态规划(所有点对的最短路径)

另一方面，由pijk定义又知：pikk1是顶点i到顶点k，且经过中间顶点序号不大于k1的最短路径，而pkjk1是从顶点k到顶点j，且经过中间顶点序号不大于k1的最短路径。这正说明pijk的最短路径包含pikk1和pkjk1的最短路径。综上所述，可知问题具有最优子结构的性质，即得：pijk=min{pijk1，pikk1+pkjk1}。

设Dk(i，j)是任一顶点i到其它所有顶点j，且经过中间顶点序号不大于k的最短路径长度。特别D0(i，j)=W。

Dk1(i，j)是任一顶点i到其它所有顶点j，且经过中间顶点序号不大于k1的最短路径长度。

Dk1(i，k)任一顶点i到顶点k，且经过中间顶点序号不大于k1的最短路径长度。

第二十二页，共八十三页，2022年，8月28日22动态规划(所有点对的最短路径)

Dk1(k，j)任一顶点k到顶点j，且经过中间顶点序号不大于k1的最短路径长度。最优值定义

综上所述可得：计算最优值

算法：Floyd

输入：邻接矩阵W

输出：

D[1…n,1…n]及next[1…n,1…n]分别为最优值及最 短路径矩阵

Floyd(W，next)过程：Floyd(D，next)第二十三页，共八十三页，2022年，8月28日23动态规划(所有点对的最短路径)

1.fori←1ton2.forj←1ton3.next[i][j]←j4.endfor5.endfor6.fork←1ton7.fori←1ton8.forj←1ton9.ifD[i][k]+D[k][j]<D[i][j]then10.D[i][j]←D[i][k]+D[k][j]11.next[i][j]←next[i][k]

12.endif13.endfor14.endfor15.endfor第二十四页，共八十三页，2022年，8月28日24动态规划(所有点对的最短路径)构造最优解

在计算最优值时，利用数组next[1…n,1…n]记载当前经过的中间顶点信息k，即数组next[1…n,1…n]记载任一顶点i到其它所有顶点j最短路径。

算法：Print_Path

输入：最短路径矩阵next[1…n,1…n]及i，j

输出：i到j的最短路径next[1…n,1…n]

Print_Path(next，i，j)过程：Print_Path(next，i，j)

1.ifnext[i][j]=jthen2.print(ij)3.return第二十五页，共八十三页，2022年，8月28日25动态规划(所有点对的最短路径)4.endif5.print(i)6.print_path(next，next[i][j]，j)

算法复杂性分析Floyd算法时间复杂性为T(n)=(n3)，而Print_Path算法时间复杂性为T(n)=(n)。算法时间复杂性：

T(n)=(n3)算法空间复杂性：

S(n)=(n2)Warshall传递闭包算法(略)第二十六页，共八十三页，2022年，8月28日26本节作业1.设G=(V，E)是n个顶点的简单有向图，A是G的关系R的关系矩阵。要求用动态规划方法，编写一个循环迭代算法，求R的传递闭包(即称Warshall算法)。第二十七页，共八十三页，2022年，8月28日27第三节主要内容动态规划条件子问题的重叠性逆序、正序递推法的可归纳为以下四个步骤最优子结构：找出最优解的性质，并刻画其结构特征。最优值定义：递归定义最优值。计算最优值：自底向上或自顶向下计算出最优值。构造最优解：由计算最优值的信息，构造最优解。运用动态规划求解经典实例最长公共子序列问题第二十八页，共八十三页，2022年，8月28日28教学目标动态规划适用条件充分理解子问题的重叠性理解动态规划的术语熟悉最优值函数、最优值基本方程动态规划的解题步骤熟练利用基本方程刻划最优子结构熟练利用基本方程递归定义最优值掌握自底向上方法计算最优值掌握用最优值相关信息，求最优解理解实例的解题步骤第二十九页，共八十三页，2022年，8月28日29动态规划(最长公共子序列问题)

相关概念若给定序列A={a1,a2,…,an}，则另一序列C={c1,c2,…,ck}为A的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：cj=aij。例如，序列C={b，c，d，b}是序列A={a，b，c，b，d，a，b}的子序列，相应的递增下标序列为{2，3，5，7}。公共子序列给定2个序列A和B，当另一序列C既是A的子序列又是B的子序列时，称C是序列A和B的公共子序列。问题提出—最长公共子序列。给定2个序列A={a1,a2,…,an}和B={b1,b2,…,bm}，找出A和B的最长公共子序列。显然，用蛮力策略，A有2n个子序列。若用(m)时间内可确定它也是B的一个子序列，其时间复杂性(m2n)。第三十页，共八十三页，2022年，8月28日30动态规划(最长公共子序列问题)

最优子结构性质设序列A={a1,a2,…,an}和B={b1,b2,…,bm}的最长公共子序列为C={c1,c2,…,ck}，则(1)若an=bm，则ck=an=bm，且Ck-1是An-1和Bm-1的最长 公共子序列。(2)若an≠bm且ck≠an，则C是An-1和B的最长公共子 序列。(3)若an≠bm且ck≠bm，则C是A和Bm-1的最长公共子 序列。由此可见，(1)说明A、B两个序列的最长公共子序列包含了它们前缀An-1、Bm-1的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。

第三十一页，共八十三页，2022年，8月28日31动态规划(最长公共子序列问题)递归定义最优值由最优子结构性质知：计算A和B的最长公共子序列时，都要计算A和Bm-1及An-1和B的最长公共子序列，而这两个子问题都包含一个公共子问题（重迭子问题），即计算Bm-1和An-1最长公共子序列。从上述可知：最长公共子序列问题的最优子结构性质决定了建立子问题最优值的递归关系。于是，令L[i,j]记录a1,a2,…,ai和b1,b2,…,bj的最长公共子序列的长度。显然，当i=0或j=0时，则L[i,j]=0表示Ai和Bj的最长公共子序列为空序列。其它情况，则由最优子结构性质建立递归关系如下：第三十二页，共八十三页，2022年，8月28日32动态规划(最长公共子序列问题)

举例：X=abcbdab，Y=bdcaba4432210b74332210a63322210d53322110b42222110c32211110b21110000a1000000Xi0abacdb6543210bacb递归推导得解：bcbaYjijnulnul0第三十三页，共八十三页，2022年，8月28日33动态规划(最长公共子序列问题)

计算最优值算法由递归关系直接计算，公共子问题求解会被重复计算。基于空间考虑，总共有(mn)个不同的子问题，用动态规划算法自底向上地计算最优值能提高算法的效率。

算法：LCSLENGTH

输入：字母表上的两个字符串A和B及长度n,m

输出：最长公共子序列的长度及最优解数组s[1…n][1…m]L←LCSLENGTH(n,m)过程：LCSLENGTH(n,m)

1 fori←0ton 2 L[i,0]←0 3 endfor4forj←0tom 5 L[0,j]←0 6 endfor第三十四页，共八十三页，2022年，8月28日34动态规划(最长公共子序列问题)

7 fori←1ton 8 forj←1tom 9 ifA[i]=B[j]then 10 L[i,j]←L[i-1,j-1]+1 12 s[i,j]←‘↖’13 elseifL[i-1,j]>=L[i,j-1]then14 L[i,j]←L[i-1,j] 15 s[i,j]←‘’ 16 else 17 L[i,j]←L[i,j-1]18 s[i,j]←‘’ 19 endif20 endif21endfor22endfor23returnL[n,m]和s复杂性分析 T(n)=(nm)改进

T(n)=min{m,n}第三十五页，共八十三页，2022年，8月28日35构造最优解

算法：LCS

输入：s[1n,1m]及n,m

输出：输出最长公共子序列xLCS(n,m,x,s)过程：LCS(i,j,x,s)1ifi=0orj=0thenreturn 2ifs[i,j]=

‘↖’then3LCS(i-1,j-1,x,s)4 输出x[i]5 elseifs[i,j]=‘’then6 LCS(i-1,j,x,s)7 else8 LCS(i,j-1,x,s)9endif10endif动态规划(最长公共子序列问题)复杂性分析

T(n)=O(n+m)第三十六页，共八十三页，2022年，8月28日36本节思考题1.用动态规划方法，编写一个循环迭代算法，求解给定序列的最长递增子序列。第三十七页，共八十三页，2022年，8月28日37第四节主要内容动态规划条件子问题的重叠性

逆序、正序递推法的可归纳为以下四个步骤最优子结构：找出最优解的性质，并刻画其结构特征。最优值定义：递归定义最优值。计算最优值：自底向上或自顶向下计算出最优值。构造最优解：由计算最优值的信息，构造最优解。运用动态规划求解经典实例矩阵连乘积问题第三十八页，共八十三页，2022年，8月28日38教学目标动态规划适用条件充分理解子问题的重叠性理解动态规划的术语熟悉最优值函数、最优值基本方程动态规划的解题步骤熟练利用基本方程刻划最优子结构熟练利用基本方程递归定义最优值掌握自底向上方法计算最优值掌握用最优值相关信息，求最优解理解实例的解题步骤第三十九页，共八十三页，2022年，8月28日39动态规划(矩阵连乘积问题)

问题提出设有矩阵M1，M2和M3及其维数分别是210，102和210，计算它们的乘积，即M1M2M3。矩阵的乘法顺序若按M1(M2M3)顺序计算，共有10210+21010=400数乘次数。而若按(M1M2)M3顺序计算，则数乘次数只有2102+2210=80。由上述可知：高效的矩阵乘积算法与矩阵的乘法结合律有关。这种结合顺序数随矩阵个数增长而增加。显然，算法就是寻找一个数乘次数最少的乘法运算顺序。蛮力的方法考察n个可乘的矩阵的M1M2…Mn，共有n-1个乘法运算顺序。如(M1M2M3M4)有3个乘法运算顺序，但它们的结合顺序数则有5种：第四十页，共八十三页，2022年，8月28日40动态规划(矩阵连乘积问题)显然，结合顺序数是n个矩阵加括弧的方法数。设f(n)为求n个矩阵乘积的所有放置括弧的方法数，假定矩阵乘法为： ((M1M2

…Mk

)

(Mk+1Mk+2

…Mn

))则有：复杂性分析

见数据结构P152的解法第四十一页，共八十三页，2022年，8月28日41动态规划(矩阵连乘积问题)每个括弧化表达式，有n-1次的矩阵乘法次数，即矩阵乘法时间是(n)。因此，数乘次数的时间复杂性为：最优子结构性质

设对于任意矩阵Mi，其行数为ri，列数为ri+1且1in，则(MiMi+1)可乘是Mi列数等于Mi+1行数。于是，M1，M2，…，Mn的行数分别为r1，r2，…，rn及rn+1，其中rn+1为Mn的列数。令Mi,j为矩阵乘积，Mi,j=MiMi+1…Mj，1ijn。由上述可知存在k，i+1kj，Mi,j=Mi,k-1

Mk,j。Mi,j的数乘次数记为C[i，j]，则计算C[i，j]： C[i，j]=C[i，k1]+C[k，j]+rirkrj+1复杂性分析

第四十二页，共八十三页，2022年，8月28日42动态规划(矩阵连乘积问题)这导致寻找一个k，i+1kj，使得C[i，j]最少，即特别地计算M1,n的一个最优顺序包含计算矩阵子链M1,k-1

和Mk,n，1<k<=n的最优顺序。若不然，存在一个数乘次数更少的子链M1,k-1，替换原来的M1,k-1的顺序，于是得到M1,n另一个最优的顺序，这是一个矛盾。同理可知，计算M1,n的一个最优顺序包含计算矩阵子链Mk,n的最优顺序。递归定义最优值第四十三页，共八十三页，2022年，8月28日43动态规划(矩阵连乘积问题)显然C[i，j]是Mi,j的一个最优顺序，i+1kj，即数乘次数最少，而原问题M1,n的一个最优顺序便是C[1，n]。当i=j时，即为单一矩阵，数乘次数显然为0。当i<j时，即存在k，i+1kj，使得C[i，j]是Mi,j的一个最优顺序。从而C[i，j]可递归定义：计算最优值算法从(1≤i≤j≤n)知：不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有第四十四页，共八十三页，2022年，8月28日44动态规划(矩阵连乘积问题)

举例计算5个矩阵乘积最少数乘次数。设：M1：510M2：104M3：46M4：610M5：102C[6,6]C[1,6]C[1,5]C[1,4]C[1,3]C[1,2]C[1,1]C[2,6]C[2,5]C[2,4]C[2,3]C[2,2]C[3,6]C[3,5]C[3,4]C[3,3]C[4,6]C[4,5]C[4,4]C[5,6]C[5,5]d=0d=2d=1d=3d=4d=5(M1(

M2(

M3(

M4M5))))例如：n=6的计算形式348262043203200202483640324030168424040120500第四十五页，共八十三页，2022年，8月28日45动态规划(矩阵连乘积问题)

由此可见，用递归计算，许多子问题被重复计算多次。动态规划算法恰好可克服这缺陷。用动态规划算法解此问题，可依据其最优值递归定义以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法，算法如下。

算法：MATCHAIN

输入：n个矩阵的链的维数r[1n+1]，其中r[1n]是n 个矩阵的行数，r[n+1]是Mn列数

输出：C[1,n]最优值和最优计算次序的s[1n,1n]1.MATCHAIN(n)

过程MATCHAIN(n)第四十六页，共八十三页，2022年，8月28日46动态规划(矩阵连乘积问题)

1fori←1ton2C[i,i]←03endfor4ford←1ton15 fori←1tond6j←i+d7 C[i,j]←C[i,i]+C[i+1,j]+r[i]r[i+1]r[j+1]8s[i,j]←i+19fork←i+2toj10t←C[i,k-1]+C[k,j]+r[i]*r[k]*r[j+1]11ift<C[i,j]then12 C[i,j]←t13s[i,j]←k14endif15endfor16endfor17endfor18returnC[1,n]和s算法复杂度分析：MATCHAIN算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。第四十七页，共八十三页，2022年，8月28日47动态规划(矩阵连乘积问题)构造最优解(最少数乘的矩阵链)MATCHAIN算法用s[i,j]记录矩阵乘积的最优计算次序全部信息，即计算Mi,j矩阵时，保存断开矩阵Mi,k-1和Mk,j断开点k。因为s[1,n]记录M1,n的最优括弧表达式，即有：M1,n=(M1,s[1,n]-1)(Ms[1,n],n)=((M1,s[1,s[1,n]-1]-1) (Ms[1,s[1,n]-1],s[1,n]-1))((Ms[1,n],s[s[1,n],n]-1)(Ms[s[1,n],n],n))以此类推构造最优解。显然，若要输出矩阵链的最优计算顺序，还要有一个输出最优解的算法，请参见教材P66一节。下列MChainMuliply算法输出Mi,j的最优计算次序的运算结果。

第四十八页，共八十三页，2022年，8月28日48动态规划(矩阵连乘积问题)算法：MChainMuliply输入：s[1n,1n]及1和n

输出：输出最优计算次序的Mi,j

MChainMuliply(1,n,s)

过程MChainMuliply(i,j,s)1ifi=jreturnMi2X←MChainMuliply(i,s[i,j]-1,s)3Y←MChainMuliply(s[i,j],j,s)4returnMultiply(XY)首先，假设算法Multiply(X，Y)表示矩阵X与Y的两个矩阵一般乘积，那么，MChainMuliply算法描述如下：第四十九页，共八十三页，2022年，8月28日49动态规划(矩阵连乘积问题)

动态规划的基本要素

1.最优子结构性质；2.重叠子问题；1.最优子结构性质

自底向上求解子问题的最优解，逐步构造问题最优解。2.重叠子问题用自顶向下的直接递归方式求解子问题，子问题有重复。计算M1,4的递归树第五十页，共八十三页，2022年，8月28日50算法：RecMatChain输入：

n个矩阵的链的维数r[1n+1]，其中r[1n]是n个矩阵的行数 ，r[n+1]是Mn列数

输出：记录矩阵乘积的最优计算次序的s[1n,1n]RecMatChain(1,n)

过程RecMatChain(i,j)1ifi=jreturn02u←RecMatChain(i,i)+RecMatChain(i+1,j)+r[i]*r[i+1]*r[j+1]3s[i,j]←i+14fork←i+2toj5t←RecMatChain(i,k)+RecMatChain(k+1,j)+r[i]*r[k]*r[j+1]6ifu<tthen7u←t8s[i,j]←k9endif10endfor11returns动态规划(矩阵连乘积问题)最坏情况下复杂性分析

第五十一页，共八十三页，2022年，8月28日51动态规划(矩阵连乘积问题)3.备忘录方法

备忘录方法与自顶向下的直接递归方式的控制结构相同，区别在于备忘录方法备忘了每个子问题的解，以备需要时查看。它是动态规划的一种变形。

算法：MemMatChain输入：整数n

输出：最优值数组C[1n,1n]和最优计算次序的s[1n,1n]MemMatChain(n)

过程MemMatChain(n)1 fori←1ton2forj←iton3C[i,j]←04endfor5endfor6returnLookupChain(1,n)第五十二页，共八十三页，2022年，8月28日52动态规划(矩阵连乘积问题) 1if(C[i,j]>0)thenreturnC[i,j] 2ifi=jthenreturn0 3u←LookupChain(i,i)+LookupChain(i+1,j)+r[i]*r[i+1]*r[j+1]; 4s[i,j]←i+1;5fork←i+2toj6t←LookupChain(i,k)+LookupChain(k+1,j)+r[i]*r[k]*r[j+1];7ift<uthen8u←t9s[i,j]←k10endif11C[i,j]←u12endfor13returns复杂性分析

算法：LookupChain输入：维数数组r[1n+1]及C[1n,1n]

输出：最优计算次序的s[1n,1n]1.LookupChain(1,n)

过程LookupChain(i,j)第五十三页，共八十三页，2022年，8月28日53本节作业1.对于以下5个矩阵应用本节算法MATCHAIN。M1：23，M2：36，M3：64，M4：42，M5：42找出这5个矩阵相乘需要的最少数乘乘法次数。请给出一个括号表达式，使在这种次序下达到乘法的次数最少。2.用备忘录方法，编写一个递归算法，计算斐波那契序列。第五十四页，共八十三页，2022年，8月28日54第五节主要内容动态规划条件子问题的重叠性

逆序、正序递推法的可归纳为以下四个步骤最优子结构：找出最优解的性质，并刻画其结构特征。最优值定义：递归定义最优值。计算最优值：自底向上或自顶向下计算出最优值。构造最优解：由计算最优值的信息，构造最优解。运用动态规划求解经典实例0/1背包问题第五十五页，共八十三页，2022年，8月28日55教学目标动态规划适用条件充分理解子问题的重叠性理解动态规划的术语熟悉最优值函数、最优值基本方程动态规划的解题步骤熟练利用基本方程刻划最优子结构熟练利用基本方程递归定义最优值掌握自底向上方法计算最优值掌握用最优值相关信息，求最优解理解实例的解题步骤第五十六页，共八十三页，2022年，8月28日56动态规划(0/1背包问题)

问题提出

设有n个物品的集合W={w1,w2,…，wn}，wj和vj分别为的物品体积和价值，C为背包容量，且C,wj,vj为正整数。要求从W中选择物品装入背包，使得装入背包的物品总价值最大。数学模型

0-1背包问题是一个特殊的整数规划问题

最优子结构性质1设(x1,x2,…,xn)为0/1背包问题的一个最优解，则(x2,…,xn)是相应子问题的一个最优解：第五十七页，共八十三页，2022年，8月28日57动态规划(0/1背包问题)若不然，设(z2,…,zn)是上述子问题的一个最优解，而(x2,…,xn)不是它的最优解。由此可知：且因此第五十八页，共八十三页，2022年，8月28日58动态规划(0/1背包问题)这说明(x1,z2,…,zn)是所给0/1背包问题的一个更优解，而(x1,x2,…,xn)不是问题0/1背包问题的一个最优解，此为矛盾。这说明(x1,x2,…,xn)不是问题0/1背包问题的一个最优解。最优子结构2

设V[i,j]表示从W中选择最前面i个物品组成的物品子集{w1,w2,…,wi}装入容量为j的背包总价值。于是得到：第五十九页，共八十三页，2022年，8月28日59动态规划(0/1背包问题)递归定义最优值

根据以上分析，定义如下递推关系：若V[i,j]对应子集不包含第i个物品wi，有V[i,j]=V[i1,j]。若V[i,j]对应子集包含第i个物品wi，即最优子集由第i个 物品wi及在最前面i1个物品中适合容量为jwi的子集 构成的，有V[i,j]=V[i1,jwi]+

vi。综上所述，最前面i个物品的所有可行的子集中，最 优解的价值是上述两者中的最大者。第六十页，共八十三页，2022年，8月28日60动态规划(0/1背包问题)

举例设物品体积集W={2,3,4,5}，V={3,4,5,7}及C=9，V[0…n,0…C]，H[1…n,0…C]和X[1n]

H[]0123456789100111111112000111111130000111111400000111111197308121087543007541298754300543777744300432333333300321000000000VWi976543210CV[]X[]0011X[]1110第六十一页，共八十三页，2022年，8月28日61动态规划(0/1背包问题)

算法:

KNAPSACK

输入:

n种物品体积数组W[1n]和V[0n,0C]价值数 组，背包容量C

输出:

最优

值V[n,C]及最优解信息数组H[0n,0C]

KNAPSACK(n,C)

过程

KNAPSACK(n,C)1

fori←0ton2V[i,0]←03endfor4forj←0toC5V[0,j]←06endfor

计算最优值及算法

1.自底向上方法算法如下第六十二页，共八十三页，2022年，8月28日62动态规划(0/1背包问题)

7fori←1ton8forj←1toC9V[i,j]←V[i-1,j]10ifwi<=jthen11ifV[i,j]<V[i-1,j-wi]+vithen12V[i,j]←V[i-1,j-wi]+vi13H[i,j]←114else15H[i,j]←016endif17endif18endfor19endfor20returnV[n,C]和H复杂性分析T(n)=(nC)第六十三页，共八十三页，2022年，8月28日63动态规划(0/1背包问题)2.备忘录方法用自顶向下的直接递归方法(并非所有的子问题都需要解)，数组V[0n,0C]存储各子问题的最优值，数组X[0n,0C]存储最优解的信息。

算法:

KNAPSACKREC 输入:n种物品体积数组W[1n]和V[1n,0C]价值 数组，背包容量C 输出:

最优值V[n,C]及最优解信息数组H[0n,0C]1

fori←0ton2forj←0toC3V[i,j]←14endfor5endfor6maxv←knapsack(n,C)7returnmaxv,H第六十四页，共八十三页，2022年，8月28日64动态规划(0/1背包问题)

过程knapsack(i,j)1ifV[i,j]=1then2ifi=0orj=0thenV[i,j]←03else 4b←knapsack(i-1,j)5ifw[i]<=jthen6a←knapsack(i-1,j-w[i])+v[i]；7ifa>=bthen8V[i,j]←a;H[i,j]←19else10V[i,j]←b;H[i,j]←011endif12endif13endif14endif15returnV[n,C],H复杂性分析T(n)=(nC)第六十五页，共八十三页，2022年，8月28日65构造最优解

算法SOLUTION

输入n种物品体积数组W[1n]和V[1n,0C]价值 数组，背包容量C及H[0n,0C]

输出

C中最大总价值及最优解信息数组X[1n]

SOLUTION(n,C)

过程SOLUTION(n,C)1y←C2X[n]←H[n,C]3fori←ndownto14ifX[i]=1theny←y-w[i]5X[i-1]←H[i-1,y]6endfor7returnX动态规划(0/1背包问题)复杂性分析

T(n)=(n)第六十六页，共八十三页，2022年，8月28日66本节作业1.教材P1043-4（1）第六十七页，共八十三页，2022年，8月28日67第六节主要内容动态规划条件子问题的重叠性

逆序、正序递推法的可归纳为以下四个步骤最优子结构：找出最优解的性质，并刻画其结构特征。最优值定义：递归定义最优值。计算最优值：自底向上或自顶向下计算出最优值。构造最优解：由计算最优值的信息，构造最优解。运用动态规划求解经典实例最优二叉搜索树问题第六十八页，共八十三页，2022年，8月28日68教学目标动态规划适用条件充分理解子问题的重叠性理解动态规划的术语熟悉最优值函数、最优值基本方程动态规划的解题步骤熟练利用基本方程刻划最优子结构熟练利用基本方程递归定义最优值掌握自底向上方法计算最优值掌握用最优值相关信息，求最优解理解实例的解题步骤第六十九页，共八十三页，2022年，8月28日69二叉搜索树

设X={x1，x2，…，xn}是一个有序集，即x1<x2<…<xn。用二叉树的结点存储X中的元素，这此结点称为内部结点。X的二叉搜索树T具有如下性质：(1)若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；(2)若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；(3)它的左、右子树也分别为二叉搜索树451253337249961动态规划(最优二叉搜索树问题)

在随机的情况下，二叉搜索树的查找成功或者不成功比较次数最多不超过第七十页，共八十三页，2022年，8月28日70动态规划(最优二叉搜索树问题)问题提出 设X={x1，x2，…,xn}是一个有序集。若其元素在“等概率”前提下，在搜索树下的二分查找，其性能最优。若去除“等概率”的前提，在搜索树下的二分查找，其性并不一定能最优。现在，考虑X有序集中的各个元素在“不等概率”情况下，如何构造一棵平均查找次数(或路径)最少的二叉搜索树，称之为最优二叉搜索树，简称最优搜索树。最优搜索树是客观存在的事实。首先，考察静态最优搜索树(或称次优搜索树)，设5个关键字的有序表及其元素相应权值(或查找成功概率)为： 关键字ABCDE 权值1302293则构造次优搜索树如下：

第七十一页，共八十三页，2022年，8月28日71（1）构造算法次优查找树的时间复杂度：O(nlogn)（2）次优查找树的特点它与最优查找树时间复杂度相差不超过3%，但构造容易；其平均查找长度和logn成正比；在元素的查找概率不等时，可用次优查找树表示静态查找树，故称静态查找树表。ECDABEADBC平均查找路长为132的搜索树动态规划(最优二叉搜索树问题)平均查找路长为105的搜索树第七十二页，共八十三页，2022年，8月28日72现在，不仅要考察查找成功概率，也要考察查找不成功概率的情况，于是，在T中搜索一个元素x，返回的结果是：(1)找到T中的内部结点xi=x，设bi为xi的查找成功概率；(2)没找到，即有叶子结点(xi，xi+1)。设ai为x的查找不成 功概率。有：动态规划(最优二叉搜索树问题)

二叉搜索树的平均比较次数(或路长)第七十三页，共八十三页，2022年，8月28日73蛮力方法时间复杂度

n个内部结点和n+1个叶子结点的不同二叉搜索树表示了不同的搜索策略。n个内部结点共有 棵不同二叉搜索树。故 ，见右图。动态规划(最优二叉搜索树问题)最优子结构二叉搜索树T的一棵含有内部结点xi，…，xj和叶子结点(xi-1，xi)，…，(xj，xj+1)的子树可以看作是有序集{xi，…,xj}关于全集合{xi-1，…，xj+1}的一棵二叉搜索树，其存取概率为下面的条件概率(bi、ai分别为查找xi成功、不成功概率)xkT(1,k-1)T(k+1,n)T(1,n)第七十四页，共八十三页，2022年，8月28日74动态规划(最优二叉搜索树问题)

设有序集{xi，…，xj}关于存取概率的一棵最优二叉搜索