数据结构与算法 acm动态规划总结.doc
文本预览下载声明
Pku acm 1163 the Triangle 动态规划题目总结(一)
对于一个有数字组成的二叉树，求由叶子到根的一条路径，使数字和最大，如：
7
8
8 1 0
2 7 4 4
4 5 2 6 5
这个是经典的动态规划，也是最最基础、最最简单的动态规划，典型的多段图。思路就是建立一个数组，由下向上动态规划，保存页子节点到当前节点的最大值，Java核心代码如下：
for(int i=num-2;i=0;i--){
for(int j=0;j=i;j++){
//该句是整个动态规划的核心
number[i][j]=Math.max(number[i+1][j],number[i+1][j+1])+number[i][j];
}
}
Pku acm 1579 Function Run Fun 动态规划题目总结(二)
Consider a three-parameter recursive function w(a, b, c): if a = 0 or b = 0 or c = 0, then w(a, b, c) returns: 1 if a 20 or b 20 or c 20, then w(a, b, c) returns: w(20, 20, 20) if a b and b c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: 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页讲到自底向上的递推，这个例子就非常典型。总体来说这个题目还是非常简单的，不过这个思想是地道的动态规划。
Pku acm 2081 Recamans Sequence 动态规划题目总结(三)
一道很简单的动态规划，根据一个递推公式求一个序列，我选择顺序的求解，即自底向上的递推，一个int数组result根据前面的值依此求出序列的每一个结果，另外一个boolean数组flag[i]记录i是否已经出现在序列中，求result的时候用得着，这样就避免了查找。核心代码为：
for(i=1;i=500000;i++)
{
if(result[i-1]-i0flag[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]] = true;
}
}
Pku acm 1953 World Cup Noise 动态规划题目总结(四)
给定一个小于45的整数n，求n位2进制数中不含相邻1的数的个数。看似简单的一道题，如果当n=45时，对2的45次方检查，是无法完成的任务。先分析一下这个问题：
N
以1结尾的个数
以0结尾的个数
总和
1
1
1
2
2
1
2
3
3
…
…
…
对于n=1来说，以1结尾、以0结尾个数都是1，总和是2，下面过度到2：对于所有以1结尾的数，后面都可以加上0，变为n=2时以0结尾的，而只有结尾为0的数才能加上1（因为不能有两个连续0），这样就可以在n=2的格里分别填上1、2，总和算出来为3，以此类推，我们可以算出所有n=45的值，然后根据输入进行相应输出。核心代码如下：
int i,num,count,array[50][2],j=0;
array[1][1] = 1;
array[1][0] = 1;
for(i=2;i50;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];可以继续简化代码。
Pku acm 1458 Common S
显示全部