ACM动态规划总结 动态规划经典题傻瓜式讲解
4星 · 超过85%的资源 需积分: 10 50 浏览量
2009-04-12
15:09:12
上传
评论 5
收藏 460KB DOC 举报 
Pku acm 1163 the Triangle 动态规划题目总结(一)
题目：
对于一个有数字组成的二叉树，求由叶子到根的一条路径，使数字和最大，如：
!!
!" "
这个是经典的动态规划，也是最最基础、最最简单的动态规划，典型的多段图。思路
就是建立一个数组，由下向上动态规划，保存页子节点到当前节点的最大值，# 核心代
码如下：
for$int% &'&%%()
for$int*&*+&*,,()
该句是整个动态规划的核心
-.-*./max$-,.-*.0-,.-*,.(,-.-*.&
1
1
带有详细注释的代码可以在 233!获得
Pku acm 1579 Function Run Fun 动态规划题目总结(二)
"4
53%3#62$00(
6+++02$00(3
6' ' ' 02$00(32$ 0 0 (
6++02$00(32$00%(,2$0%0%(%2$0
%0(
2332$%00(,2$%0%0(,2$%00%(%2$%0%0
%(
这本身就是一个递归函数，要是按照函数本身写递归式，结果肯定是 789，这里我开
了一个三维数组，从 2$00(开始递推，逐步产生到 2$ 0 0 (的值，复杂度
$:(
总结：这道题是很地道的 ;<，因为它的子问题实在是太多了，所以将问题的结果保
存起来，刘汝佳《算法艺术和信息学竞赛》中 " 页讲到自底向上的递推，这个例子就非
常典型。总体来说这个题目还是非常简单的，不过这个思想是地道的动态规划。
带有详细注释的代码可以在 233!获得
剩余18页未读，继续阅读
资源评论
xw_njust_ecjtu2014-09-10差不多，还行吧
kai_ding2012-10-23写的不错，就是分析的太少了
喧嚣天空2012-06-24不怎么的，内容和”动态规划32讲一样“
