程序设计基础12_2_动态规划(2015春)

1、第第12章章 贪心法贪心法与动态规划与动态规划112.1.3贪心法解题的一般步骤贪心法特点，就是在求最优解的过程中，每一步都采用一种贪心法特点，就是在求最优解的过程中，每一步都采用一种局部最局部最优策略优策略，逐渐，逐渐缩小缩小问题范围和规模，最后把每一步结果问题范围和规模，最后把每一步结果合并合并起来得起来得到一个全局的最优解。到一个全局的最优解。在例在例12.112.1中，每次选取删除的数字都是中，每次选取删除的数字都是第一个递减区间的首位数第一个递减区间的首位数字字，也就是当前的删除可以保证在当前删除位数要求下的最优解，也就是当前的删除可以保证在当前删除位数要求下的最优解，同时使剩下的数

2、字串逐渐接近最后要求的目标最优解。同时使剩下的数字串逐渐接近最后要求的目标最优解。2在例在例12.212.2中，每一次选取的时间都是满足条件的中，每一次选取的时间都是满足条件的最早结束事件最早结束事件，向问题的解答前进一步，同时给剩余事件的选取留下了最多的不向问题的解答前进一步，同时给剩余事件的选取留下了最多的不重叠时间；最后得到的事件序列，就是每一次选取的事件集合。重叠时间；最后得到的事件序列，就是每一次选取的事件集合。在例在例12.312.3中，每一步都中，每一步都将覆盖最大间隔的线段断开将覆盖最大间隔的线段断开，使得线段总，使得线段总长度减少，同时使线段数目更接近最大数目限制；最后得到的

3、最长度减少，同时使线段数目更接近最大数目限制；最后得到的最小线段总长度，其实是计算过程唯一确定的一种线段覆盖方式得小线段总长度，其实是计算过程唯一确定的一种线段覆盖方式得到的。到的。贪心法解题的一般步骤贪心法解题的一般步骤 从问题的某个初始解出发；从问题的某个初始解出发； 采用循环语句，当可以向求解目标前进一步时，采用循环语句，当可以向求解目标前进一步时，根据局部最优策略，得到一个部分解，缩小问题根据局部最优策略，得到一个部分解，缩小问题的范围或规模；的范围或规模； 将所有部分解综合起来，得到问题的最终解。将所有部分解综合起来，得到问题的最终解。312.1 12.1 贪贪 心心 法法12.2

4、12.2 动动 态态 规规 划划4引例引例 递归的重叠子问题递归的重叠子问题 斐波那契序列：斐波那契序列：f(1)=1; f(2)=1;f(1)=1; f(2)=1; f(n)=f(n-1)+f(n-2); (n2) f(n)=f(n-1)+f(n-2); (n2)5 递归实现递归实现long longlong long f(int n)f(int n) if if(n=1|n=2)(n=1|n=2) returnreturn 1 1; ; returnreturn f(n-1)f(n-1)+ +f(n-2)f(n-2); ; f(6)=f(5)+f(4) =f(4)+f(3)+f(4) 动态

5、规划动态规划DPDP实现实现long long long long f(int n)f(int n) intint i; i; long long long long a100;a100; a1=1;a2=1;a1=1;a2=1; forfor(i=3; i=n;i+)(i=3; inSum2)if(nSum1nSum2)return (nSum1+Dij);return (nSum1+Dij);elseelsereturn (nSum2+Dij);return (nSum2+Dij); 语句简洁，但效率低下语句简洁，但效率低下N=100时 ，总的调用次数为：20+ 21+ 22+299不可忍

6、受！不可忍受！10解决办法解决办法n 第一次算出第一次算出MaxSun(i,j)MaxSun(i,j)的值时直接保存，以的值时直接保存，以后用时取出来即可，不必重复计算。后用时取出来即可，不必重复计算。n 每个每个MaxSunMaxSun（i,ji,j）只需计算一次，总的计算）只需计算一次，总的计算次数就是数字三角形中的数字总数，即：次数就是数字三角形中的数字总数，即：1+2+3+N=N(N+1)/21+2+3+N=N(N+1)/2。n 用用aijaij存放存放MaxSunMaxSun（i,ji,j）的计算结果）的计算结果 n 求值过程的递推关系：求值过程的递推关系： aij=Dij i=NM

7、ax(ai+1j,ai+1,j+1)+Dij 其它从第N-1行开始向上逐行递推，就可以求得a11的值。 11int main()int main() int i,j;int i,j;scanf(%d,&N);scanf(%d,&N);for(i=1;i=N;i+)for(i=1;i=N;i+)for(j=1;j=i;j+)for(j=1;j=i;j+)scanf(%d,&Dij);scanf(%d,&Dij);for(j=1;jfor(j=1;j= =N;j+) N;j+) / / 修改教材修改教材p292 jN p292 jN 改成改成 j=N j1;i-)f

8、or(i=N;i1;i-)for(j=1;j=i;j+)for(j=1;jaij+1)if(aijaij+1)ai-1j=aij+Di-1j;ai-1j=aij+Di-1j;elseelseai-1j=aij+1+Di-1j;ai-1j=aij+1+Di-1j;printf(%dn,a11);printf(%dn,a11);return 0;return 0; 12动态规划动态规划 这种将一个问题分解成为子问题求解，并且将这种将一个问题分解成为子问题求解，并且将中间子问题的结果保存起来以避免重复计算的中间子问题的结果保存起来以避免重复计算的方法，就叫做方法，就叫做“ “动态规划动态规划” ”。

9、 动态规划通常用来求最优解，能用动态规划求动态规划通常用来求最优解，能用动态规划求解的问题，必须满足最优解的每个局部解也都解的问题，必须满足最优解的每个局部解也都是最优的。即：如上述数组是最优的。即：如上述数组a a里面的每个元素里面的每个元素值，都是对应下标位置到达三角形底部的最佳值，都是对应下标位置到达三角形底部的最佳路径。路径。13动态规划的基本思想动态规划的基本思想 什么样的问题适合用动态规划求解呢什么样的问题适合用动态规划求解呢? ? 两个基本要素两个基本要素(1)(1)和和(2)(2)(1)(1)最优子结构性质最优子结构性质 基本基本要求要求是该问题具有最优子结构性质是该问题具有最

10、优子结构性质，通俗地讲即问题的最优通俗地讲即问题的最优解包含其子问题的最优解解包含其子问题的最优解。(2)(2)子问题重叠性质子问题重叠性质 子问题呈现大量的重复，称为子问题重叠性质。子问题呈现大量的重复，称为子问题重叠性质。(3)(3)记忆化记忆化 在应用动态规划时，对于重复出现的子问题，只需在第一次遇到在应用动态规划时，对于重复出现的子问题，只需在第一次遇到时加以求解，并把答案保存起来，以便以后再遇到时直接引用，不时加以求解，并把答案保存起来，以便以后再遇到时直接引用，不必重新求解，从而大大地提高解题的效率必重新求解，从而大大地提高解题的效率实质：分治思想和解决冗余。实质：分治思想和解决冗

11、余。优势：相比之下，一般的搜索技术，对于某个子问题，不管是否已优势：相比之下，一般的搜索技术，对于某个子问题，不管是否已经求解过，只要遇上，就会再次对它求解，因而影响解题的效率。经求解过，只要遇上，就会再次对它求解，因而影响解题的效率。 14动态规划算法的基本步骤动态规划算法的基本步骤 (1)(1)选择适当的问题状态表示，并分析最优解的性质；选择适当的问题状态表示，并分析最优解的性质； (2)(2)递归地定义最优值递归地定义最优值( (即建立递归关系即建立递归关系) )； (3)(3)以自底向上的方式计算出最优值；以自底向上的方式计算出最优值； (4)(4)根据计算最优值时得到的信息，构造一个

12、最优解。根据计算最优值时得到的信息，构造一个最优解。步骤步骤(1)(3)是动态规划的基本步骤。在只需要是动态规划的基本步骤。在只需要求出最优值的情形，步骤求出最优值的情形，步骤(4)可以省略。可以省略。若需要求出问题的一个最优解，则必须执行步骤若需要求出问题的一个最优解，则必须执行步骤(4)。此时，。此时，在步骤在步骤(3)中计算最优值时，通常需记录更多的信息，以便在中计算最优值时，通常需记录更多的信息，以便在步骤步骤(4)中，根据所记录的信息，快速地构造出一个最优解。中，根据所记录的信息，快速地构造出一个最优解。15 这道题已经用动态规划成功地解决，但是，如果对问题这道题已经用动态规划成功地

13、解决，但是，如果对问题的最优结构刻画得不恰当的最优结构刻画得不恰当( (即状态表示不合适即状态表示不合适) )，则无法，则无法使用动态规划。使用动态规划。 比如：比如： 用一元组用一元组D(X)D(X)描述问题，描述问题，D(X)D(X)表示从顶层到达第表示从顶层到达第X X层层的最大路径得分。因此，此问题就是求出的最大路径得分。因此，此问题就是求出D(N)(D(N)(若需要若需要，还应求出最优路径，还应求出最优路径) )。这是一种很自然的想法和表示。这是一种很自然的想法和表示方法。遗憾的是，这种描述方式并不能满足最优子结构方法。遗憾的是，这种描述方式并不能满足最优子结构性质。因为性质。因为D

14、(X)D(X)的最优解的最优解( (即最优路径即最优路径) )可能不包含子问可能不包含子问题题例如例如D(X-1)D(X-1)的最优解。的最优解。 7 3 8 8 1 0 数字三角形 16 显然，显然，D(3)D(3)7+3+87+3+81818，其最优解，其最优解( (路径路径) )为为7-3-87-3-8。而而D(2)D(2)7+87+81515，最优解，最优解( (路径路径) )为为7-87-8。故。故D(3)D(3)的最的最优解不包含子问题优解不包含子问题D(3)D(3)的最优解。由于不满足最优子的最优解。由于不满足最优子结构性质，因而无法建立子问题最优值之间的递归关结构性质，因而无法

15、建立子问题最优值之间的递归关系，也即无法使用动态规划。系，也即无法使用动态规划。 7 3 8 8 1 0 数字三角形 17 注意事项注意事项: : (1) (1)问题的状态表示对能否用动态规划进行求解是至问题的状态表示对能否用动态规划进行求解是至关重要的，不恰当的状态表示将使问题的描述不具有最关重要的，不恰当的状态表示将使问题的描述不具有最优子结构性质，从而无法建立最优值的递归关系，动态优子结构性质，从而无法建立最优值的递归关系，动态规划的应用也就无从谈起。因此，上面步骤规划的应用也就无从谈起。因此，上面步骤(1)(1)，即状即状态表示和最优子结构性质的分析，是最关键的一步态表示和最优子结构性

16、质的分析，是最关键的一步。 (2) (2)在算法的程序设计中，应充分利用子问题重叠性在算法的程序设计中，应充分利用子问题重叠性质来提高解题效率。更具体地说，质来提高解题效率。更具体地说，应采用递推应采用递推( (迭代迭代) )的的方法来编程计算由递归式定义的最优值，而不采用直接方法来编程计算由递归式定义的最优值，而不采用直接递归的方法。递归的方法。18例例12.5 最长公共子序列问题最长公共子序列问题 p294 p294子序列：子序列：Z=Z= 是是 X=A X= 的一个子序列，可以不相邻但是的一个子序列，可以不相邻但是先后顺序保持不变先后顺序保持不变公共子序列：公共子序列： X= X=和和Y

17、=Y=的公共子序列的公共子序列 和和等，等，最长最长4 4一个给定序列的一个给定序列的子序列子序列是在该序列中删去若干元素后得到的序列。是在该序列中删去若干元素后得到的序列。给定给定2 2个序列个序列X X和和Y Y，当另一序列，当另一序列Z Z既是既是X X的子序列又是的子序列又是Y Y的子序列时，的子序列时，称称Z Z是序列是序列X X和和Y Y的公共子序列。公共子序列中长度最长的公共子序列的公共子序列。公共子序列中长度最长的公共子序列叫做叫做最长公共子序列最长公共子序列。最长公共子序列最长公共子序列(LCS)(LCS)问题问题可以叙述为：给定可以叙述为：给定2 2个序列个序列X=xX=x

18、1 1，x xm m 和和Y=yY=y1 1，y yn n ，要求找出，要求找出X X和和Y Y的一个最长公共子序列。的一个最长公共子序列。 19 方案一：枚举方案一：枚举 对对X X的每一个子序列，检查它是否也是的每一个子序列，检查它是否也是Y Y的子序列，从的子序列，从而确定它是否为而确定它是否为X X和和Y Y的公共子序列，并且在检查过程的公共子序列，并且在检查过程中遴选出最长的公共子序列。中遴选出最长的公共子序列。X X的所有子序列都检查的所有子序列都检查过后即可求出过后即可求出X X和和Y Y的最长公共子序列。的最长公共子序列。 X X的一个子序列相应于下标序列的一个子序列相应于下标

19、序列11，2 2，mm的一个的一个子序列，故子序列，故X X共有共有2 2mm个不同子序列，枚举需要指数时个不同子序列，枚举需要指数时间。为此，考虑能否用动态规划方法求解。间。为此，考虑能否用动态规划方法求解。20例例12.5 最长公共子序列问题最长公共子序列问题 p294p294 方案二：动态规划方案二：动态规划 最优子结构性质：最优子结构性质： 设序列设序列X=xX=x1 1，x xmm 和和Y=yY=y1 1，y yn n 的一个最的一个最长公共子序列为长公共子序列为Z=zZ=z1 1，z zk k 。则下述结论成立：。则下述结论成立： (1) (1)若若x xmm=y=yn n，则，则

20、z zk k=x=xmm=y=yn n 且且Z(k-1)Z(k-1) = z = z1 1，z zk-1k-1 是是X(m-1)X(m-1)和和Y(n-1)Y(n-1)的最长公共子序列。的最长公共子序列。 (2) (2)若若x xmm y yn n 且且 z zk k x xmm，则，则Z Z是是X(m-1)X(m-1)和和Y Y的最长公共子的最长公共子序列。序列。 (3) (3)若若x xmm y yn n 且且 z zk k y yn n，则，则Z Z是是X X和和Y(n-1)Y(n-1)的最长公共子的最长公共子序列。序列。 证明略证明略21例例12.5 最长公共子序列问题最长公共子序列问

21、题 p294p294 由最长公共子序列问题的最优子结构性质可知，要找由最长公共子序列问题的最优子结构性质可知，要找出出X=xX=x1 1，x xm m 和和Y=yY=y1 1，y yn n 的一个最长公共子的一个最长公共子序列，可按以下方式递归地进行：序列，可按以下方式递归地进行： 当当 x xm m = y = yn n时时，找出，找出X(m-1)X(m-1)和和Y(n-1)Y(n-1)的最长公共子的最长公共子序列，然后在其尾部加上序列，然后在其尾部加上x xm m(=y(=yn n) )即可得即可得X X和和Y Y的一个最的一个最长公共子序列。长公共子序列。 当当x xm m y yn n

22、时时，必须解，必须解2 2个子问题个子问题，即找出，即找出X(m-1)X(m-1)和和Y Y的一个最长公共子序列及的一个最长公共子序列及X X和和Y(n-1)Y(n-1)的一个最长公的一个最长公共子序列。这共子序列。这2 2个公共子序列中个公共子序列中较长者较长者即为即为X X和和Y Y的一个的一个最长公共子序列。最长公共子序列。22例例12.5 最长公共子序列问题最长公共子序列问题 p294p294状态表示：用状态表示：用Ci,jCi,j记录序列记录序列X(i)X(i)和和Y(j)Y(j)的最长公共子序列的长的最长公共子序列的长度，其中度，其中X(i)=xX(i)=x1 1，x xi i,

23、Y(j)=y, Y(j)=y1 1，y yj j 。原问题最优。原问题最优解的长度为解的长度为Cm,nCm,n。我们来建立子问题的最优值我们来建立子问题的最优值Ci,jCi,j的递归关系。当的递归关系。当i=0i=0或或j=0j=0时，时，空序列是空序列是X(i)X(i)和和Y(j)Y(j)的最长公共子序列，故的最长公共子序列，故Ci,jCi,j0 0。其他情。其他情况下，由最优子结构性质，可建立递归方程如下况下，由最优子结构性质，可建立递归方程如下: : 0 i=0 或j=0;Ci,j Ci-1,j-1+1 i,j0 且xi i=yj j; maxCi-1,j,Ci,j-1 i,j0 且xi

24、 iyj j;由此递归方程容易看到最长公共子序列问题具由此递归方程容易看到最长公共子序列问题具有子问题重叠性质。有子问题重叠性质。 23例例12.5 最长公共子序列问题最长公共子序列问题 p294p29424例例12.5 最长公共子序列问题最长公共子序列问题 p294p294intint main() main() intint i,j,len1,len2,cNN; i,j,len1,len2,cNN;charchar xN,yN; xN,yN;gets(x);gets(x);gets(y);gets(y);len1=strlen(x);len1=strlen(x);len2=strlen(y

25、);len2=strlen(y);forfor(i=0;i=len1;i+) (i=0;i=len1;i+) / /初始化首列初始化首列ci0=0;ci0=0;forfor(j=0;j=len2;j+) (j=0;j=len2;j+) / /初始化首行初始化首行c0j=0;c0j=0;25例例12.5 最长公共子序列问题最长公共子序列问题 p296p296forfor(i=1;i=len1;i+) (i=1;i=len1;i+) / /动态规划动态规划 forfor(j=1;j=len2;j+)(j=1;jcij-1) (ci-1jcij-1) cij=ci-1j; cij=ci-1j; el

26、seelse cij=cij-1; cij=cij-1;printf(%dn,clen1len2);printf(%dn,clen1len2);returnreturn 0; 0; 26例例12.5 最长公共子序列问题最长公共子序列问题 p296p296例例12.6 12.6 最长上升子序列最长上升子序列 p296 p296n 上升序列上升序列 b b (b (b1 1, b, b2 2, ., b, ., bs s) ) ，其中，其中b b1 1 b b2 2 . . b bS Sn 对于给定的序列，求出最长上升子序列的长度。对于给定的序列，求出最长上升子序列的长度。n 给定序列给定序列(a

27、(a1 1, a, a2 2, ., a, ., an n) ) 可以得到一些上升的子序列可以得到一些上升的子序列(a(ai1i1, a, ai2i2, ., a, ., aiKiK) ) 其中其中1= 1= i i1 1 i i2 2 . i . iKK = n= n，可以不相邻，但先后顺序不能改变可以不相邻，但先后顺序不能改变n 例如对于序列例如对于序列(1, 7, 3, 5, 9, 4, 8)(1, 7, 3, 5, 9, 4, 8) 上升子序列有上升子序列有(1) (1, 7) (3, 4, 8) (1,3,5,8) (1) (1, 7) (3, 4, 8) (1,3,5,8) 其中其

28、中最长的长度是最长的长度是4 4，比如子序列，比如子序列(1, 3, 5, 8)(1, 3, 5, 8) 2712.6 12.6 最长上升子序列最长上升子序列 p296 p296n 方案一：枚举方案一：枚举，例如对于，例如对于序列序列(1, 7, 3, 5, 9, 4, 8) (1, 7, 3, 5, 9, 4, 8) 28n 方案二：动态规划方案二：动态规划DPDP，划分子问题，划分子问题 (1)原问题原问题nMaxnMaxn n个数序列个数序列(a(a1 1,a,a2 2, ,a, ,an n) ) 的最长上升序列的长度的最长上升序列的长度 (2)子问题子问题MaxLen(MaxLen(k

29、 k) )求以求以a ak k(k=1,2,3, ,n)(k=1,2,3, ,n)为为终点终点的最长上升的最长上升子序列的长度，子序列的长度，终点终点是指上升子序列中最右边的那个数是指上升子序列中最右边的那个数 (3)原问题最优解原问题最优解 nMax nMax = = MaxMax MaxLen( MaxLen(k k), ),k k= =1 1, ,2 2, ,3 3, , ,n n 2912.6 12.6 最长上升子序列最长上升子序列 p296 p296n 方案二：动态规划方案二：动态规划DPDP，划分子问题，划分子问题 (1)原问题原问题nMaxnMaxn n个数序列个数序列(a(a1

30、 1,a,a2 2, ,a, ,an n) ) 的最长上升序列的长度的最长上升序列的长度 (2)子问题子问题MaxLen(MaxLen(k k) )求以求以a ak k(k=1,2,3, ,n)(k=1,2,3, ,n)为为终点终点的最长上升子序列的最长上升子序列的长度，的长度，终点终点是指上升子序列中最右边的那个数是指上升子序列中最右边的那个数 (3)原问题最优解原问题最优解 nMax nMax = = MaxMax MaxLen( MaxLen(k k), ),k k= =1 1, ,2 2, ,3 3, , ,n n MaxLen ( MaxLen (1 1) = ) = 1 1 Max

31、Len ( MaxLen (k k) = ) = MaxMax MaxLen ( MaxLen (i i) )：1 1 i i k k 且且 a ai i a ak k 且且 k1 + k1 + 1 1n 虽然虽然子问题子问题与与原问题原问题形式上并不完全一样，但是只要这形式上并不完全一样，但是只要这NN个子问个子问题都解决了，那么这题都解决了，那么这NN个子问题的解中，最大的那个就是整个问个子问题的解中，最大的那个就是整个问题的解。上述子问题与题的解。上述子问题与终点终点的位置有关。的位置有关。3012.6 12.6 最长上升子序列最长上升子序列 p296 p296n 方案二：动态规划方案二

32、：动态规划DPDP，划分子问题，找出，划分子问题，找出状态转移方程状态转移方程nMax nMax = = MaxMax MaxLen( MaxLen(k k), ),k k= =1 1, ,2 2, ,3 3, , ,n n n 状态转移方程状态转移方程的含义的含义 MaxLen(MaxLen(k k) )的值的值在在a ak k左边左边的那些的那些“终点终点i i”数值数值小于小于a ak k，且长，且长度度最大最大的那个上升子序列的长度再加的那个上升子序列的长度再加1 1，即，即a ak k 左边左边任何任何“终点终点i i”小小于于a ak k 的子序列，加上的子序列，加上a ak k

33、后就能形成一个后就能形成一个更长更长的上升子序列。的上升子序列。n 实现时不必写递归函数，从实现时不必写递归函数，从 MaxLen(1)MaxLen(1)就能推算出就能推算出MaxLen(2)MaxLen(2)，有了有了MaxLen(1)MaxLen(1)和和MaxLen(2)MaxLen(2)就能推算出就能推算出MaxLen(3)MaxLen(3) 状态转移方程：状态转移方程： MaxLen ( MaxLen (1 1) = ) = 1 1 MaxLen ( MaxLen (k k) = ) = MaxMax MaxLen ( MaxLen (i i) )：1 1 i i k k 且且 a

34、ai i a ak k 且且 k1 + k1 + 1 1课堂练习课堂练习 10 33 12 55 49 64 78 37 30 6610 33 12 55 49 64 78 37 30 66元素的元素的位序位序i“终点终点”元素的值元素的值第第i个元素为个元素为终点的最大上终点的最大上升子序列长度升子序列长度110234567891033125549647837306611033212233453355564783730664931intint main() main() intint n, n, mm, i, , i, j j; ; /m/m存放存放a ai i左边各终点左边各终点 / /最

35、长上升子序列长度的最大值最长上升子序列长度的最大值 scanf(“%d”,&n); scanf(“%d”,&n); / /输入序列长度输入序列长度n nforfor( (i i=1; i=n; i+)=1; i=n; i+) scanf(“%d”,&bi); scanf(“%d”,&bi); / /输入输入n n个整数个整数bibi MaxLen MaxLen1 1=1 1; ; / /初始化以第一个数为初始化以第一个数为 / /终点的最长上升子序列长度终点的最长上升子序列长度1 1 forfor( (i=2; i=n; i+i=2; i=n; i+) ) /

36、/求以求以a ai i为终点的为终点的 mm=0;=0; / /最长上升子序列长度最长上升子序列长度 forfor(j=1; j(j=1; j ajaj) ) / /小于升子序列长度小于升子序列长度 if if( (mmMaxLenj)MaxLenj) mm=MaxLenj;=MaxLenj; MaxLen MaxLeni i=mm+ +1 1; ; int int nMax nMax = -1; = -1; / /初始化初始化nMaxnMax / /循环求以循环求以akak为终点的为终点的 / /最长上升子序列最大长度最长上升子序列最大长度 for for( (i=1; i=n; i+) i

37、=1; i=n; i+) if if( (nMax nMax MaxLen MaxLeni i) ) nMax nMax = MaxLen= MaxLeni i; ; printf(“%dn”, printf(“%dn”,nMaxnMax); ); / /输出最大长度输出最大长度 return return 0; 0; 32n 方案二：动态规划方案二：动态规划DPDP的实现的实现nMaxnMax = = MaxMax MaxLen( MaxLen(i i), ), i i= =1 1, ,2 2, ,3 3, , ,n n MaxLen (MaxLen (1 1) = ) = 1 1MaxLe

38、n (MaxLen (i i) = ) = MaxMax MaxLen ( MaxLen (j j) )：1 1 j j i i 且且 b bj j b bi i 且且 i1 + i1 + 1 1特别提醒：教材特别提醒：教材p297p297状态转移方程状态转移方程 源程序源程序 a a 教材中数组教材中数组 b b k k 教材中变量教材中变量 i i i i 教材中变量教材中变量 j j3312.6 12.6 最长上升子序列最长上升子序列 p296 p2963412.6 12.6 最长上升子序列最长上升子序列 p296 p2963512.6 12.6 最长上升子序列最长上升子序列 p296

39、p296补充例题分析补充例题分析1、编辑距离问题编辑距离问题2 2、排队买票问题、排队买票问题 36编辑距离问题编辑距离问题 1. 1. 问题描述问题描述 设设A A和和B B是是2 2个字符串。要用最少的字符操作，将字符个字符串。要用最少的字符操作，将字符串串A A转换为字符串转换为字符串B B。这里所说的字符操作包括：。这里所说的字符操作包括： (1) (1)删除一个字符；删除一个字符； (2) (2)插入一个字符；插入一个字符； (3) (3)将一个字符改为另一个字符。将一个字符改为另一个字符。 将字符串将字符串A A转换为字符串转换为字符串B B所用的最少字符操作数称所用的最少字符操作

40、数称为字符串为字符串A A到到B B的编辑距离，记为的编辑距离，记为 (A,B)(A,B)。请求出。请求出 (A,B)(A,B)。37 2 2解题思路解题思路 设所给的设所给的2 2个字符串分别为个字符串分别为A AA1.mA1.m和和B=B1.nB=B1.n。 状态表示：考虑从字符子串状态表示：考虑从字符子串A1.i(A1.i(按序按序) )变换到字符变换到字符子串子串B1.jB1.j的最少字符操作问题，有的最少字符操作问题，有d(id(i，j)j) (A1.i(A1.i， B1.j) B1.j)。显然，。显然，2 2个单字符个单字符a a，b b之间的编之间的编辑距离辑距离: :当当aba

41、b时，为时，为 (a(a，b)b)1 1；当；当a=ba=b时，为时，为 (a(a，b)b)0 0 。问题的解为。问题的解为d(md(m，n)n)。 最优子结构性质：假设最优子结构性质：假设E Ee el le ek-1k-1e ek k，k= d(i,j)k= d(i,j)为从为从字符串字符串A1.iA1.i按序变换到字符串按序变换到字符串B1.jB1.j的一个最少字的一个最少字符操作序列符操作序列( (也称作也称作d(i,j)d(i,j)的一个最优解的一个最优解) )，那么最后一，那么最后一个操作个操作e ek k，属于下列，属于下列3 3种操作之一：种操作之一：38 (1)(1)将字符将

42、字符AiAi改为字符改为字符Bj(Bj(如果如果AiAiBjBj，则，则e ek k为空操作为空操作, ,不参加计数不参加计数) )，此时，此时E E1 1e el le ek-1k-1为为d(i-1d(i-1，j-j-1)1)的一个最优解；的一个最优解； (2) (2)删除字符删除字符Ai,Ai,此时此时E E1 1e el le ek-1k-1为为d(i-1,j)d(i-1,j)的一个的一个最优解；最优解； (3) (3)插入字符插入字符Bj,Bj,此时此时E E1 1e el le ek-1k-1为为d(i,j-1)d(i,j-1)的一个的一个最优解。最优解。 因此因此, ,问题具有最优子结构性质。根据最优子结构性问题具有最优子结构性质。根据最优子结构性质质, ,建立递归关系如下：建立递归关系如下： d(i,j)=mind(i-1,j-1)+d(i,j)=mind(i-1,j-1)+ (Ai,Bj),(Ai,Bj), d(i-1,j)+1,d(i,j-1)+1 d(i-1,j)+1,d(i,j-1)+1 初始条件：初始条件：d(i,0)d(i,0)i,ii,i0 0m m； d(O,j) d(