程序设计实习讲义8

程序设计实习第八讲动态规划树形递归存在冗余计算例1：POJ2753Fibonacci数列求Fibonacci数列的第n项intf(intn){if(n==0||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冗余计算计算过程中存在冗余计算，为了除去冗余计算可以从已知条件开始计算，并记录计算过程中的中间结果。树形递归存在冗余计算去除冗余：intf[n+1];f[1]=f[2]=1;intI;for(i=3;i=n;i++)f[i]=f[i-1]+f[i-2];coutf[n]endl;用空间换时间-动态规划例2POJ1163数字三角形在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。三角形的行数大于1小于等于100，数字为0-99738810274445265输入格式：5//三角形行数。下面是三角形738810274445265要求输出最大和解题思路：以D(r,j)表示第r行第j个数字，以MaxSum(r,j)代表从第r行的第j个数字到底边的各条路径中，数字之和最大的那条路径的数字之和，则本题是要求MaxSum(0,0)。（假设行编号和一行内数字编号都从0开始)。典型的动态规划问题。从某个D(r,j)出发，显然下一步只能走D(r+1,j)或者D(r+1,j+1)，所以，对于N行的三角形：if(r==N-1)MaxSum(r,j)=D(N-1,j)elseMaxSum(r,j)=Max(MaxSum(r＋1,j),MaxSum(r+1,j+1))+D(r,j),#includeiostream.h#defineMAX101inttriangle[MAX][MAX];intn;intlongestPath(inti,intj);voidmain(){inti,j;cinn;for(i=0;in;i++)for(j=0;j=i;j++)cintriangle[i][j];coutlongestPath(0,0)endl;}数字三角形的递归程序：数字三角形的递归程序：intlongestPath(inti,intj){if(i==n)return0;intx=longestPath(i+1,j);inty=longestPath(i+1,j+1);if(xy)x=y;returnx+triangle[i][j];}超时！！为什么超时？回答：重复计算738810274445265如果采用递规的方法，深度遍历每条路径，存在大量重复计算。则时间复杂度为2n,对于n=100，肯定超时。改进思想：从下往上计算，对于每一点，只需要保留从下面来的路径中和最大的路径的和即可。因为在它上面的点只关心到达它的最大路径和，不关心它从那条路经上来的。解法1：如果每算出一个MaxSum(r,j)就保存起来，则可以用o(n2)时间完成计算。因为三角形的数字总数是n(n+1)/2此时需要的存储空间是：intD[100][100];//用于存储三角形中的数字intaMaxSum[100][100];//用于存储每个MaxSum(r,j)#defineMAX_NUM100intD[MAX_NUM+10][MAX_NUM+10];intN;intaMaxSum[MAX_NUM+10][MAX_NUM+10];main(){inti,j;scanf(%d,&N);for(i=1;i=N;i++)for(j=1;j=i;j++)scanf(%d,&D[i][j]);for(j=1;j=N;j++)aMaxSum[N][j]=D[N][j];for(i=N;i1;i--)for(j=1;ji;j++){if(aMaxSum[i][j]aMaxSum[i][j+1])aMaxSum[i-1][j]=aMaxSum[i][j]+D[i-1][j];elseaMaxSum[i-1][j]=aMaxSum[i][j+1]+D[i-1][j];}printf(%d,aMaxSum[1][1]);}解法2:没必要用二维Sum数组存储每一个MaxSum(r,j),只要从底层一行行向上递推，那么只要一维数组Sum[100]即可,即只要存储一行的MaxSum值就可以。比解法一改进之处在于节省空间，时间复杂度不变#defineMAX_NUM100intD[MAX_NUM+10][MAX_NUM+10];intN;intaMaxSum[MAX_NUM+10];main(){inti,j;scanf(%d,&N);for(i=1;i=N;i++)for(j=1;j=i;j++)scanf(%d,&D[i][j]);for(j=1;j=N;j++)aMaxSum[j]=D[N][j];for(i=N;i1;i--)for(j=1;ji;j++){if(aMaxSum[j]aMaxSum[j+1])aMaxSum[j]=aMaxSum[j]+D[i-1][j];elseaMaxSum[j]=aMaxSum[j+1]+D[i-1][j];}printf(%d,aMaxSum[1]);}递归到动规的一般转化方法原来递归函数有几个参数，就定义一个几维的数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值，这样就可以从边界开始，逐步填充数组，相当于计算递归函数值的逆过程。例题：最长上升子序列问题描述一个数的序列bi，当b1b2...bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,aN)，我们可以得到一些上升的子序列(ai1,ai2,...,aiK)，这里1=i1i2...iK=N。比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。这些子序列中最长的长度是4，比如子序列(1,3,5,8).你的任务，就是对于给定的序列，求出最长上升子序列的长度。输入数据输入的第一行是序列的长度N(1=N=1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。输出要求最长上升子序列的长度。输入样例71735948输出样例4解题思路1.找子问题经过分析，发现“求以ak（k=1,2,3…N）为终点的最长上升子序列的长度”是个好的子问题――这里把一个上升子序列中最右边的那个数，称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样，但是只要这N个子问题都解决了，那么这N个子问题的解中，最大的那个就是整个问题的解。2.确定状态：上所述的子问题只和一个变量相关，就是数字的位置。因此序列中数的位置k就是“状态”，而状态k对应的“值”，就是以ak做为“终点”的最长上升子序列的长度。这个问题的状态一共有N个。3.找出状态转移方程：状态定义出来后，转移方程就不难想了。假定MaxLen(k)表示以ak做为“终点”的最长上升子序列的长度，那么：MaxLen(1)=1MaxLen(k)=Max{MaxLen(i)：1ik且aiak且k≠1}+1这个状态转移方程的意思就是，MaxLen(k)的值，就是在ak左边，“终点”数值小于ak，且长度最大的那个上升子序列的长度再加1。因为ak左边任何“终点”小于ak的子序列，加上ak后就能形成一个更长的上升子序列。实际实现的时候，可以不必编写递归函数，因为从MaxLen(1)就能推算出MaxLen(2)，有了MaxLen(1)和MaxLen(2)就能推算出MaxLen(3)……#includestdio.h#includememory.h#defineMAX_N1000intb[MAX_N+10];intaMaxLen[MAX_N+10];main(){intN;scanf(%d,&N);for(inti=1;i=N;i++)scanf(%d,&b[i]);aMaxLen[1]=1;for(i=2;i=N;i++){//每次求以第i个数为终点的最长上升子序列的长度intnTmp=0;//记录满足条件的，第i个数左边的上升子序列的最大长度for(intj=1;ji;j++){//察看以第j个数为终点的最长上升子序列if(b[i]b[j]){if(nTmpaMaxLen[j])nTmp=aMaxLen[j];}}aMaxLen[i]=nTmp+1;}intnMax=-1;for(i=1;i=N;i++)if(nMaxaMaxLen[i])nMax=aMaxLen[i];printf(%d\n,nMax);}例题：Poj1458最长公共子序列给出两个字符串，求出这样的一个最长的公共子序列的长度：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。最长公共子序列SampleInputabcfbcabfcabprogrammingcontestabcdmnpSampleOutput420输入两个子串s1,s2,设MaxLen(i,j)表示:s1的左边i个字符形成的子串，与s2左边的j个字符形成的子串的最长公共子序列的长度MaxLen(i,j)就是本题的“状态”假定len1=strlen(s1),len2=strlen(s2）那么题目就是要求MaxLen(len1,len2)最长公共子序列显然：MaxLen(n,0)=0(n=0…len1）MaxLen(0,n)=0(n=0…len2）递推公式：if(s1[i-1]==s2[j-1])MaxLen(i,j)=MaxLen(i-1,j-1)+1;elseMaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j));最长公共子序列S1s1[i-1]S2s2[j-1]S1i-1S2j-1S1长度为iS2长度为jMaxLen(S1,S2)不会比MaxLen(S1,S2j-1)和MaxLen(S1i-1,S2)都大，也不会比两者中任何一个小#includeiostream.h#includestring.hcharsz1[1000];charsz2[1000];intanMaxLen[1000][1000];main(){while(cinsz1sz2){intnLength1=strlen(sz1);intnLength2=strlen(sz2);intnTmp;inti,j;for(i=0;i=nLength1;i++)anMaxLen[i][0]=0;for(j=0;j=nLength2;j++)anMaxLen[0][j]=0;for(i=1;i=nLength1;i++){for(j=1;j=nLength2;j++){if(sz1[i-1]==sz2[j-1])anMaxLen[i][j]=anMaxLen[i-1][j-1]+1;else{intnLen1=anMaxLen[i][j-1];intnLen2=anMaxLen[i-1][j];if(nLen1nLen2)anMaxLen[i][j]=nLen1;elseanMaxLen[i][j]=nLen2;}}}coutanMaxLen[nLength1][nLength2]endl;}}活学活用掌握递归和动态规划的思想，解决问题时灵活应用例题：POJ1661HelpJimmyHelpJimmy是在下图所示的场景上完成的游戏：场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落