动态规划入门.ppt

《动态规划入门.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、动态规划入门晋江市养正中学张昱峥三角形的行数大于1小于等于100，数字为0-99例题一、数字三角形738810274445265在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。输入格式：5//三角形行数。下面是三角形738810274445265要求输出最大和解题思路：用二维数组存放数字三角形。D(r,j):第r行第j个数字(r,j从1开始算)MaxSum(r,j):从D(r,j)到底边的各条

2、路径中，最佳路径的数字之和。问题：求MaxSum(1,1)典型的递归问题。D(r,j)出发，下一步只能走D(r+1,j)或者D(r+1,j+1)。故对于N行的三角形：if(r==N)MaxSum(r,j)=D(r,j)elseMaxSum(r,j)=Max{MaxSum(r＋1,j),MaxSum(r+1,j+1)}+D(r,j)intD[MAX][MAX];intn;intMaxSum(inti,intj){if(i==n)returnD[i][j];intx=MaxSum(i+1,j);inty=M

3、axSum(i+1,j+1);returnmax(x,y)+D[i][j];}数字三角形的递归程序:#include#include#defineMAX101usingnamespacestd;intmain(){inti,j;cin>>n;for(i=1;i<=n;i++)for(j=1;j<=i;j++)cin>>D[i][j];cout<

4、6451如果采用递规的方法，深度遍历每条路径，存在大量重复计算。则时间复杂度为2n,对于n=100行，肯定超时。如果每算出一个MaxSum(r,j)就保存起来，下次用到其值的时候直接取用，则可免去重复计算。那么可以用O(n2)时间完成计算。因为三角形的数字总数是n(n+1)/2改进数字三角形的记忆递归型动归程序：#include#includeusingnamespacestd;#defineMAX101intD[MAX][MAX];intn;intmaxSum

5、[MAX][MAX];intMaxSum(inti,intj){if(maxSum[i][j]!=-1)returnmaxSum[i][j];if(i==n)maxSum[i][j]=D[i][j];else{intx=MaxSum(i+1,j);inty=MaxSum(i+1,j+1);maxSum[i][j]=max(x,y)+D[i][j];}returnmaxSum[i][j];}intmain(){inti,j;cin>>n;for(i=1;i<=n;i++)for(j=1;j<=i;j++)

6、{cin>>D[i][j];maxSum[i][j]=-1;}cout<

7、38810274445265递归转成递推201310712101045265738810274445265递归转成递推302321201310712101045265738810274445265递归转成递推#include#includeusingnamespacestd;#defineMAX101intD[MAX][MAX];intn;intmaxSum[MAX][MAX];intmain(){inti,j;cin>>n;for(i=1;i<=n;i++)f

8、or(j=1;j<=i;j++)cin>>D[i][j];for(inti=1;i<=n;++i)maxSum[n][i]=D[n][i];for(inti=n-1;i>=1;--i)for(intj=1;j<=i;++j)maxSum[i][j]=max(maxSum[i+1][j],maxSum[i+1][j+1])+D[i][j]cout<