递归和动态规划.ppt

递归和动态规划,内容提要,递归： （1）将原问题分解为更小规模的同类问题 （2）结束条件 #include “stdio.h“ int 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，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(i=3;i=n;i+) fi = fi-1+fi-2; cout fn endl;,动态规划的实质,动态规划的实质就是 就是将用递归解决时会重复计算的值，算好一次后就存起来，以后不必重新计算，用空间换时间。动态规划通常用求最优解，能用动态规划解决的求最优解问题，必须满足最优解的每个局部也都是最优的。,记忆化搜索,动态规划,例9 poj 1163 数字三角形 在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。 三角形的行数大于1小于等于100 数字为0 - 99,7 3 8 8 1 0 2 7 4 4 4 5 2 6 5,输入格式： /三角形行数。下面是三角形 7 3 8 8 1 0 2 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(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 24,解决重复计算的方法： 将中间计算结果保存起来，从而不必每次都递归计算。 每个结点只计算一次 总计算次数=1+2+3+n,#include “stdio.h“ #include “memory.h“ int 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); / 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 ); dest pointer to destination c character to set count number of characters,动态规划：将一个问题分解为子问题递归求解，将中间结果保存以避免重复计算的方法。 求最优解 一切子问题也是最优的,递归 递推,amaxsumij= elemij i=n max(amaxsum(i+1,j),amaxsum(i+1,j) in,算法二：动态规划从下往上逐层计算 #include “memory.h“ int n; int elem101101; int amaxsum101101; int main(int argc, char* argv) scanf(“%d“, ,解题步骤： （1）问题分解为子问题 越来越简单 最终直接有解 （2）状态：子问题对应的变量 的值及结果 （3）状态迁移 从已知状态推导未知状态,amaxsumij= elemij i=n max(amaxsum(i+1,j),amaxsum(i+1,j) in,动态规划,例10 poj 1458最大公共子串 给出两个字符串，求出这样的一个最长的公共子序列的长度：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序和原串中的先后顺序一致。 sample input abcfbc abfcab programming contest abcd mnp sample output 4 2 0,算法一：递归的思想 设两个字符串分别是 char str1maxl; 长度是len1 char 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 “stdio.h“ #include “memory.h“ #include “string.h“ char str1100; char str2100; int maxstr(char *s,int len1,char *t,int len2) if(len1=0|len2=0) return 0; else if(str1len1-1 = str2len2-1) return 1+maxstr(str1,len1-1,str2,len2-1); else if(maxstr(str1,len1-1，str2,len2)maxstr(str1,len1,str2,len2-1) return maxstr(str1,len1-1,str2,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 abfcab abcfb abfcab abcf abfca abc abfca ab abfca a abfca abfca,算法二：动态规划 从str1和str2的第一个字符开始考虑； int comlenmaxmax; 用一个二维数组记录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 100 char str1max; char str2max; int commaxmax; int main(int 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); /while getchar(); return 0; ,void main() char ch; while(ch = getchar() != eof) putchar(ch); ctrl+z,动态规划,例11 poj 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增大，更是不可想象,算法三，因为要凑出，可以考虑记录所有能够凑出的组合的数目， 定义数组 int sum41； sumi表示能够凑出和为i的次数 考虑只用a1能凑出a1一次，用a2能够凑出a2一次，a1+a2一次， 用a3能够凑出a3一次，它与前面的所有能够凑出的数相加得到的数各一次 依次类推，使用所有的数，并计算能够得到的和的可能及每种和的次数,#include #define max 41 void 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 ,动态规划,例12 poj 平板上色问题 问题描述：一个平板被一组大小不等的长方形覆盖，现在需要为每个长方形上一种颜色。每个长方形需要上的颜色是预先确定的。每种画笔上一种颜色。但为了避免画笔将涂料滴到已经上好色的、且颜色不同的长方形上，在对一个长方形a上色前，要求：位于a正上方的其它长方形都已上好色。每取一次画笔，可以为多个长方形上色。请编写一个程序，计算为了完成一个平板的全部上色，最少需要取多少次画笔。,算法一：一步枚举递归 枚举第一次使用的颜色，将能涂色的矩形x个涂色，则剩下的矩形数目减少x个，变成更小规模的同类问题，递归下去 源程序 最坏情况下, 枚举次数为15*1414, 会超过秒，改用递归的方法,算法二：动态规划 用枚举矩形被刷与不刷的状态，在每种状态下，枚举最后一次刷的矩形下的最小换笔次数，即 enumerateij; i取值范围是，表示每个举行刷与未刷的状态， j取值范围是，表示当前状态下最后一次刷的矩形， enumerateij 表示某种状态下的换笔最小次数； 对于*15种状态，逐一枚举下一次涂色的矩形，如果该矩形颜色与最后一次涂色的矩形相同，则原状态新矩形的最小取笔次数等于原状态取笔次数，否则原状态新矩形的最小取笔次数等于原状态取笔次数。 本题的解就是找出