文档介绍：ACM 程序设计谢勇 ericxie@ 2017-2-23 2今天, 你AC吗? 依然没有 2017-2-23 3第四讲动态规划入门(Dynamic programming ) 2017-2-23 4一、经典问题:数塔问题有形如下图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的值最大。 2017-2-23 5用暴力的方法,可以吗? 2017-2-23 6 这道题如果用枚举法(暴力思想),在数塔层数稍大的情况下(如 31),则需要列举出的路径条数将是一个非常庞大的数目( 2^30= 1024^3 > 10^9=10 亿)。试想一下: 2017-2-23 7拒绝暴力, 倡导和谐~ 2017-2-23 8 从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值,只要左右两道路径上的最大值求出来了才能作出决策。同样,下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去, 直到倒数第二层时就非常明了。如数字 2,只要选择它下面较大值的结点 19 前进就可以了。所以实际求解时,可从底层开始,层层递进, 最后得到最大值。结论:自顶向下的分析,自底向上的计算。考虑一下: 2017-2-23 9二、经典问题:最长有序子序列 963852741 Num[I] 876543210I 2017-2-23 10 解决方案: 963852741 Num[I] 876543210I543432321 F[I]