资料课件讲义动态规划

1、动态规划小组15级成员楚东方本PPT为思维导向PPT，具体内容详见：/chudongfang2015/article/details/51590817个人对动态规划的理解： 1.动态规划是一个付出额外空间来节省时间，就是所谓的空间换时间。 2.动态规划储存每个状态的最优解。 3.动态规划是用来把子问题的结果储存下来，再次用到的时候就不必再进行重复计算。算法导论对动态规划的解释：动态规划和分治方法相似，都是通过组合子问题的解来求解原问题， 分治方法将问题划分为互不相交的子问题，递归的求解子问题，再将他们的解组合起来，求出原问题的解。与之相态规划应用于子问题重

2、叠的情况，在这种情况下，分治会做许多不必要的工作，它会反复地求解那些公共大子问题，而动态规划算法对每个问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子问题都重新计算，避免了这种不必要的计算工作，这也就是为什么其可以提高效率的原因。前导题一钢条切割问题Serling公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,，单位为美元)。钢条的长度均为整英寸。图15-1给出了一个价格表的样例。钢条切割问题是这样的：给定一段长度为n英寸的钢条和一个价格表pi(i=1

3、,2,n)，求切割钢条方案，使得销售收益rn最大。注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。动态规划原理给出应用动态规划的四个步骤：1刻画一个最优解的结构特征。234递归地定义最优解的值。计算最优解的值，通常采用自底而上的方法。利用计算出的信息构造一个最优解。前导题二矩阵链乘法矩阵链乘法问题可以表述如下：给定n个矩阵构成的一个链（A1*A2*A3*An），其中i=1,2,n,矩阵Ai的维数为p(i-1)*p(i),对于乘积A1*A2*A3*An以一种最小化标量乘法次数的方式进行加括号。所谓矩阵链乘法是指当一些矩阵相乘时，如何加括号来改变乘法顺序从而来降低乘法次

4、数。例如有三个矩阵连乘：A1*A2*A3，其维数分别为：10*100，100*5，5*50. 如果按照（A1*A2）*A3）来计算的话，求（A1*A2）要10*100*5=5000次乘法，再乘以A3需要10*5*50=2500次乘法，因此总共需要7500次乘法。如果按照（A1*（A2*A3）来计算的话，求（A2*A3）要100*5*50=25000次乘法，再乘以A1需要10*100*50=50000次乘法，因此总共需要75000次乘法。可见，按不同的顺序计算，代价相差很大。动态规划原理动态规划主要包括以下的四个内容：1 最优子结构234重叠子问题重构最优解备忘最优子结构如果一个问题的最优解包含

5、了其子问题的最优解，我们就称此子问题具有最优子结构。最优子结构在贪心算法中和动态规划算法中体现较多，在动态规划中， 我们用子问题的最优解来构造原问题的最优解，因此我们必须小心确保考察了最优解中用到的所有子问题（只有这样才能算当前最优）前面两个例子都用到了最优子结构问题，你会发现在发掘最优子结构性质的过程中，实际上遵循如下模式： 1.证明最优解的第一个组成部分是做出一个选择，做出这个选择会产生一个或多个子问题。2.对于一个给定的问题，在其可能的一步选择中，你只是假定已经知道了这个选择（通过max或min遍历）3. 给定可获得最优解的选择后，你确定这次选择会产生哪些子问题，以及如何更好的刻画子问题

6、空间。4. 作为构成原问题的最优解组成部分，每个子问题的解就是它本身的最优解。重叠子问题 适合用动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须满足足够“小”，即问题的递归算反复地求解相同的子问题，而不是一直生成新的子问题。一般来讲，不同问题的总数通常是输入规模的多项式函数为好。如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题性质。与之相对，适合用分治方法求解的问题通常在递归的每一步都生成全新的子问题。动态规划算法通常利用重叠子问题性质，对每个子问题求解一次，经解存入一个表中，当再次需要这个子问题时直接查表， 每次查表的代价为时间常量。重构最优解 从实际考虑，

7、我们通常将每个子问题所做的选择存在一个表 中，这样就不必根据代价值来重构这些信息。对于矩阵链乘法， 如果用sij记录了子问题的最优代价，其重构每次选择只需O(1)，否则其需要w(1)时间。 备忘思路就是对自然但低效的递归算法加入备忘机制。与自底而上方法一样，我们维护一个表记录子问题的解，但仍保持递归算法的控制流程。带备忘的递归算法为每个子问题维护一个表项来保存它的解。每个表项的初值设为一个特殊值，表示尚未填入子问题的解。当递归调用过程中第一次遇到子问题时，计算其解，并存入表项。随后每次遇到同一个子问题，只是简单的查表，返回其解。例题一：最长公共子序列问题介绍：给定两个序列X=x1,x2,x3,x4xm,和Y=y1,y2,y3,y4,y5yn.求X和Y长度最长的公共子序列。简称LCS例题二：图论的最短路径算法：Floy算法求图任意两点间的最短路径例题三：经典问题：石子归并有n堆石子排成一列，每堆石子有一个重量wi, 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和wi+wi+1。问安排怎样的合并顺序，能够使得总合