《杭电ACM课件(lecture04)动态规划》由会员分享，可在线阅读，更多相关《杭电ACM课件(lecture04)动态规划（37页珍藏版）》请在金锄头文库上搜索。
1、ACM 程序设计计算机学院 刘春英*1今天，你 了吗？ACDate2每周一星（3）：05059127陈谦益Date3第四讲动态规划(1) （ Dynamic programming）Date4先热身一下Date5（1466）计算直线的交点数问题描述：平面上有n条直线，且无三线共点，问这些直 线能有多少种不同交点数。 输入：n（n 无交点； 2、第四条与其中两条平行，交点数为(n-1)*1+0=3; 3、第四条与其中一条平行，这两条平行直线和另外两点直线的交点数 为(n-2)*2=4,而另外两条直线既可能平行也可能相交，因此可能交点数 为：（n-2）*2+0=4 或者 (n-2)*2+1=5 4
2、、 第四条直线不与任何一条直线平行，交点数为：(n-3)*3+0=3 或者 (n-3)*3+2=5 或者 (n-3)*3+3=6即n=4时，有0个，3个，4个，5个，6个不同交点数。Date9从上述n=4的分析过程中，我们发现：m条直线的交点方案数 =（m-r）条平行线与r条直线交叉的交点数+ r条直线本身的交点方案=（m-r）*r+r条之间本身的交点方案数（ 1 109=10亿） 。Date13拒绝暴力，倡导和谐Date14考虑一下： 从顶点出发时到底向左走还是向右走应取决 于是从左走能取到最大值还是从右走能取到最 大值，只要左右两道路径上的最大值求出来了 才能作出决策。 同样，下一层的走向
3、又要取决于再下一层上 的最大值是否已经求出才能决策。这样一层一 层推下去，直到倒数第二层时就非常明了。 如数字2，只要选择它下面较大值的结点19前 进就可以了。所以实际求解时，可从底层开始 ，层层递进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。Date15Understand?Date16二、思考题：最长有序子序列I012345678NumI 147258369请回答：穷举（暴力）方法的时间复杂度是多少？Date17解决方案：I012345678NumI 147258369FI123234345Date18三、HDOJ_1160 FatMouses Speed l题目链 接 Sam
4、ple Input 6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900 Sample Output4 4 5 9 7Date19题目分析：l设Micei.W表示第i只老鼠的重量， Micei.S表示第i只老鼠的速度。我们先对 Mice进行排序，以W为第一关键字，从小 到大，S为第二关键字，从大到小。l设fi为Micei至Micen最长的序列长度 。考虑某一个fi，则有： lfi = max(fi, fj+1) (1 Micej.W，Micei.S Micej.S) l其
5、中，初始条件为fi=1 (i=1, 2, ., n)。 Date20Qestion: 两个问题有 本质区别吗 ？Date21思考（期末考试题）：Super Jumping! Jumping!Jumping! Date22解题思路？Date23四、HDOJ_1159 Common Subsequencel题目链接 Sample Input abcfbc abfcab programming contest abcd mnp Sample Output420Date24请先计算暴力算法的时间复杂度： （当然是指最坏情况！） ？Date25abcfbc a111111 b122222 f122333
6、 c123334 a123334 b123344辅助空间变化示意图Date26子结构特征：lf(i,j)= l由于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) Date27理论总结Date28如果各个子问题不是独立的，不同的 子问题的个数只是多项式量级，如果 我们能够保
7、存已经解决的子问题的答 案，而在需要的时候再找出已求得的 答案，这样就可以避免大量的重复计 算。由此而来的基本思路是，用一个 表记录所有已解决的子问题的答案， 不管该问题以后是否被用到，只要它 被计算过，就将其结果填入表中。 一、动态规划的基本思想 Date29二、动态规划的基本步骤 动态规划算法通常用于求解具有某 种最优性质的问题。在这类问题中， 可能会有许多可行解。每一个解都对 应于一个值，我们希望找到具有最优 值（最大值或最小值）的那个解。设 计一个动态规划算法，通常可以按以 下几个步骤进行： Date30（1）找出最优解的性质，并刻画其结构特征 。 （2）递归地定义最优值。 （3）以自
8、底向上的方式计算出最优值。 （4）根据计算最优值时得到的信息，构造一 个最优解。其中（1）（3）步是动态规划算法的 基本步骤。在只需要求出最优值的情形，步 骤（4）可以省去。若需要求出问题的一个 最优解，则必须执行步骤（4）。此时，在 步骤（3）中计算最优值时，通常需记录更 多的信息，以便在步骤（4）中，根据所记 录的信息，快速构造出一个最优解。Date31三、动态规划问题的特征动态规划算法的有效性依赖于问题本身所具 有的两个重要性质： 1、最优子结构：当问题的最优解包含了其子 问题的最优解时，称该问题具有最优子结构 性质。 2、重叠子问题：在用递归算法自顶向下解问 题时，每次产生的子问题并不总是新问题， 有些子问题被反复计算多次。动态规划算法 正是利用了这种子问题的重叠性质，对每一 个子问题只解一次，而后将其解保存在一个 表格中，在以后尽可能多地利用这些子问题 的解。Date32思考：免费馅饼 Date33如何解决？请发表见解 Date34Any Question?Date35附：课后作业lACM ProgrammingExercise（4）lDP入门练习题目： 1003 、 1466 、1087、1159、1176 1058、1069、2059、2084Date36ACM, 天天见！ Date37
