动态规划(第7章)ppt课件.ppt

《动态规划(第7章)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/9/9AlgorithmsDesignTechniquesandAnalysis算法设计技巧与分析0华南师范大学计算机学院2021/9/9华南师范大学计算机学院1第七章动态规划动态规划的基本模式7.1引言7.2最长公共子序列问题7.3矩阵链乘7.4动态规划的基本模式应用7.5所有点对间的最短路问题7.60-1背包问题2021/9/9华南师范大学计算机学院27.1引言问题1：计算Fibonaccisequence:f(n)=f(n-1)+f(n-2),n>2;f(1)=1,f(2)=1.算法1（直接递归法）2021/9

2、/9华南师范大学计算机学院37.1引言根据递推公式，当n很大时，其时间时间复杂度分析：O(1.618n)(见例2.20)。也就是，计算f(n)所需要的运行时间对于n的值是指数的。该算法的特点：子问题的求解有大量的重复时间复杂度分析：O(1.618n)2021/9/9华南师范大学计算机学院4算法2（备忘录方法）算法特点：从上到下计算子问题，每个子问题只计算一次时间复杂度分析：O(n)int fibonacci(Integer n){if(list.get(n-1)!=0){return list.get(n-1);       

3、   }list.add(n-1,fibonacci(n-1)+fibonacci(n-2));return list.get(n-1);}7.1引言2021/9/9华南师范大学计算机学院5算法3（动态规划法）算法特点：从下到上计算子问题，每个子问题只计算一次时间复杂度分析：O(n)for(int i=2;i<=n;i++){result = f1 + f2;f1 = f2;f2 = result;}7.1引言2021/9/9华南师范大学计算机学院6问题2：计算二项式系数Cnk。算法1——直接递归计算算法特点：有大量的重复计算

4、7.1引言2021/9/9华南师范大学计算机学院7问题2：计算二项式系数Cnk。算法2算法特点：用帕斯卡三角从下到上来计算，每个子问题只算一次。即可以用下列填矩阵的方式求出C(n，k)。7.1引言2021/9/9华南师范大学计算机学院8算法复杂度大概的估计一下，只填了下三角矩阵，算法复杂度大概的估计一下，只填了下三角矩阵，为n*k/2=n*k，具体的次数为：为n*k/2=n*k，具体的次数为：7.1引言2021/9/9华南师范大学计算机学院9算法伪代码第一个for是控制行的，要填到第n行。第二个for来控制每行填到哪的，到i和

5、k的较小值。从这2个for也可以看出复杂度为n*k。7.1引言2021/9/9华南师范大学计算机学院107.2最长公共子序列问题问题给定某字母表上的两个长度分别为n和m的串A和B,要求确定A和B的最长公共子序列的长度。穷举法2021/9/9华南师范大学计算机学院11动态规划算法命题7.1设L(i,j)表示A=a1a2…ai和B=b1b2…bj的最长公共子序列的长度。则L(i,0)=0L(0,j)=0ifai=bj,L(i,j)=L(i-1,j-1)+1ifaibj，L(i,j)=max{L(i-1,j),L(i,j-1)}

6、其中，1in,1jn.7.2最长公共子序列问题Algorithm7.1LCS7.2最长公共子序列问题122021/9/9华南师范大学计算机学院137.2最长公共子序列问题2021/9/9华南师范大学计算机学院147.2最长公共子序列问题2021/9/9华南师范大学计算机学院157.3矩阵链乘问题求对n个矩阵进行连乘积M1M2…Mn的最小乘法次数。2021/9/9华南师范大学计算机学院167.3矩阵链乘穷举法2021/9/9华南师范大学计算机学院177.3矩阵链乘2021/9/9华南师范大学计算机学院187.3矩阵链乘动

7、态规划算法设C(i,j)表示求MiMi+1…Mj的最少乘法次数。则C(i,i)=0ifij，C(i,j)=mini

8、227.3矩阵链乘2021/9/9华南师范大学计算机学院237.3矩阵链乘2021/9/9华南师范大学计算机学院247.3矩阵链乘2021/9/9华南师范大学计算机学院25时间复杂度——定理7.27.3矩阵链乘2021/9/9华南师范大学计算机学院26适用范围多阶段决策的最优