资源描述：
《《工学动态规划》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ACM程序设计杭州电子科技大学刘春英acm@hdu.edu.cn7/14/20211这个月赛，你吗？参加7/14/20212每周一星（3）：10071221江春辉7/14/20213知识回顾上一讲:递推求解...7/14/20214第四讲动态规划（Dynamicprogramming）7/14/20215一、经典问题：数塔问题有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。7/14/20216用暴力的方法，可以吗？7/14/20217这道题如果用枚举法（暴力思想），在数塔层数
2、稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（2^30=1024^3>10^9=10亿）。试想一下：7/14/20218拒绝暴力，倡导和谐～7/14/20219从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。如数字2，只要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。结论：自顶
3、向下的分析，自底向上的计算。考虑一下：7/14/202110二、经典问题：最长有序子序列I012345678Num[I]1472583697/14/202111解决方案：I012345678Num[I]147258369F[I]1232343457/14/202112思考1160FatMouse'sSpeedSampleInput60081300600021005002000100040001100300060002000800014006000120020001900SampleOutput445977/14/202113再思考（1087期末考
4、试题）SuperJumping!Jumping!Juping!7/14/202114解题思路？7/14/202115三、经典问题：最长公共子序列HDOJ-1159：SampleInputabcfbcabfcab programmingcontest abcdmnpSampleOutput4 2 07/14/202116abcfbca111111b122222f122333c123334a123334b123344辅助空间变化示意图7/14/202117f(i,j)={由于f(i,j)只和f(i-1,j-1),f(i-1,j)和f(i,j-1)有关
5、,而在计算f(i,j)时,只要选择一个合适的顺序,就可以保证这三项都已经计算出来了,这样就可以计算出f(i,j).这样一直推到f(len(a),len(b))就得到所要求的解了.f(i-1,j-1)+1(a[i]==b[j])max(f(i-1,j),f(i,j-1))(a[i]!=b[j])子结构特征：7/14/202118四、经典问题：1421搬寝室SampleInput2113SampleOutput47/14/202119第一感觉：根据题目的要求，每次提的两个物品重量差越小越好，是不是每次提的物品一定是重量相邻的物品呢？证明：假设四个从小
6、到大的数：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……(略)7/14/202120预备工作：排序！7/14/202121第二感觉：对于一次操作，显然提的物品重量越接近越好，是不是可以贪心呢？请思考…考虑以下情况：1458什么结论？7/14/202122详细分析：从最简单的情况考虑：2个物品选一对，结论显然结论？4个物品选一对？（如何利用前面的知识）3个物品选一对，…n个物品选一对，…最终问题：n个物品选k对，如何？（n>
7、=2k）n个物品选二对，…7/14/202123五、经典问题：1058HumbleNumbersProblemDescriptionAnumberwhoseonlyprimefactorsare2,3,5or7iscalledahumblenumber.Thesequence1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,...showsthefirst20humblenumbers. Writeaprogramtofindandprintthenthelementinthissequenc
8、e7/14/202124算法分析：典型的DP!1->?1->2=min(1*2,1*3,1*5,1*7)1->2->3=min(2*2,
