动态规划算法应用及其优化---毕业论文

本 科 毕 业 论 文 动态规划算法应用及其优化The Practice And Optimize Of Dynamic Programming Algorithm姓 名：学 号：学院：软件学院系：软件工程专 业：软件工程年 级：指导教师： 年 月摘要动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。它建立在最优原则的基础上,是基本算法中设计难度相当大的一种。采用动态规划方法，可以高效地解决许多用贪婪算法或分治算法无法解决的问题，是信息学竞赛选手必须熟练掌握的一种算法,以其多元性广受出题者的喜爱。动态规划算法没有一个固定的解题模式，技巧性很强。涉及优化问题，一般都离不开动态规划，然而因为在程序算法中动态规划属于最难理解的算法之列，这也使得许多人对此望而却步。本文从数字三角形问题入手，逐步深入动态规划算法。介绍了该算法的理论基础，基本概念，涉及领域和解题步骤。通过矩阵连乘，炮弹拦截，最长单调上升子序列等实际问题的讨论，探讨动态规划的基本思想。同时本文还对两个与动态规划有密切联系的其他方法进行了比较。在对该算法的基本问题比较全面的论述后，本文接着探讨了动态规划算法的优化。从三个方面讨论了动态规划算法时间复杂度的优化，从两个实例讨论了动态规划算法空间复杂度的优化。关键词：动态规划；备忘录方法；算法优化AbstractDynamic programming is a branch of operational research. It is the mathematical method for solving the optimization decision-making process. It is the one that very difficult to design in the basic algorithms. It is built on the basis of optimization principle. By the dynamic programming, we can solve many problem, which cant solve by the greedy algorithm or divide and rule algorithm, elegantly and effectively. It is the algorithm that players must master in the competition. It is popular with the examiners for its diversity. Dynamic programming algorithm does not have a fixed problem-solving mode. It is Skillful. Optimization problems generally are solved by the dynamic programming. But many people do not have the courage to learn dynamic programming algorithm because it is the most difficult algorithm.This article discussed the dynamic programming algorithm step by step started from the question of the number-triangle, and introduced its theory, domain, conception and steps to use. It explored the basic idea of dynamic programming through the matrix chain problem and missile intercepting problem. At the same time, this article compared two other algorithms similar to the dynamic programming algorithm.Then this article discussed how to optimize the dynamic programming algorithm. It discussed how to optimize the time complexity from three aspects and how to optimize the space complexity from two aspects.Key words: dynamic programming; memorandum; optimize algorithm 目录第一章问题的引入11.1问题描述11.2穷举搜索法解题1第二章初识动态规划42.1分析最优解的性质42.2递归地定义最优值52.3计算最优值52.4构造最优解8第三章从理论角度看动态规划93.1最优化原理93.2基本术语103.3动态规划的基本思想113.4动态规划问题的特征113.5动态规划基本步骤12第四章从应用角度看动态规划134.1矩阵连乘问题134.1.1问题描述134.1.2最优解的性质144.1.3递归定义最优值154.1.4计算最优值154.1.5构造最优解174.2导弹拦截问题174.2.1问题描述174.2.2 最优子结构性质184.2.3 递归的定义最优值184.2.4 计算最优解194.2.5 构造最优解20第五章动态规划与其它算法比较215.1动态规划与搜索算法215.2动态规划与备忘录方法22第六章动态规划算法的优化256.1 动态规划时间优化256.1.1 减少状态总数256.1.2减少每个状态转移的状态数286.1.3减少状态转移的时间306.2 动态规划空间优化326.2.1 最长公共子序列问题空间优化326.6.2 数字三角形问题空间优化35第七章总结36致谢37参考文献38ContentChapter 1Introduction11.1Question11.2Frist answer1Chapter 2Understand dynamic programming42.1The nature of the optimal solution42.2Optimal value52.3Get optimal value52.4Get optimal solution8Chapter 3 Theory Of Dynamic programming93.1Optimization Principle93.2Terms103.3The basic idea113.4Features113.5Steps12Chapter 4 Practice Of Dynamic programming134.1 Matrix chain problem134.1.1 Question134.1.2 The nature of the optimal solution144.1.3 Optimal value154.1.4 Get optimal value154.1.5 Get optimal solution174.2 Missile intercepting problem174.2.1 Question174.2.2 The nature of the optimal solution184.2.3 Optimal value184.2.4 Get optimal value194.2.5 Get optimal solution20Chapter 5 Compare215.1 Compare to search algorithm215.2 Compare to memorandum algorithm22Chapter 6 Optimize The Dynamic Programming256.1 Optimize the time complexity256.1.1Reduce the state256.1.2 Reduce the state transition286.1.3 Reduce the time of state transition306.2 Optimize the space complexity326.2.1 Example 1326.6.2 Example 235Chapter 7 Summarize36Acknowledgement37References38动态规划算法应用及其规划第一章 问题的引入天才设题，智者解题 对于绝大多数没有数据结构和算法知识的编程人员，穷举搜索法经常成了克敌制胜的关键法宝，它也似乎是可以解决一切问题的万能钥匙。如今计算机的处理器不是号称一秒钟可以处理好多亿条指令，那么穷举搜索法好像是没有什么好担心的了。事实真的如此吗，先来看看下面这个例子。1.1问题描述如下所示为一个数字三角形：73 88 1 02 7 4 44 5 2 6 5请编写一个程序计算从顶至底的某一条路径，使该路径所经过的数字的总和最大，要求满足一下三个条件：每一步可沿直线向下或右斜线向下走；1 = 三角形行数 = 100；三角形中的数字为整数0，1，99。1.2穷举搜索法解题分析上面的题目，要计算所有路径中所经过数字总和最大的路径，那么可以穷举出所有可能的路径，然后从中选出总和最大的路径。要怎么实现对所有路径的穷举呢，使用深度搜索可以很好的完成任务。用搜索法写出如下的算法程序：/参数：i，路径起始位置所在的行。j，路径起始位置所在的列。/ n，三角形的总行数。triangle，存储三角形的二维数组。int maxPath(int i, int j, int n, int* triangle)int iMax1, iMax2;if (i = n)return triangleij;elseiMax1 = maxPath(i + 1, j, n, triangle);iMax2 = maxPath(i + 1, j + 1, n, triangle);if (iMax1 iMax2)return iMax2 + triangleij;return iMax1 + triangleij;接下来，对上面的算法进行数据规模测试，记录下该算法对于不同数据规模（在此表现为n值的大小）运行所需要的时间，如表1-1所示：表1-1：递归搜索法的运行时间测试数据规模(n)=2324252627282930运行时间(s)= 1136132860122从上表可以看出，当n大于25时，运行所需时间就超过1秒，并且随着n的增长而迅速增长（实际上是按所需时间随指数增长）。所以，即使你所使用的电脑性能确实比上面的测试机好上好几倍，也解决不了问题。再看看题目的数据规模(n值)是100，而搜索算法只能解决n24的数据规模(相信你也忍受不了运行好几秒甚至几十秒才出来的结果吧)。分析上面算法，算法进行了很多重复的运算，例如第三行的第二个数，在计算第二行第一个数时调用计算了一次，计算第二行第二个数时又调用计算了一次，共调用计算了2次。同样道理，得出各行数据调用运算的次数如下：11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1 上面的调用运算次数实际上是一个杨辉三角。大量重复的运算使得搜索算法的时间复杂度随指数增长，导致运算时间严重超标。穷举搜索法不再是万能钥匙了，那么有没有什么办法解决这个问题呢，或是应该采用更加先进的算法?第二章 初识动态规划山穷水复疑无路 柳暗花明又一村下面用动态规划的方法来解决上面的题目。首先，在这里把设计一个动态规划算法的基本步骤罗列出来1：1、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值；4、根据计算最优值时得到的信息，构造一个最优解。2.1分析最优解的性质设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解结构特征。为了方便阐述，将从三角形上某个点(i, j)出发到达三角形底边的某条特定路径记为pathi:j，三角形上一行中可以到达点(i, j)的点可能有(i -1, j) 和(i - 1, j - 1)，其路径可以记为pathi -1:j 和pathi - 1:j - 1。这两条路径的数值和只要相应的加上所在点的整数即可。该问题的一个关键特征是：若从三角形某一个点(i, j)出发到达三角形底边的某条路径满足了其上数值之和为所有从该点出发到达底边的路径中最大的(简单地描述为该路径是最优的)，那么去掉点(i, j)得到的子路径也同样是最优的。否则，假设有一条其他的子路径更优，即其和更大，那么它再加上点(i, j)的整数，其和比上面的到(i, j)的路径还大，这与上面提到的路径是最优的是矛盾的。因此，该问题的最优解包含了其子问题的最优解，这种性质称为最优子结构性质。一个问题的最优子结构性质是该问题可用动态规划算法求解的最显著特征。2.2递归地定义最优值设计一个动态规划算法的第二步是递归的定义最优值。在该问题中设所有从点(i, j)到三角形底边的路径path(i, j)中最优路径的和值(最优值)为mij；则mnj就等于点(i, j)的整数值，mij(i != n)则可能是由mi + 1j加上点(i, j)的整数得到，或是由mi + 1j +1加上点(i, j)的整数得到，所以可以写出下面的递归式：mij=trianglenj i=nmaxmi+1j, mi+1j+1+triangleij in通过上式，只要给mij带入(0, 0)这个点，既是求解从顶点出发到三角形底边的最优值。mij给出了问题的最有值，如果还需要构造问题的最优解，即是要知道取得最优值的路径，那么可以增加一个数组sij来记录在每一点处最优路径选择的是下方的点(用0标识)还是右下方的点(用1标识)。然后即可根据sij来构造最优解。2.3计算最优值 在第一章中利用上面的递归式写出了问题的递归算法，同时也看到简单的递归运算耗费了指数计算时间。然而注意到在递归计算过程中不同的子问题只有(n2)个。在递归搜索算法中很多子问题被重复计算了多次，这同时也是该问题可以用动态规划算法来计算的又一显著特征。有了上面mij的递归式，现在以自底向上的方式来计算问题的最优值，在计算过程中保存已解决子问题的答案，每个子问题只计算一次，而在后面需要时只需简单的查一下，从而避免的大量的重复计算，最终得到多项式时间的算法。下面给出数字三角形的动态规划算法。/参数：n，三角形的总行数。triangle，存储三角形的二维数组。/ m，子问题最优值数组。s，构造最优解用到的数组。void maxPath2(int n, int* triangle, int* m, int* s)for (int i=0; i=0; row-)for (int col=0; col trianglerow+1col+1)mrowcol = mrow + 1col + trianglerowcol;srowcol = 0;elsemrowcol += mrow + 1col + 1 + trianglerowcol; srowcol = 1;问题的最优值存储在m00中。对于题目中一开始的数字三角形，算法maxPath2计算mij的先后次序如图2-1所示：图2-1：mij计算次序mij的计算结果如表2-1所示：表2-1：mij计算结果0123403012319220131037121010445265sij的计算结果如表2-2所示：表2-2： sij的计算结果01234001002101310104-1-1-1-1-1由于算法的计算主要是在两个for循环中，故算法的时间复杂度为O(n2)。再次运行程序，会发现无论数据规模在100以内如何变化，程序的运行时间都不会超过1秒钟了。2.4构造最优解动态规划的前三个步骤是其解题的基本步骤，而若是同时需要求出问题的一个最优解，那么就需要执行第四个步骤。这里构造最优解只需按照数组s中的值逐步详细查找即可，在此不做详细讨论。第三章 从理论高度看动态规划会当凌绝顶，一览众山小在上两章中通过一个比较简单的例子，初步认识了动态规划的基本思想和解题步骤。下面将从理论的角度去研究它。3.1最优化原理1951年美国数学家R.Bellman等人，根据一类多阶段问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。一些静态模型，只要人为地引进“时间”因素，分成时段，就可以转化成多阶段的动态模型，用动态规划方法去处理。与此同时，他提出了解决这类问题的“最优化原理”(Principleofoptimality)：“一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略”。简言之，一个最优策略的子策略，对于它的初态和终态而言也必是最优的2。这个“最优化原理”如果用数学化一点的语言来描述的话，就是：假设为了解决某一优化问题，需要依次做出n个决策D1，D2，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 k n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，Dn也是最优的。最优化原理是动态规划的基础。任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划方法计算。能采用动态规划求解的问题都需要满足一定的条件3：(1) 问题中的状态必须满足最优化原理；(2) 问题中的状态必须满足无后效性。所谓的无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结”。3.2基本术语下面对最优化理论中提到的一些术语做一个阐述4：多阶段决策问题：在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要做出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图3-1所示： 图3-1：多阶段决策示例这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。很明显数字三角形问题就是这样一个多阶段决策问题。阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻做出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。在前面的例子中，第一个阶段就是三角形最下排的点到三角形底边，而第二个阶段就是次下排到三角形的底边，以此类推。状态：一般在动态规划的时候所用到的一些数组，也就是用来存储每个状态的最优值的。无后效性：要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。3.3动态规划的基本思想从上面的讨论中知道动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题(子策略)，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式5。3.4动态规划问题的特征那么具体来说什么样的问题能够采用动态规划来解决呢，这就是在数字三角形问题中已经提到过的动态规划问题所具有的特征6：1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质，也就是满足了最优化原理。 2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。如果问题本身满足了上面两个性质，就可以考虑用动态规划算法来解决这个问题。3.5动态规划基本步骤前面已经提到了动态规划设计的基本步骤，这里再次说明1： 找出最优解的性质，并刻画其结构特征； 递归地定义最优值（写出动态规划方程）； 以自底向上的方式计算出最优值； 根据计算最优值时得到的信息，构造一个最优解。步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。第四章 从应用角度看动态规划实践是检验真理的唯一标准通过简单的数字三角形问题的动态规划求解和对动态规划基本思想的了解，我们对动态规划有了一个初步的印象，下面再通过一些比较复杂而有意思的实例来加深对动态规划的理解。4.1矩阵连乘问题先来看一个动态规划里比较经典的一个问题。4.1.1问题描述给定n个矩阵A1，A2，An，其中Ai和Ai+1是可乘的(i=1, 2 , n-1)，要计算这n个矩阵的连乘积A1A2 , ,An。对于两个矩阵相乘可以采用下面的算法：/参数：a，b，相乘的两个矩阵。c，结果矩阵。/ ra，ca为a矩阵的行数和列数。rb，cb为b矩阵的行数和列数void matrixMultiply(int* a, int* b, int* c, int ra, int ca, int rb, int cb) for (int i=0; ira; i+) for (int j=0; jcb; j+)int sum = ai0 * b0j;for (int k=1; kca; k+)sum += aik * bkj;cij = sum; 上述算法的主要计算量在三重for循环中。对于可乘矩阵A和B，若A是一个p*q的矩阵，B是一个q*r 的矩阵，那么A，B相乘所需要的计算量就是pqr。如果矩阵的数量增加，会是什么样的情况呢。假设有ABC三个矩阵，这三个矩阵的位数分别是10*100，100*10，10*20。在有3个矩阵的时候可以选择两种计算结果的次序，即先计算AB，再与C向乘，或先计算BC再与A相乘。对应于第一种次序的计算量是10*100*10 + 10*10*20 = 12000次数乘，对应于第二种次序的计算量是10*100*20 + 100*10*20 = 40000次数乘。从上面的计算中容易看出：在矩阵连乘时，不同的计算次序决定了不同的计算量。那么自然地导出下面的问题：如何确定矩阵连乘的最优次序，以使整个连乘过程的计算量达到最小。在这里矩阵连乘的次序可以用加括号的方式来表示，如ABCD四个矩阵连乘的计算次序对应5种加括号方式：(A(BC)D)，(A(B(CD)， (AB)(CD)，(AB)C)D)，(A(BC)D)。下面用动态规划来求解这个问题：4.1.2最优解的性质将矩阵连乘积AiAi+1Aj简记为Ai：j。来看A1：n的一个最优次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1=kn，则完全加括号方式为(A1Ak)(Ak+1An)。以此次序，先分别计算A1：k和Ak+1：n，然后将计算结果相乘得到A1：n，总计算量为A1：k的计算量加上Ak+1：n的计算量，再加上A1：k和Ak+1：n相乘的计算量。来看看该问题是否满足最优化原理。计算A1：n的一个最优次序所包含的计算矩阵子链A1：k和Ak+1：n的次序也是最优的。事实上若有一个计算A1：k的次序需要的计算量更少，则用此次序替换原来计算A1：k的次序，得到计算A1：n的次序需要的计算量将比最优次序所需计算量更少，这是一个矛盾。同理知，计算A1：n的一个最有次序所包含的计算矩阵子链Ak+1：n的次序也是最优的。可见该问题可以使用动态规划求解。4.1.3递归定义最优值设计算Ai：j所需的最少数乘次数为mij，1 = i = j =n，则原问题的最优值为m1n。当i=j时，Ai：j为单一矩阵，无需计算，所以mii = 0。当i j时，若计算Ai：j的最优次序在Ak和Ak+1之间断开，则mii =mik + mk + 1j + pi-1pkpj(在这里用pi-1*pi表示矩阵Ai的维数)。由于在计算时并不知道断开点k的位置，所以k还未定。不过k的位置只有j i个可能，即i = k = j-1。因此，k是这j-i个位置中使计算量达到最小的那个位置。则mij可以递归的定义为：mij=0 i=jminikjmik+mk+1j+pi-1pkpj ij若将对应于mij的断开位置k记为sij，在计算出最优值mij后，可递归的有sij构造出相应的最优解。4.1.4计算最优值有了以上分析之后可以写出矩阵连乘次序问题的动态规划算法如下：/参数：p，数组p用于存储矩阵的维数p0，p1，.，pnvoid matrixMultiplyChain(int* p, int n, int* m, int* s)for (int i=1; i=n; i+)mii = 0;for (int r=2; r=n; r+)for (int i=1; i=n-r+1; i+)int j = i + r - 1;mij = mi+1j + pi-1*pi*pj;sij = i;for (int k=i+1; kj; k+)int t = mik + mk+1j + pi-1*pk*pj;if (t mij)mij = t;sij = k;矩阵乘法链问题计算最优值的顺序和数字三角形问题基本相似，但是列有不同，如图4-1所示：图4-1：mij计算次序4.1.5构造最优解下面根据求解最优值时sij记录的断开位置k构造一个最优解。void Traceback(int i, int j, int* s)if (i = j) return; Traceback(i, sij, s);Traceback(sij + 1, j, s);cout Multiply A i , sij;cout and A (sij + 1) , j endl;调用Traceback(1，n，s)就可以输出A1：n的一个最有计算次序。4.2导弹拦截问题4.2.1问题描述某国为了防御敌国的导弹袭击，发明出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），计算这套系统最多能拦截多少导弹，并依次输出被拦截的导弹飞来时候的高度。样例：INPUT 389 207 155 300 299 170 158 65 OUTPUT6（最多能拦截的导弹数）389 300 299 170 158 65因为只有一套导弹拦截系统，并且这套系统除了第一发炮弹能到达任意高度外，以后的每一发炮弹都不能高于前一发炮弹的高度；所以，被拦截的导弹应该按飞来的高度组成一个非递增序列。题目要求计算这套系统最多能拦截的导弹数，并依次输出被拦截导弹的高度，实际上就是要求在导弹依次飞来的高度序列中寻找一个最长非递增子序列7。4.2.2 最优子结构性质设X=x1,x2,xn为依次飞来的导弹序列，Y=y1,y2,yk为问题的最优解（即X的最长非递增子序列），s为问题的状态（表示导弹拦截系统当前发送炮弹能够到达的最大高度，初值为s=第一发炮弹能够到达任意的高度）。如果y1=x1，即飞来的第一枚导弹被成功拦截。那么，根据题意“每一发炮弹都不能高于前一发的高度”，问题的状态将由s=变成sx1（x1为第一枚导弹的高度）；在当前状态下，序列Y1=y2,yk也应该是序列X1=x2,xn的最长非递增子序列（用反证法很容易证明）。也就是说，在当前状态sx1下，问题的最优解Y所包含的子问题（序列X1）的解（序列Y1）也是最优的。这就是拦截导弹问题的最优子结构性质。4.2.3 递归的定义最优值设D(i)为第i枚导弹被拦截之后，这套系统最多还能拦截的导弹数（包含被拦截的第i枚）。可以设想，当系统拦截了第k枚导弹xk，而xk又是序列X=x1,x2,xn中的最小值，即第k枚导弹为所有飞来的导弹中高度最低的，则有D(k)=1；当系统拦截了最后一枚导弹xn，那么，系统最多也只能拦截这一枚导弹了，即D(n)=1；其它情况下，也应该有D(i)1。根据以上分析，可归纳出问题的动态规划递归方程为：Di= 1 i=nmaxik=n1,Dk+1 xixk假设系统最多能拦截的导弹数为dmax（即问题的最优值），则 dmax= D(i) （i为被系统拦截的第一枚导弹的顺序号）。4.2.4 计算最优解根据问题的动态规划递归方程，可以采用自底向上的方法依次计算出D(n-1)、D(n-2)、D(1)的值，算法代码如下：/参数：x，导弹高度序列。dmax，最优值。xh，第一枚被拦截导弹的序号。void headOff(int* d, int* x, int n, int dmax, int xh)int i;for (i=0; i=0; i-) for (int j=i+1; j=xj & didj+1)di = dj + 1; dmax = 0;xh = 1;for (i=0; i dmax)dmax = di;xh = i;4.2.5 构造最优解在计算最优值时保存了被拦截的第一枚导弹的顺序号xh。接下来通过这个信息构造问题的最优解（由所有被拦截的导弹的高度组成的非递增序列）。算法代码如下：void max(int xh, int* x, int* d, int n)cout xxh;for (int i=xh+1; in; i+)if (di=dxh-1 & xi=xxh)cout -1)return mij;if (i = n)return triangleij;elseiMax1 = maxPath(i + 1, j, n, triangle);iMax2 = maxPath(i + 1, j + 1, n, triangle);if (iMax1 iMax2)return iMax2 + triangleij;return iMax1 + triangleij;结合上面的算法，看看备忘录方法的主要特点： 用一个表格来保存已解决的子问题的答案(上面例子中的数组m)，用的时候查表即可。 采用的递归方式是自顶向下。 控制结构与直接递归相同，区别在于备忘录方式为每个解过的子问题建立备忘录。 初始化为每个子问题的记录存入一个特殊的值(上面例子中为-1)，表示并未求解。在求解过程中，查看相应记录如果是特殊值，表示未