递归和动态规划.ppt
《递归和动态规划.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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 递归 动态 规划
链接地址:https://www.31ppt.com/p-2666720.html