文档介绍：Pkuacm1163theTriangle动态规划题目总结(一)题目:./JudgeOnline/problem?id=1163对于一个有数字组成的二叉树,求由叶子到根的一条路径,使数字和最大,如:788**********这个是经典的动态规划,也是最最基础、最最简单的动态规划,典型的多段图。思路就是建立一个数组,由下向上动态规划,保存页子节点到当前节点的最大值,Java核心代码如下:for(inti=num-2;i>=0;i--){ for(intj=0;j<=i;j++){ //该句是整个动态规划的核心number[i][j]=(number[i+1][j],number[i+1][j+1])+number[i][j]; }}带有详细注释的代码可以在http://download./user/china8848/获得Pkuacm1579FunctionRunFun动态规划题目总结(二)./JudgeOnline/problem?id=1579Considerathree-parameterrecursivefunctionw(a,b,c):ifa<=0orb<=0orc<=0,thenw(a,b,c)returns:1ifa>20orb>20orc>20,thenw(a,b,c)returns:w(20,20,20)ifa<bandb<c,thenw(a,b,c)returns:w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)otherwiseitreturns:w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)这本身就是一个递归函数,要是按照函数本身写递归式,结果肯定是TLE,这里我开了一个三维数组,从w(0,0,0)开始递推,逐步产生到w(20,20,20)的值,复杂度O(n^3).总结:这道题是很地道的DP,因为它的子问题实在是太多了,所以将问题的结果保存起来,刘汝佳《算法艺术和信息学竞赛》中115页讲到自底向上的递推,这个例子就非常典型。总体来说这个题目还是非常简单的,不过这个思想是地道的动态规划。带有详细注释的代码可以在http://download./user/china8848/获得Pkuacm2081Recaman'sSequence动态规划题目总结(三)./JudgeOnline/problem?id=2081一道很简单的动态规划,根据一个递推公式求一个序列,我选择顺序的求解,即自底向上的递推,一个int数组result根据前面的值依此求出序列的每一个结果,另外一个boolean数组flag[i]记录i是否已经出现在序列中,求result的时候用得着,这样就避免了查找。核心的java代码为:for(i=1;i<=500000;i++){ if(result[i-1]-i>0&&flag[result[i-1]-i]==false) { result[i]=result[i-1]-i; flag[result[i-1]-i]=true; } else { result[i]=result[i-1]+i; flag[result[i-1]+i]=true; }}带有详细注释的代码可以在http://download./user/china8848/获得Pkuacm1953WorldCupNoise动态规划题目总结(四)./JudgeOnline/problem?id=1953给定一个小于45的整数n,求n位2进制数中不含相邻1的数的个数。看似简单的一道题,如果当n=45时,对2的45次方检查,是无法完成的任务。先分析一下这个问题:N以1结尾的个数以0结尾的个数总和111221233………对于n=1来说,以1结尾、以0结尾个数都是1,总和是2,下面过度到2:对于所有以1结尾的数,后面都可以加上0,变为n=2时以0结尾的,而只有结尾为0的数才能加上1(因为不能有两个连续0),这样就可以在n=2的格里分别填上1、2,总和算出来为3,以此类推,我们可以算出所有n<=45的值,然后根据输入进行相应输出。核心代码如下:inti,num,count,array[50][2],j=0;array[1][1]=1;array[1][0]=1;for(i=2;i<50;i++){ array[i][0]=array[i-1][1]; array[i][1]=array[i-1][1]+array[i-1][0];}我们可以继续找出规律,其实这个就是斐波那切数列数列:F[N]=F[N-1]+F[N-2];可以继续简化代码。带有详细注