今天你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页。