《ACM程序设计教学PPT动态规划.ppt》由会员分享，可在线阅读，更多相关《ACM程序设计教学PPT动态规划.ppt（32页珍藏版）》请在三一办公上搜索。
1、ACM程序设计,杭州电子科技大学 刘春英,2023/2/13,2,4月20日组队赛,你 吗？,报名了,2023/2/13,3,每周一星（5）：,Gavintop,2023/2/13,4,知识回顾,递推求解.,2023/2/13,5,第六讲,动态规划（Dynamic programming）,2023/2/13,6,一、经典问题：数塔问题,有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。,2023/2/13,7,用暴力的方法，可以吗？,2023/2/13,8,这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），
2、则需要列举出的路径条数将是一个非常庞大的数目（230=10243 109=10亿）。,试想一下：,2023/2/13,9,拒绝暴力，倡导和谐,2023/2/13,10,从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。如数字2，只要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。,考虑一下：,2023/2/13,1
3、1,思考：免费馅饼,2023/2/13,12,如何解决？,请发表见解,2023/2/13,13,威威猫系列故事打地鼠,再思考：,2023/2/13,14,二、经典问题：最长有序子序列,2023/2/13,15,解决方案：,2023/2/13,16,思考 1160 FatMouses Speed,Sample Input6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900,Sample Output4 4 5 9 7,2023/2/13,17,再思考（1087 期末考试题）
4、,Super Jumping!Jumping!Juping!,解题思路？,2023/2/13,19,三、经典问题：最长公共子序列,HDOJ-1159：Sample Inputabcfbc abfcabprogramming contest abcd mnp,Sample Output 4 2 0,2023/2/13,20,辅助空间变化示意图,2023/2/13,21,f(i,j)=由于f(i,j)只和f(i-1,j-1),f(i-1,j)和f(i,j-1)有关,而在计算f(i,j)时,只要选择一个合适的顺序,就可以保证这三项都已经计算出来了,这样就可以计算出f(i,j).这样一直推到f(len
5、(a),len(b)就得到所要求的解了.,f(i-1,j-1)+1(ai=bj),max(f(i-1,j),f(i,j-1)(ai!=bj),子结构特征：,2023/2/13,22,四、经典问题：1421 搬寝室,Sample Input 2 1 1 3Sample Output 4,2023/2/13,23,第一感觉：,根据题目的要求，每次提的两个物品重量差越小越好，是不是每次提的物品一定是重量相邻的物品呢？,证明：假设四个从小到大的数：a、b、c、d，只需证明以下表达式成立即可：(a-b)2+(c-d)2(a-c)2+(b-d)2(a-b)2+(c-d)2(a-d)2+(b-c)2(略),
6、2023/2/13,24,预备工作：,排序！,2023/2/13,25,第二感觉：,对于一次操作，显然提的物品重量越接近越好，是不是可以贪心呢？请思考,考虑以下情况：1 4 5 8,什么结论？,2023/2/13,26,详细分析：,从最简单的情况考虑：2个物品选一对，结论显然,结论？,4个物品选一对？（如何利用前面的知识）,3个物品选一对，,n个物品选一对，,最终问题：n个物品选k对，如何？（n=2k）,n个物品选二对，,2023/2/13,27,五、经典问题：1058 Humble Numbers,Problem Description A number whose only prime f
7、actors are 2,3,5 or 7 is called a humble number.The sequence 1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,.shows the first 20 humble numbers.Write a program to find and print the nth element in this sequence,2023/2/13,28,算法分析：典型的DP!,1-?,1-2=min(1*2,1*3,1*5,1*7),1-2-3=min(2*2,1*3,1*5,1*7),1-2-3
8、-4=min(2*2,2*3,1*5,1*7),1-2-3-4-5=min(3*2,2*3,1*5,1*7),2023/2/13,29,状态转移方程？,F(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7)(ni,j,k,m)特别的：i,j,k,m 只有在本项被选中后才移动,2023/2/13,30,如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。,小结：DP的基本思想,2023/2/13,31,课后任务：,WebDIY在线作业(6):201303ACM程序设计作业（6）刘春英老师,2023/2/13,32,Welcome to HDOJ,该加油了,
