《整理版动态规划基础讲解及经典案例分析解答课件》由会员分享，可在线阅读，更多相关《整理版动态规划基础讲解及经典案例分析解答课件（60页珍藏版）》请在金锄头文库上搜索。
1、2018/10/8,1,第九课,动态规划(I),综合实践考核,话弹讶寄痊畦琳普晦道棺榔哄徽痢坦可况迄筷伟隘够摆臆维袭毋捂营佃召动态规划基础讲解及经典案例分析解答动态规划基础讲解及经典案例分析解答,数字三角形,1、问题描述,上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。 注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。,谰竣掇卓好屁枪洱锑添棺路枢额不伞蛊网轧脸扇胰凄迪泅克鲍撅循叫茂积动态规划基础讲解及经典案例分析解答动态规划基础讲解及经
2、典案例分析解答,问题描述,输入数据 输入的第一行是一个整数N (1 N nSum2 )return nSum1+Drj;return nSum2+Drj;,柄尊川讯绅方喀憋捎默厦渠疮铣糟允杖黎图难购免廊业逾返贝相峻矽惠鉴动态规划基础讲解及经典案例分析解答动态规划基础讲解及经典案例分析解答,3、参考程序 I,int main(void) int m;scanf(“%d“, ,提交结果：Time Limit Exceed,甄军苫陈薄已郁沏贾嫉拟厘涉跨恼岗终梧斌琴阮罚胶形困涉僵婪杰紧永淹动态规划基础讲解及经典案例分析解答动态规划基础讲解及经典案例分析解答,程序I分析,上面的程序，效率非常低，在N 值
3、并不大，比如N=100 的时候，就慢得几乎永远算不出结果了。 为什么会这样呢？是因为过多的重复计算。 我们不妨将对MaxSum 函数的一次调用称为一次计算。那么，每次计算MaxSum(r, j)的时候，都要计算一次MaxSum(r+1, j+1)，而每次计算MaxSum(r, j+1)的时候，也要计算一次MaxSum(r+1, j+1)。重复计算因此产生。 在题目中给出的例子里，如果我们将MaxSum(r, j)被计算的次数都写在位置（r, j），那么就能得到右面的三角形：,1 1 1 1 2 1 1 3 3 1 1 4 6 4 1,7 3 8 8 1 0 2 7 4 4 4 5 2 6 5,
4、瞎瓶吊嗜走柔呐柯睁妓晕获狄角赔坦走恭涛疽蓝污娩铁过拯芭平走焚品蛹动态规划基础讲解及经典案例分析解答动态规划基础讲解及经典案例分析解答,程序分析,从上图可以看出，最后一行的计算次数总和是16，倒数第二行的计算次数总和是8。不难总结出规律，对于N 行的三角形，总的计算次数是20 +21+22+2(N-1)=2N-1。当N= 100 时，总的计算次数是一个让人无法接受的大数字。既然问题出在重复计算，那么解决的办法，当然就是，一个值一旦算出来，就要记住，以后不必重新计算。即第一次算出MaxSum(r, j)的值时，就将该值存放起来，下次再需要计算MaxSum(r, j)时，直接取用存好的值即可，不必再
5、次调用MaxSum 进行函数递归计算了。这样，每个MaxSum(r, j)都只需要计算1 次即可，那么总的计算次数（即调用MaxSum 函数的次数）就是三角形中的数字总数，即1+2+3+N = N(N+1)/2。如何存放计算出来的MaxSum（r, j）值呢？显然，用一个二维数组aMaxSumNN就能解决。aMaxSumrj就存放MaxSum(r, j)的计算结果。下次再需要MaxSum(r, j)的值时，不必再调用MaxSum 函数，只需直接取aMaxSumrj的值即可。,卓添犊商旗扁娃咳吓墩玩官跌尝肩直教森蚌霄轿赖津抢肩胁部鸥椽识观俄动态规划基础讲解及经典案例分析解答动态规划基础讲解及经典
6、案例分析解答,4、参考程序 II,#include #include #define MAX_NUM 100 int DMAX_NUM + 10MAX_NUM + 10; int N; int aMaxSumMAX_NUM + 10MAX_NUM + 10; int MaxSum( int r, int j) if( r = N ) return Drj;if( aMaxSumr+1j = -1 ) /如果MaxSum(r+1, j)没有计算过aMaxSumr+1j = MaxSum(r+1, j);if( aMaxSumr+1j+1 = -1)aMaxSumr+1j+1 = MaxSum(r
7、+1, j+1);if( aMaxSumr+1j aMaxSumr+1j+1 )return aMaxSumr+1j +Drj;return aMaxSumr+1j+1 + Drj; ,羊焦案吏枪父剑夯界淘臻矗阅摈褐抒劫疚木姬诀庆臣乍涯酉遮莹慰杰竿散动态规划基础讲解及经典案例分析解答动态规划基础讲解及经典案例分析解答,4、参考程序 II,int main(void) int m;scanf(“%d“, ,茄斟书危鳞发督折蔓瞅税箱碳统轴殷蛔缸境困锐步礼允夸犯胯饺痛懊闭叉动态规划基础讲解及经典案例分析解答动态规划基础讲解及经典案例分析解答,程序II分析,这种将一个问题分解为子问题递归求解，并且将中
8、间结果保存以避免重复计算的办法，就叫做“动态规划”。动态规划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是最优的。以上题为例，最佳路径上面的每个数字到底部的那一段路径，都是从该数字出发到达到底部的最佳路径。 实际上，递归的思想在编程时未必要实现为递归函数。在上面的例子里，有递推公式：,因此，不需要写递归函数，从aMaxSumN-1这一行元素开始向上逐行递推，就能求得aMaxSum11的值了。,慰特沉汗啤侯澄简炕懈内靡闺爷筏宝欣农到茎瞒伺男礁原昼戊巩殉浇锚惭动态规划基础讲解及经典案例分析解答动态规划基础讲解及经典案例分析解答,5、参考程序 III,int D
9、MAX_NUM + 10MAX_NUM + 10; int N; int aMaxSumMAX_NUM + 10MAX_NUM + 10; int main(void) int i, j;scanf(“%d“, ,思考题：上面的几个程序只算出了最佳路径的数字之和。如果要求输出最佳路径上的每个数字，该怎么办？,殖拌盏桐甄献诈版沦害不弧撑郭芝坡冶谰谜坚吏小斑歌顿阳瑶骡英收株掉动态规划基础讲解及经典案例分析解答动态规划基础讲解及经典案例分析解答,动态规划解题的一般思路,许多求最优解的问题可以用动态规划来解决。首先要把原问题分解为若干个子问题。注意单纯的递归往往会导致子问题被重复计算，用动态规划的方法
10、，子问题的解一旦求出就要被保存，所以每个子问题只需求解一次。 子问题经常和原问题形式相似，有时甚至完全一样，只不过规模从原来的n 变成了n-1，或从原来的nm 变成了n(m-1) 等等。找到子问题，就意味着找到了将整个问题逐渐分解的办法。分解下去，直到最底层规模最小的的子问题可以一目了然地看出解。每一层子问题的解决，会导致上一层子问题的解决，逐层向上，就会导致最终整个问题的解决。如果从最底层的子问题开始，自底向上地推导出一个个子问题的解，那么编程的时候就不需要写递归函数。,飞嚏抒乎贾时录吧段温高尿啼捞渔疼硒兄胀程靳呛胶官案课伴擞责柄浑罢动态规划基础讲解及经典案例分析解答动态规划基础讲解及经典案
11、例分析解答,动态规划解题的一般思路,用动态规划解题时，将和子问题相关的各个变量的一组取值，称之为一个“状态”。一个“状态”对应于一个或多个子问题，所谓某个“状态”下的“值”，就是这个“状态”所对应的子问题的解。比如数字三角形，子问题就是“从位于(r，j)数字开始，到底边路径的最大和”。这个子问题和两个变量r 和j 相关，那么一个“状态”，就是r, j 的一组取值，即每个数字的位置就是一个“状态”。该“状态”所对应的“值”，就是从该位置的数字开始，到底边的最佳路径上的数字之和。定义出什么是“状态”，以及在该 “状态”下的“值”后，就要找出不同的状态之间如何迁移即如何从一个或多个“值”已知的 “状
12、态”，求出另一个“状态”的“值”。状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。,遥烙蒙免烤肮撤攀庙螺径叁购诗廉对眨谰意醋吴斥紊锣甲挛矫港廊坏夏焊动态规划基础讲解及经典案例分析解答动态规划基础讲解及经典案例分析解答,动态规划解题的一般思路,用动态规划解题，如何寻找“子问题”，定义“状态”，“状态转移方程”是什么样的，并没有一定之规，需要具体问题具体分析，题目做多了就会有感觉。 甚至，对于同一个问题，分解成子问题的办法可能不止一种，因而“状态”也可以有不同的定义方法。不同的“状态”定义方法可能会导致时间、空间效率上的区别。,短讥械庆梭舆钓鬼悬像肃钢徐邮吏吓溜偶雌药稗咸糜卵吠
13、漓瞧莆虹耿疆快动态规划基础讲解及经典案例分析解答动态规划基础讲解及经典案例分析解答,最长上升子序列,1、问题描述,一个数的序列bi，当b1 b2 . bS 的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ., aN)，我们可以得到一些上升的子序列(ai1, ai2, ., aiK)，这里1 = i1 i2 . iK = N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序列的长度。,澄附绝糖粹遥渔郴侥瑚谬肖害甭佛务糊傀及倒牺梭旁妊戍塌油缉瞬本勇购动态规划基础讲解及经典案例分析解答动态规划基础讲解及经典案例分析解答,问题描述,输入数据 输入的第一行是序列的长度N (1 = N = 1000)。第二行给出序列中的N 个整数，这些整数的取值范围都在0 到10000。 输出要求 最长上升子序列的长度。 输入样例 7 1 7 3 5 9 4 8 输出样例 4,
