《数学动态规划》PPT课件.ppt

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

1、递归和动态规划内容提要递归：（1）将原问题分解为更小规模的同类问题（2）结束条件#include"stdio.h"intfactorial(intn){if(n<=0)return(-1);if(n==1)return(1);elsereturnn*factorial(n-1);}intmain(intargc,char*argv[]){printf("%d",factorial(5));getchar();return0;}f(5)f(4)f(3)f(2)f(1)线性的f(x)->g(f(x-x’))每个f(x-x’)只计算一次。树形递归例８：POJ2753Fi

2、bonacci数列1，1，…，f(n-1)+f(n-2),…intf(intn){if(n==0

3、

4、n==1)returnn;returnf(n-1)+f(n-2);}树形递归f(5)f(3)f(2)f(1)f(2)f(4)f(0)f(1)f(0)f(3)f(2)f(1)f(1)f(0)f(1)11001010冗余计算例８：POJ2753Fibonacci数列计算过程中存在冗余计算，为了出去冗余计算可以从已知条件开始计算，并记录计算过程中的中间结果。f(1)1动态规划例８：POJ2753Fibonacci数列intf[n+1];f[1]=f[2]=1;intI;for

5、(i=3;i<=n;i++)f[i]=f[i-1]+f[i-2];cout<

6、10274445265输入格式：//三角形行数。下面是三角形738810274445265要求输出最大和算法一：递归的想法设f(i,j)为三角形上从点(i,j)出发向下走的最长路经，则f(i,j)=max(f(i+1,j),f(i+1,j+1))+d[i][j]要输出的就是f(1，1,)即从最上面一点出发的最长路经。代码如下：intn;intelem[101][101];intMaxSum(introw,intcol){if(row==n)returnelem[row][col];//intnSum1=MaxSum[row+1][col];//intnsum2=Max

7、Sum[row+1][col+1];if(MaxSum(row+1,col)>=MaxSum(row+1,col+1))returnMaxSum(row+1,col)+elem[row][col];elsereturnMaxSum(row+1,col+1)+elem[row][col];}intmain(intargc,char*argv[]){scanf("%d",&n);inti,j;for(i=1;i<=n;i++)for(j=1;j<=i;j++)scanf("%d",&elem[i][j]);printf("%d",MaxSum(1,1));getcha

8、r();return0;}超时73881027444526557388102744452653023212013107121010452651201121121221331231464124解决重复计算的方法：将中间计算结果保存起来，从而不必每次都递归计算。每个结点只计算一次总计算次数=1+2+3+…+n#include"stdio.h"#include"memory.h"intn;intelem[101][101];intaMaxSum[101][101];intMaxSum(introw,intcol){if(row==n)returnelem[row][col]

9、;if(aMaxSum[row+1][col]==-1)aMaxSum[row+1][col]=MaxSum(row+1,col);if(aMaxSum[row+1][col+1]==-1)aMaxSum[row+1][col+1]=MaxSum(row+1,col);//intnSum1=MaxSum[row+1][col];//intnsum2=MaxSum[row+1][col+1];if(MaxSum(row+1,col)>=MaxSum(row+1,col+1))returnMaxSum(row+1,col)+elem[row][col];