资源描述：
《算法课件(七)动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、动态规划法1内容（一）动态规划基础斐波那契数列：重复子问题数塔问题：记忆化搜索和递推的方法多段图问题：无后效性和最优化原理动态规划的思想和概念（二）动态规划典型实例矩阵连乘，最长子串，TSP，背包，流水线调度2动态规划基础3例1.斐波那契数列问题递归求解重复/叠子问题longintFib_rec(inth)//递归{num++;if(h==1
2、
3、h==2){return1;}elsereturn(Fib_rec(h-1)+Fib_rec(h-2));}4方法1：记忆化搜索intfi[n];intFib_memo(intn)
4、//记忆化搜索{if(n==0
5、
6、n==1)returnfi[n]=n;elseif(fi[n]!=0)returnfi[n];returnfi[n]=Fib_memo(n-1)+Fib_memo(n-2);}5方法2：递推longintFib_ita(inth)//递推{inti,f1,f2,f3;f1=1;f2=1;for(i=3;i<=h;i++){f3=f1+f2;f1=f2;f2=f3;}return(f2);}6例2.数塔问题有如图所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要
7、求找出一条路径，使路径上的数值和最大。7方法1：贪心算法贪心策略？是否满足贪心选择性质？是否满足最优子结构性质？反例：9-15-8-9-16（57）9-12-10-18-9（58）91215106821895197104168方法2：递归枚举最保险的思路，列举出所有可能的路径再比较，得出和最大的路径。9121510682189519710416如何递归？使问题向边界条件转化的规则(递归定义)。递归边界条件；9从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来
8、了才能作出决策。同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。10inta[100][100];//下三角形存放数据intmax(inti,intj,intn)//递归函数{intleft,right;if(i==n)//到达底层returna[i][j];left=max(i+1,j,n);//左边right=max(i+1,j+1,n);//右边return(left>right)?(left+a[i][j]):(right+a[i][j]);}ma
9、x(1,1,n)max(2,1,n)max(2,2,n)max(3,1,n)max(3,2,n)………………9121510682189519710416重叠子问题：计算了两次18的最大路径。11方法3：记忆化搜索inta[100][100],f[100][100];intmax(inti,intj,intn){intleft,right;if((i==n)
10、
11、(j==n))f[i][j]=a[i][j];if(f[i][j]!=-1)returnf[i][j];left=max(i+1,j,n);//左边right=max
12、(i+1,j+1,n);//右边return(f[i][j]=(left>right)?(left+a[i][j]):(right+a[i][j]));}算法改进：存储中间计算结果。该动态规划算法递归实现——记忆化搜索。12方法4：递推法intmax_ita(intn){for(inti=N-1;i>=1;i--){for(intj=1;j<=i;j++){a[i][j]+=(a[i+1][j]>=a[i+1][j+1])?(a[i+1][j]):(a[i+1][j+1]);}}returna[1][1];}13计算过程：
13、动态规划912 1510 6 82 18 9 519 7 10 4 16阶段5阶段4阶段3阶段2(21)(28)(19)(21)(38)(34)(29)(50)(49)(59)决策决策决策决策阶段1595049383429212819211971041614动态规划基础（一）动态规划的基本思想重叠子问题：由于动态规划的问题有重叠子问题的特点，为了减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。多阶段决策：把求解的问题分成许多阶段或多个子问题，然后按顺
14、序求解各子问题，最后一个子问题就是初始问题的解（递推求解）。15动态规划基础（二）适用动态规划方法的前提条件动态规划算法的问题及决策应该具有两个性质：最优化原理(或称为最佳原则、最优子结构)、无后向性。无后向性(无后效性)：某阶段状态一旦确定以后，就不受这个状态以后决策的影响。即某状态以后的过程不会影响
