acm动态规划方案总结.doc

Pkuacm1163theTriangle动态规划题目总结(一)题目：对于一种有数字构成二叉树，求由叶子到根一条途径，使数字和最大，如：78810274445265这个是典型动态规划，也是最最基本、最最简朴动态规划，典型多段图。思路就是建立一种数组，由下向上动态规划，保存页子节点到当前节点最大值，Java核心代码如下：for(inti=num-2;i>=0;i--){for(intj=0;j<=i;j++){//该句是整个动态规划核心number[i][j]=Math.max(number[i+1][j],number[i+1][j+1])+number[i][j];}}带有详细注释代码可以在获得Pkuacm1579FunctionRunFun动态规划题目总结(二)Considerathree-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页讲到自底向上递推，这个例子就非常典型。总体来说这个题目还是非常简朴，但是这个思想是地道动态规划。带有详细注释代码可以在获得Pkuacm2081Recaman'sSequence动态规划题目总结(三)一道很简朴动态规划，依照一种递推公式求一种序列，我选取顺序求解，即自底向上递推，一种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;}}带有详细注释代码可以在获得Pkuacm1953WorldCupNoise动态规划题目总结(四)给定一种不大于45整数n，求n位2进制数中不含相邻1数个数。看似简朴一道题，如果当n=45时，对245次方检查，是无法完毕任务。先分析一下这个问题：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];可以继续简化代码。带有详细注释代码可以在获得Pkuacm1458CommonSubsequence动态规划题目总结(五)求两个string最大公共字串，动态规划典型问题。算法导论有详细解说。下面以题目中例子来阐明算法：两个string分别为：abcfbc和abfca。创立一种二维数组result[][],维数分别是两个字符串长度加一。咱们定义result[i][j]表达Xi和Yj最长子串(LCS).当i或j等于0时，result[i][j]=0.LCS问题存在一下递归式：result[i][j]=0i=0orj=0result[i][j]=result[i-1][j-1]+1Xi==Yjresult[i][j]=MAX(result[i-1][j]，resu