《hduacm版04动态规划入门》由会员分享，可在线阅读，更多相关《hduacm版04动态规划入门（31页珍藏版）》请在金锄头文库上搜索。
1、ACM程序设计程序设计7/20/20241今天，今天，你你 ACAC吗？吗？依然没有7/20/20242每周一星（每周一星（3）：）：亚里土多德亚里土多德7/20/20243第第四四讲讲动态规划动态规划（Dynamic programmingDynamic programming）7/20/20244一、一、经典问题经典问题：数塔问题数塔问题 有形如下图所示的数塔，从顶部出发，在每有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。层，要求找出一条路径，使路径上的值最大。7/20/20
2、245用用暴力暴力的方法，可以吗？的方法，可以吗？7/20/20246这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（230= 10243 109=10亿）。试想一下：试想一下：7/20/20247 拒绝拒绝暴力，暴力，倡导倡导和谐和谐7/20/20248从顶点出发时到底向左走还是向右走应取决于是从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走
3、向又要取决于再下一层上的最同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。直到倒数第二层时就非常明了。如数字如数字2，只要选择它下面较大值的结点，只要选择它下面较大值的结点19前进就前进就可以了。所以实际求解时，可从底层开始，层层递进，可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。最后得到最大值。结论：自顶向下的分析，自底向上的计算。结论：自顶向下的分析，自底向上的计算。考虑一下：考虑一下：7/20/20249二、二、经典问题经典问题：最长有序子序列：最长有序子序
4、列I012345678NumI1472583697/20/202410解决方案：解决方案：I012345678NumI147258369FI1232343457/20/202411思考思考 11601160 FatMouses FatMouses Speed Speed Sample Input6008 1300 6008 1300 6000 2100 500 6000 2100 500 2000 1000 2000 1000 4000 1100 4000 1100 3000 6000 3000 6000 2000 8000 2000 8000 1400 6000 1400 6000 1200
5、 2000 1200 2000 1900 1900 Sample Output4 4 5 9 77/20/202412再再思考思考（1087 1087 期末考试题）期末考试题）Super Jumping! Jumping!Super Jumping! Jumping!Juping!Juping! 7/20/202413解题思路？解题思路？7/20/202414三、三、经典问题经典问题：最长公共子序列：最长公共子序列HDOJ-1159HDOJ-1159：Sample Inputabcfbc abfcababcfbc abfcabprogramming contest programming co
6、ntest abcd mnp abcd mnp Sample OutputSample Output 4 4 2 2 0 07/20/202415辅助空间变化示意图辅助空间变化示意图7/20/202416f(i,j)= n由于f(i,j)只和f(i-1,j-1), f(i-1,j)和f(i,j-1)有关, 而在计算f(i,j)时, 只要选择一个合适的顺序, 就可以保证这三项都已经计算出来了, 这样就可以计算出f(i,j). 这样一直推到f(len(a),len(b)就得到所要求的解了.f(i-1,j-1)+1 (ai=bj)max(f(i-1,j),f(i,j-1) (ai!=bj) 子结构特
7、征：子结构特征：7/20/202417四四、经典问题经典问题：14211421 搬寝室搬寝室Sample InputSample Input 2 1 2 1 1 31 3Sample OutputSample Output 4 47/20/202418第一感觉：第一感觉：n根据题目的要求，每次提的两个物根据题目的要求，每次提的两个物品重量差越小越好，是不是每次提品重量差越小越好，是不是每次提的物品一定是重量相邻的物品呢？的物品一定是重量相邻的物品呢？n证明：假设四个从小到大的数：a、b、c、d，只需证明以下表达式成立即可：n(a-b)2+(c-d)2 (a-c)2+(b-d)2n(a-b)2+
8、(c-d)2=2k）nn个物品选二对，个物品选二对，7/20/202422五、五、经典问题经典问题：1058 1058 Humble NumbersHumble NumbersProblem Description Problem Description A number whose only prime factors are 2,3,5 A number whose only prime factors are 2,3,5 or 7 is called a humble number. The or 7 is called a humble number. The sequence 1,
9、2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, . shows the 15, 16, 18, 20, 21, 24, 25, 27, . shows the first 20 humble numbers. first 20 humble numbers. Write a program to find and print the nth Write a program to find and print th
10、e nth element in this sequence element in this sequence 7/20/202423算法分析算法分析：典型的：典型的DP!n1 -?n1 -2=min(1*2,1*3,1*5,1*7)n1 -2 -3=min(2*2,1*3,1*5,1*7)n1 -2 -3 - 4 = min(2*2,2*3,1*5,1*7)n1 -2 -3 - 4 -5= min(3 3*2,2 2*3,1*5,1*7)7/20/202424状态转移方程？状态转移方程？nF(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7)(ni,j,k,m)特别的：i
11、,j,k,m 只有在本项被选中后才移动7/20/202425关键问题：关键问题：n这个题目的哪些这个题目的哪些经验值得我们借经验值得我们借鉴？鉴？7/20/202426思考：思考：免费馅饼免费馅饼 7/20/202427如何解决？如何解决？请发表见解请发表见解 7/20/202428如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。 小结小结：DPDP的基本思想的基本思想 7/20/202429课后任务：课后任务：DIYDIY在线作业在线作业(4):(4): 201003201003ACMACM程序设计在线作业（程序设计在线作业（4 4）动态规划入门动态规划入门7/20/202430Welcome to HDOJWelcome to HDOJ该该加油加油了了 7/20/202431
