3北京大学程序设计实习课程

《程序设计实习》课程(C++ProgrammingPractice)程序设计实习第九讲动态规划主讲教师：田永鸿[e-mail]://idm.pku.edu.cn/jiaoxue-CPP/cpp08.htm2008年3月24日北京大学《程序设计实习》课程2内容提要为什么要用动态规划的方法递归程序转化为动态规划程序例题作业北京大学《程序设计实习》课程3树形递归例1：POJ2753Fibonacci数列1，1，…，f(n-1)+f(n-2),…intf(intn){if(n==0||n==1)returnn;returnf(n-1)+f(n-2);}北京大学《程序设计实习》课程4f(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数列计算过程中存在冗余计算，为了除去冗余计算可以从已知条件开始计算，并记录计算过程中的中间结果。北京大学《程序设计实习》课程5POJ2753Fibonacci数列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;用空间换时间-动态规划北京大学《程序设计实习》课程6什么是动态规划？动态规划是求解包含重叠子问题的最优化方法基本思想：将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解（注意：不是简单分而治之）。只能应用于有最优子结构的问题（即局部最优解能决定全局最优解，或问题能分解成子问题来求解）。计算机科学与工程、管理科学（运筹学）等领域中许多算法的基础，如最短路径、背包问题、项目管理、网络流优化等。北京大学《程序设计实习》课程7什么是动态规划？动态规划的性质最优化子结构性质。若问题的最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构性质（即满足最优化原理）能用动态规划解决的求最优解问题，必须满足最优解的每个局部也都是最优的子问题重叠性质。在用递归算法自顶向下对问题进行求解是，每次产生的子问题并不总是新问题，有些子问题可能被重复计算多次。动态规划算法利用此性质，对每个子问题只计算一次，然后将其结果保存起来以便高效重用。动态规划的实质就是北京大学《程序设计实习》课程8动规的要诀－状态用动态规划解题，关键是要找出“状态”，和在“状态”间进行转移的办法（即状态转移方程）我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。北京大学《程序设计实习》课程9动态规划例2POJ1163数字三角形在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。三角形的行数大于1小于等于100数字为0-99738810274445265北京大学《程序设计实习》课程10POJ1163输入格式：5//三角形行数。下面是三角形738810274445265要求输出最大和北京大学《程序设计实习》课程11解题思路算法一：递归的想法设f(i,j)为三角形上从点(i,j)出发向下走的最长路经，则f(i,j)=max(f(i+1,j),f(i+1,j+1))要输出的就是f(0,0)即从最上面一点出发的最长路经。北京大学《程序设计实习》课程12解题思路以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-1)returntriangle[i][j];intx=longestPath(i+1,j);inty=longestPath(i+1,j+1);if(xy)x=y;returnx+triangle[i][j];}超时！！北京大学《程序设计实习》课程14为什么超时？讨论北京大学《程序设计实习》课程15为什么超时？回答：重复计算738810274445265如果采用递规的方法，深度遍历每条路径，存在大量重复计算，则时间复杂度为2n，对于n=100，肯定超时。北京大学《程序设计实习》课程16一种可能的改进思想：从下往上计算，对于每一点，只需要保留从下面来的路径中和最大的路径的和即可。因为在它上面的点只关心到达它的最大路径和，不关心它从那条路经上来的。问题：有几种解法？？从使用不同的存储开销角度分析1.2×100×100×sizeof(int)2.(100×100+100)×sizeof(int)3.100×sizeof(int)北京大学《程序设计实习》课程17解法1如果每算出一个MaxSum(r,j)就保存起来，则可以用o(n2)时间完成计算。因为三角形的数字总数是n(n+1)/2此时需要的存储空间是：intD[100][100];//用于存储三角形中的数字intSum[100][100];//用于存储每个MaxSum(r,j)北京大学《程序设计实习》课程18解法2没必要用二维Sum数组存储每一个MaxSum(r,j),只要从底层一行行向上递推，那么只要一维数组Sum[100]即可,即只要存储一行的MaxSum值就可以。比解法一改进之处在于节省空间，时间复杂度不变北京大学《程序设计实习》课程19解法3能否不用二维数组D[100][100]存储数字呢？思路：倒过来考虑。前面的思路是从底往上最终算出MaxSum(0,0)。如果从顶往下算，最终算出每一个MaxSum(N-1,j)，然后再取最大的MaxSum(N-1,j)，不就是答案吗？此时递推公式为：if(r==0)MaxSum(r,j)=D[0][0];elseMaxSum(r,j)=Max(MaxSum(r-1,j-1),MaxSum(r-1,j))+D[r][j];北京大学《程序设计实习》课程20由于两重循环形式为：for(r=0;rN;r++)for(j=0;jr+1;j++){………..}r,j不断递增，所以实际上不需要D[100][100]数组，每次从文件里读取下一个数字即可。而每一行的每个MaxSum(r,j)仍然都需要存储起来，这样，只需要一个Sum[100]数组。(注：只需设一个临时存储变量，在计算MaxSum(r,j)后写入数组时，暂存MaxSum(r-1,j))北京大学《程序设计实习》课程21递归到动规的一般转化方法原来递归函数有几个参数，就定义一个几维的数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值，这样就可以从边界开始，逐步填充数组，相当于计算递归函数值的逆过程。北京大学《程序设计实习》课程22最长公共子序列POJ1458给出两个字符串，求出这样的一个最长的公共子序列的长度最长的公共子序列：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。北京大学《程序设计实习》课程23SampleInputabcfbcabfcabprogrammingcontestabcdmnp最长公共子序列SampleOutput420北京大学《程序设计实习》课程24算法1：递归设两个字符串分别是charstr1[MAXL];长度是len1charstr2[MAXL];长度是len2设f(str1,len1,str2,len2)为str1和str2的最大公共子串的长度，则可以对两个字符串的最后一个字符的情况进行枚举：情况一：str1[len1-1]==str2[len1-1]，则f(str1,len1,str2,len2)=1+f(str1,len1-1,str2,len2-1)情况二：str1[len1-1]!=str2[len1-1]，则f(str1,len1,str2,len2)=max(f(str1,len1-1,str2,len2),f(str1,len1,str2,len2-1))程序如下：北京大学《程序设计实习》课程25算法1：递归#includeiostream.h#includestring.h#defineMAX1000charstr1[MAX],str2[MAX];intcommonstr(int,int);voidmain(){while(cinstr1str2){intlen1=strlen(str1);intlen2=strlen(str2);coutcommonstr(len1-1,len2-1);coutendl;}}北京大学《程序设计实习》课程26算法1：递归intcommonstr(intlen1,intlen2){if(len1==-1||len2==-1)return0;if(str1[len1]==str2[len2])return1+commonstr(len1-1,len2-1);else{inttmp1=commonstr(len1-1,len2);inttmp2=commonstr(len1,len2-1);if(tmp1tmp2)returntmp1;elsereturntmp2;}}超时！北京大学《程序设计实习》课程27算法2：动态规划输入两个子串s1,s2,设MaxLen(i,j)表示:s1的左边i个字符形成的子串，与s2左边的j个字符形成的子串的最长公共子序列的长度MaxLen(i,j)就是本题的“状态”，定义一数组假定len1=strlen(s1),len2=strlen(s2）那么题目就是要求MaxLen(len1,len2)北京大学《程序设计实习》课程28算法2：动态规划显然：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));#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++)for(j=0;j=nLength2;j++)anMaxLen[i][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