acm动态规划总结

《acm动态规划总结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Pkuacm1163theTriangle动态规划题目总结(一)题目：http://acm.pku.edu.cn/JudgeOnline/problem?id=1163对于一个有数字组成的二叉树，求由叶子到根的一条路径，使数字和最大，如：738810274445265这个是经典的动态规划，也是最最基础、最最简单的动态规划，典型的多段图。思路就是建立一个数组，由下向上动态规划，保存页子节点到当前节点的最大值，Java核心代码如下：for(inti=num-2;i>=0;i--){for(intj=0;j<=i;j++){//该句是整个动态规划的核心number[i][j]=M

2、ath.max(number[i+1][j],number[i+1][j+1])+number[i][j];}}带有详细注释的代码可以在http://download.csdn.net/user/china8848/获得Pkuacm1579FunctionRunFun动态规划题目总结(二)http://acm.pku.edu.cn/JudgeOnline/problem?id=1579Considerathree-parameterrecursivefunctionw(a,b,c):ifa<=0orb<=0orc<=0,thenw(a,b,c)returns:1ifa>20

3、orb>20orc>20,thenw(a,b,c)returns:w(20,20,20)ifa

4、实在是太多了，所以将问题的结果保存起来，刘汝佳《算法艺术和信息学竞赛》中115页讲到自底向上的递推，这个例子就非常典型。总体来说这个题目还是非常简单的，不过这个思想是地道的动态规划。带有详细注释的代码可以在http://download.csdn.net/user/china8848/获得Pkuacm2081Recaman'sSequence动态规划题目总结(三)http://acm.pku.edu.cn/JudgeOnline/problem?id=2081一道很简单的动态规划，根据一个递推公式求一个序列，我选择顺序的求解，即自底向上的递推，一个int数组result根据

5、前面的值依此求出序列的每一个结果，另外一个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.

6、csdn.net/user/china8848/获得Pkuacm1953WorldCupNoise动态规划题目总结(四)http://acm.pku.edu.cn/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结尾的，而只有结尾为

7、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];}我们可以继续找出规律，其实这个就是斐波那切数列数列