资源预览内容
第1页 / 共28页
第2页 / 共28页
第3页 / 共28页
第4页 / 共28页
第5页 / 共28页
第6页 / 共28页
第7页 / 共28页
第8页 / 共28页
第9页 / 共28页
第10页 / 共28页
亲,该文档总共28页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
今天你AC 了吗?*1第一页,共28页。第6讲DP入门*2第二页,共28页。我校的ACM在线评测系统n n课件下载地址:n 动态规划法将待求解问题分解成若干个相互重叠的子问题,每个子问题对应决策过程的一个阶段,一般来说,子问题的重叠关系表现在对给定问题求解的递推关系(也就是动态规划函数)中,将子问题的解求解一次并填入表中,当需要再次求解此子问题时,可以通过查表获得该子问题的解而不用再次求解,从而避免了大量重复计算。*4第四页,共28页。 原问题的解 原问题 填 表子问题1子问题2子问题n动态规划法的求解过程*5第五页,共28页。n=5时分治法计算斐波那契数的过程。 F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例:计算斐波那契数:*6第六页,共28页。01234567890112358132134动态规划法求解斐波那契数F(9)的填表过程 : 注意到,计算F(n)是以计算它的两个重叠子问题 F(n-1)和F(n-2)的形式来表达的,所以,可以设计一张表填入n+1个F(n)的值。 *7第七页,共28页。 用动态规划法求解的问题具有特征: 能够分解为相互重叠的若干子问题; 满足最优性原理(也称最优子结构性质):该问题的最优解中也包含着其子问题的最优解。(用反证法)分析问题是否满足最优性原理:1. 先假设由问题的最优解导出的子问题的解不是最优的;2. 然后再证明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾。 *8第八页,共28页。动态规划法设计算法一般分成三个阶段:(1)分段:将原问题分解为若干个相互重叠的子问题;(2)分析:分析问题是否满足最优性原理,找出动态规划函数的递推式;(3)求解:利用递推式自底向上计算,实现动态规划过程。 v 动态规划法利用问题的最优性原理,以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。*9第九页,共28页。例1斐波那契数列 nefu 85n计算斐波那契数列的值!该数列为1 1 2 3 5 8 13 21 . n有多组数据,每组1行,用N表示,1 = N = 50。 n输出Fibonacci(N)的值! *10第十页,共28页。代码:nint n;n long long feibo51;n feibo1=1;n feibo2=1;n for(int i=3;in)n coutfeibonendl;*11第十一页,共28页。用递归能做吗?nlong long data51;nlong long fblq(int n)nn if (n=1|n=2) return 1;n elsen n if (datan=0)n datan=fblq(n-1)+fblq(n-2); /看看这个! 只算1次!n return datan; n n n n n *12第十二页,共28页。现在同学们在纸上计算下题:n计算N! ninputn有多组数据,每组一行,用N表示,0 = N = 20;noutputn输出N!*13第十三页,共28页。递归的代码:n#include n#include nusing namespace std;nlong long data21;nlong long jc(int n)nn if (n=0|n=1) return 1;n if (datan=0)n datan=n*jc(n-1);n return datan; n nnint main(int argc, char *argv)nn int n;n memset(data,0,sizeof(data);n while(cinn)n coutjc(n)endl;n system(PAUSE);n return EXIT_SUCCESS;n*14第十四页,共28页。递推的代码:n#include n#include nusing namespace std;nint main(int argc, char *argv)nn int n; long long data51;n memset(data,0,sizeof(data);n data0=1;data1=1;n for(int i=2;in)n coutdatanendl;n system(PAUSE);n return EXIT_SUCCESS;n*15第十五页,共28页。Nefu20 穿过街道n一个城市的街道布局如下:从最左下方走到最右上方,每次只能往上或往右走,一共有多少种走法? *16第十六页,共28页。ninputn输入很多行行数,每行1个数字代表n的值,当n=0时结束(2=nn)n n if (n=0) break; n coutgetf(n,n)endl; n n system(PAUSE);n return EXIT_SUCCESS;n*20第二十页,共28页。其实这题递推的代码更短:nint n;n long long data2121;n for(int i=0;i=20;i+)n n datai0=1;/ 处理边界n data0i=1;/ 处理边界n n for(int j=1;j=20;j+)n for(int k=1;kn&n)n coutdatannn)n n memset(inp,0,sizeof(inp);n memset(data,0,sizeof(data);*25第二十五页,共28页。nfor(int i=1;i=n;i+)n for(int j=1;jdataij;n if (i=1) inpij=dataij;n elsen inpij=max(inpi-1j,inpi-1j-1)+dataij;n n n *26第二十六页,共28页。找出最后1行的最大值,并输出之!nint tmp=0;n for(int k=1;k=n;k+)n if (tmp=inpnk) tmp=inpnk;n couttmpendl;*27第二十七页,共28页。Welcome to HDOJThank You *28第二十八页,共28页。
收藏 下载该资源
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号