程序设计-动态规划PPT课件.ppt

程序设计-动态规划例1:POJ2753Fibonacci数列如何去除冗余——动态规划例2POJ1163数字三角形输入格式:第一行是三角形行数,下面是三角形。
5
7
38
810
2744
45265

输出:要求输出最大和。
解题思路
D(r,j):表示第r行第j个数字;
MaxSum(r,j):表示从D(r,j)到底边的各条路径中,数字之和最大的那条路径的数字之和;
本题目标是求:MaxSum(0,0)。
从某个D(r,j)出发,下一步只能走D(r+1,j)或者
D(r+1,j+1)。所以,对于N行的三角形,可以得到递推公式:#include<iostream.h>
#defineMAX101
inttriangle[MAX][MAX];
intn;
intlongestPath(inti,intj);
voidmain(){
inti,j;
cin>>n;
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
cin>>triangle[i][j];
cout<<longestPath(0,0)<<endl;
}intlongestPath(inti,intj){
if(i==n)
return0;
intx=longestPath(i+1,j);
inty=longestPath(i+1,j+1);if(x<y)
x=y;returnx+triangle[i][j];
}
超时！！为什么超时？从下往上计算,对于每一点,需要保留从底边上来到此点的路径中和最大的路径的和。
解法
每算出一个MaxSum(r,j)就保存起来。
可以用o(n^2)时间完成计算。因为三角形的数字总数是n(n+1)/2。
此时需要的存储空间是:
intD[100][100];//用于存储三角形中的数字
intaMaxSum[100][100];//用于存储每个MaxSum(r,j)#defineMAX_NUM100
intD[MAX_NUM+10][MAX_NUM+10];intN;
intaMaxSum[MAX_NUM+10][MAX_NUM+10];
main(){
inti,j;
scanf("%d",&N);
for(i=0;i<N;i++)
for(j=0;j<i;j++)
scanf("%d",&D[i][j]);
for(j=0;j<N;j++)
aMaxSum[N-1][j]=D[N-1][j];
for(i=N-1;i>0;i--)
for(j=0;j<i;j++){
if(aMaxSum[i][j]>aMaxSum[i][j+1])
aMaxSum[i-1][j]=aMaxSum[i][j]+D[i-1][j];
else
aMaxSum[i-1][j]=aMaxSum[i][j+1]+D[i-1][j];
}
printf("%d",aMaxSum[0][0]);
}解法2

没必要用二维Sum数组存储每一个MaxSum(r,j),只要从底层一行行向上递推,那么只要一维数组Sum[100]即可,即只要存储一行的MaxSum值就可以。
比解法一改进之处在于节省空间,时间复杂度不变。#defineMAX_NUM100
intD[MAX_NUM+10][MAX_NUM+10];intN;
intaMaxSum[MAX_NUM+10];
main(){
inti,j;
scanf("%d",&N);
for(i=0;i<N;i++)
for(j=0;j<i;j++)
scanf("%d",&D[i][j]);
for(j=0;j<N;j++)
aMaxSum[j]=D[N-1][j];
for(i=N-1;i>0;i--)
for(j=0;j<i;j++){
if(aMaxSum[j]>aMaxSum[j+1])
aMaxSum[j]=aMaxSum[j]+D[i-1][j];
else
aMaxSum[j]=aMaxSum[j+1]+D[i-1][j];
}
printf("%d",aMaxSum[1]);
}递归到动态规化的一般转化方法例题:最长上升子序列
一个数的序列bi,当b1<b2<...<bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,aN),我们可以得到一些上升的子序列(ai1,ai2,...,aiK),其中1<=i1<i2<...<iK<=N。
比如,对于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等等。这些子序列中最长的长度是4,比如子序列(1,3,5,8)。
你的任务,就是对于给定的序列,求