《递归和动态规划.ppt》由会员分享，可在线阅读，更多相关《递归和动态规划.ppt（36页珍藏版）》请在三一办公上搜索。
1、递归和动态规划,内容提要,递归：（1）将原问题分解为更小规模的同类问题（2）结束条件#include stdio.hint factorial(int n)if(n=0)return(-1);if(n=1)return(1);else return n*factorial(n-1);int main(int argc,char*argv)printf(%dn,factorial(5);getchar();return 0;,f(5),f(4),f(3),f(2),f(1),线性的f(x)-g(f(x-x)每个f(x-x)只计算一次。,树形递归,例：POJ 2753 Fibonacci数列1，1
2、，f(n-1)+f(n-2),int f(int n)if(n=0|n=1)return n;return f(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),1,1,0,0,1,0,1,0,冗余计算,例：POJ 2753 Fibonacci数列计算过程中存在冗余计算，为了出去冗余计算可以从已知条件开始计算，并记录计算过程中的中间结果。,f(1),1,动态规划,例：POJ 2753 Fibonacci数列int fn+1;f1=f2=1;int I;for(
3、i=3;i=n;i+)fi=fi-1+fi-2;cout fn endl;,动态规划的实质,动态规划的实质就是就是将用递归解决时会重复计算的值，算好一次后就存起来，以后不必重新计算，用空间换时间。动态规划通常用求最优解，能用动态规划解决的求最优解问题，必须满足最优解的每个局部也都是最优的。,记忆化搜索,动态规划,例9POJ 1163 数字三角形在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。三角形的行数大于1小于等于100 数字为0-99,7 3 8 8 1 0 2 7 4 4 4
4、5 2 6 5,输入格式：/三角形行数。下面是三角形73 88 1 02 7 4 4 4 5 2 6 5 要求输出最大和,算法一：递归的想法设f(i,j)为三角形上从点(i,j)出发向下走的最长路经，则f(i,j)=max(f(i+1,j),f(i+1,j+1)+dij要输出的就是f(1，1,)即从最上面一点出发的最长路经。代码如下：,int n;int elem101101;int MaxSum(int row,int col)if(row=n)return elemrowcol;/int nSum1=MaxSumrow+1col;/int nsum2=MaxSumrow+1col+1;if
5、(MaxSum(row+1,col)=MaxSum(row+1,col+1)return MaxSum(row+1,col)+elemrowcol;else return MaxSum(row+1,col+1)+elemrowcol;int main(int argc,char*argv)scanf(%d,超时,7 3 8 8 1 0 2 7 4 4 4 5 2 6 5,5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5,30 23 21 20 13 10 7 12 10 10 4 5 2 6 5,1 20 1 1 21 1 2 1 22 1 3 3 1 23 1 4 6 4 1
6、24,解决重复计算的方法：将中间计算结果保存起来，从而不必每次都递归计算。每个结点只计算一次总计算次数=1+2+3+n,#include stdio.h#include memory.hint n;int elem101101;int aMaxSum101101;int MaxSum(int row,int col)if(row=n)return elemrowcol;if(aMaxSumrow+1col=-1)aMaxSumrow+1col=MaxSum(row+1,col);if(aMaxSumrow+1col+1=-1)aMaxSumrow+1col+1=MaxSum(row+1,col
7、);/int nSum1=MaxSumrow+1col;/int nsum2=MaxSumrow+1col+1;if(MaxSum(row+1,col)=MaxSum(row+1,col+1)return MaxSum(row+1,col)+elemrowcol;else return MaxSum(row+1,col+1)+elemrowcol;int main(int argc,char*argv)scanf(%d,Sets buffers to a specified character.void*memset(void*dest,int c,size_t count);destPoin
8、ter to destinationcCharacter to setcountNumber of characters,动态规划：将一个问题分解为子问题递归求解，将中间结果保存以避免重复计算的方法。求最优解一切子问题也是最优的,递归 递推,aMaxSumij=elemij i=nmax(aMaxSum(i+1,j),aMaxSum(i+1,j)in,算法二：动态规划从下往上逐层计算#include memory.hint n;int elem101101;int aMaxSum101101;int main(int argc,char*argv)scanf(%d,解题步骤：（1）问题分解为子
9、问题 越来越简单 最终直接有解（2）状态：子问题对应的变量 的值及结果（3）状态迁移 从已知状态推导未知状态,aMaxSumij=elemij i=nmax(aMaxSum(i+1,j),aMaxSum(i+1,j)in,动态规划,例10POJ 1458最大公共子串 给出两个字符串，求出这样的一个最长的公共子序列的长度：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。Sample Inputabcfbc abfcab programming contestabcd mnp Sample Output420,算法一：递归的思想设两个字符串分别是char st
10、r1MAXL;长度是len1char str2MAXL;长度是len2设f(str1,len1,str2,len2)为str1和str2的最大公共子串的长度，则可以对两个字符串的最后一个字符的情况进行枚举：情况一：str1len1-1=str2len1-1，则 f(str1,len1,str2,len2)=1+f(str1,len1-1,str2,len2-1)情况二：str1len1-1!=str2len1-1 f(str1,len1,str2,len2)=max(f(str1,len1-1,str2,len2),f(str1,len1,str2,len2-1)程序如下：,#include
11、stdio.h#include memory.h#include string.hchar str1100;char str2100;int MaxStr(char*s,int len1,char*t,int len2)if(len1=0|len2=0)return 0;elseif(str1len1-1=str2len2-1)return 1+MaxStr(str1,len1-1,str2,len2-1);elseif(MaxStr(str1,len1-1，str2,len2)MaxStr(str1,len1,str2,len2-1)return MaxStr(str1,len1-1,str
12、2,len2);else return MaxStr(str1,len1,str2,len2-1);int main(int argc,char*argv)gets(str1);gets(str2);printf(%dn,MaxStr(str1,strlen(str1),str2,strlen(str2);getchar();return 0;,递归过程如下：abcfbc abfcababcfb abfcababcf abfcaabc abfcaab abfcaa abfca abfca,算法二：动态规划从str1和str2的第一个字符开始考虑；int comLenMAXMAX;用一个二维数组
13、记录str1的前i个字符与str2中的前j个字符的最大公共子串长度（状态）设立初值：comLen 00MAX=0;comLen 0MAX0=0;表示两个字符串中有一个没有参与比较时，最大公共子串长度为递推：if(stri=strj)comLen ij=1+comLen i-1j-1;else comLenij=max(comLeni-1j,comLenij-1);,#include stdio.h#include memory.h#include string.h#define MAX 100char str1MAX;char str2MAX;int comMAXMAX;int main(in
14、t argc,char*argv)int i,j;while(1)gets(str1);if(str10=0)break;gets(str2);int len1=strlen(str1);int len2=strlen(str2);for(i=0;icomij-1)comij=comi-1j;else comij=comij-1;/else/for printf(%dn,comlen1len2);/whilegetchar();return 0;,void main()char ch;while(ch=getchar()!=EOF)putchar(ch);CTRL+Z,动态规划,例11POJ
15、2755神奇口袋前面介绍了用递归的方法解此题，核心思想是逐一枚举每个数的使用情况，用或不用，这里可以用动态规划的方法实现这一想法即有n个数，则用1到2n所表示的二进制数来枚举所有这些数的组合情况，例如：n=3，则表示用第和第个数，不用第个数，检验有多少种组合的和是，就得到了问题的解,#include void main()int n,i,j,k,count40=0;cin n;int numbers21;for(i=0;i numbersi;for(i=1;i0;j=1,k-)if(j枚举组合太多，超时，如果n增大，更是不可想象,算法三，因为要凑出，可以考虑记录所有能够凑出的组合的数目，定义数
16、组 int sum41；sumi表示能够凑出和为i的次数考虑只用a1能凑出a1一次，用a2能够凑出a2一次，a1+a2一次，用a3能够凑出a3一次，它与前面的所有能够凑出的数相加得到的数各一次依次类推，使用所有的数，并计算能够得到的和的可能及每种和的次数,#include#define MAX 41void main()int n,i,j,input;int sumMAX;for(i=0;i n;for(i=0;i input;for(j=40;j=1;j-)if(sumj0,动态规划,例12POJ 平板上色问题 问题描述：一个平板被一组大小不等的长方形覆盖，现在需要为每个长方形上一种颜色。每
17、个长方形需要上的颜色是预先确定的。每种画笔上一种颜色。但为了避免画笔将涂料滴到已经上好色的、且颜色不同的长方形上，在对一个长方形A上色前，要求：位于A正上方的其它长方形都已上好色。每取一次画笔，可以为多个长方形上色。请编写一个程序，计算为了完成一个平板的全部上色，最少需要取多少次画笔。,算法一：一步枚举递归枚举第一次使用的颜色，将能涂色的矩形x个涂色，则剩下的矩形数目减少x个，变成更小规模的同类问题，递归下去源程序最坏情况下,枚举次数为15*1414,会超过秒，改用递归的方法,算法二：动态规划用枚举矩形被刷与不刷的状态，在每种状态下，枚举最后一次刷的矩形下的最小换笔次数，即enumeratei
18、j;i取值范围是，表示每个举行刷与未刷的状态，j取值范围是，表示当前状态下最后一次刷的矩形，enumerateij表示某种状态下的换笔最小次数；对于*15种状态，逐一枚举下一次涂色的矩形，如果该矩形颜色与最后一次涂色的矩形相同，则原状态新矩形的最小取笔次数等于原状态取笔次数，否则原状态新矩形的最小取笔次数等于原状态取笔次数。本题的解就是找出在状态 下，即所有矩形均被涂色后，最后涂色的个矩形中哪个用的取笔次数最小。例如：源程序,作业：1、Fibonacci数列的递归式动态规划算法。2、最长上升子序列 一个数的序列bi，当b1 b2 bs的时候，这个序列是上升的。对于给定的一个序列(a1，a2，aN),可以得到一些上升的子序列(ai1，ai2,，aiK),这里1i1i2iK N。比如，对于序列(1，7，3，5，9，4，8),有它的一些上升子序列，如(1，7),(3，4，8)等。这些子序列中最长的长度是4，比如子序列（1，3，5，8）。你的任务就是对于给定的序列，求出最长上升子序列的长度。,
