ACM基础知识.ppt

ACM基础知识* 1动态规划 （ Dynamic programming）Date 2n 动态规划是一种将问题实例 分解分解 为更小的、相似的 子问题子问题 ，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略n 基本要素n 最优子结构性质n 子问题Date 3先热身一下 Date 4一、数塔问题 有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。Date 5用 暴力 的方法，可以吗？Date 6这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如 31），则需要列举出的路径条数将是一个非常庞大的数目（ 230= 10243 109=10亿）。试想一下：Date 7解题思路？Date 8拒绝 暴力， 倡导 和谐Date 9理论小结Date 10