《递归和动态规划课件》由会员分享，可在线阅读，更多相关《递归和动态规划课件（36页珍藏版）》请在金锄头文库上搜索。
1、递归和动态规划,内容提要,递归： （1）将原问题分解为更小规模的同类问题 （2）结束条件#include “stdio.h“ int factorial(int n) if(ng(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
2、,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 =MaxSum(row+1,col+1)return MaxSum(row+1,col)+elemrowcol;elsereturn MaxSum(row+1,col+1)+elemrowcol; int main(in
3、t argc, char* argv) scanf(“%d“, 超时,7 3 88 1 02 7 4 44 5 2 6 5,57 3 88 1 02 7 4 44 5 2 6 5,30 23 2120 13 107 12 10 104 5 2 6 5,1 201 1 211 2 1 221 3 3 1 231 4 6 4 1 24,解决重复计算的方法：将中间计算结果保存起来，从而不必每次都递归计算。 每个结点只计算一次 总计算次数=1+2+3+n,#include “stdio.h“ #include “memory.h“ int n; int elem101101; int aMaxSum1
4、01101; 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,co
5、l)+elemrowcol;elsereturn 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,动态规划：将一个问题分解为子问题递归求解，将中间结果保存以避免重复计算的方
6、法。 求最优解 一切子问题也是最优的,递归 递推,aMaxSumij= elemij i=nmax(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
7、(aMaxSum(i+1,j),aMaxSum(i+1,j) iMaxStr(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 a
8、bfcab 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;elsecomLenij = max(comLeni-1j,comLenij-1);,#inc
9、lude “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 /forprintf(“%dn“,comlen1len2); /whilegetchar();return 0; ,
