文档介绍：acm动态规划总结
Pku acm 1163 the Triangle 动态规划题目总结一
JudgeOnlineproblemid 1163
对于一个有数字组成的二叉树求由叶子到根的一条路径使数字和最大如
7
8
8 1 0
2 7 4 4
4 5 2 6 5
这个是经典的动态规划也是最最基础最最简单的动态规划典型的多段图思路就是建立一个数组由下向上动态规划保存页子节点到当前节点的最大值Java核心代码如下
for int i num-2i 0i--
for int j 0j ij
该句是整个动态规划的核心
number[i][j] Math number[i1][j]number[i1][j1] number[i][j]
userchina8848获得
Pku acm 1579 Function Run Fun 动态规划题目总结二
JudgeOnlineproblemid 1579
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 000 开始递推逐步产生到w 的值复杂度O n3
userchina8848获得
Pku acm 2081 Recamans Sequence 动态规划题目总结三
JudgeOnlineproblemid 2081
一道很简单的动态规划根据一个递推公式求一个序列我选择顺序的求解即自底向上的递推一个int数组result根据前面的值依此求出序列的每一个结果另外一个boolean数组flag[i]记录i是否已经出现在序列中求result的时候用得着这样就避免了查找核心的java代码为
for i 1i i
if result[i-1]-i 0flag[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
userchina8848获得
Pku acm 1953 World Cup Noise 动态规划题目总结四
JudgeOnlineproblemid 1953
给定一个小于45的整数n求n位2进制数中不含相邻1的数的个数看似简单的一道题如果当n 45时对2的45次方检查是无法完成的任务先分析一下这个问题
N 以1结尾的个数 以0结尾的个数 总和 1 1