《数据结构域算法设计-ACM课件(lecture_04)动态规划(1)_20080317》由会员分享，可在线阅读，更多相关《数据结构域算法设计-ACM课件(lecture_04)动态规划(1)_20080317（46页珍藏版）》请在金锄头文库上搜索。
1、ACM程序设计,2018/10/18,2,第四讲,动态规划(1) （Dynamic programming）,2018/10/18,3,先热身一下,2018/10/18,4,(1466)计算直线的交点数,问题描述：平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。 输入：n（n=20） 输出：每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数。 样例输入 4 样例输出 0 3 4 5 6,2018/10/18,5,初步分析:,我们知道:n条直线互不平行且无三线共点的最多交点数max=1+2+(n-1)=n(n-1)/2,但本题不这么简单，因为问题问的是：
2、这些直线有多少种不同的交点数？,2018/10/18,6,思考2分钟:如何解决?,2018/10/18,7,然后，假设 0+4*0+0=0； 2、第四条与其中两条平行，交点数为0+(n-1)*1+0=3; 3、第四条与其中一条平行，这两条平行直线和另外两点直线的交点数为(n-2)*2=4,而另外两条直线既可能平行也可能相交，因此可能交点数为：0+（n-2）*2+0=4 或者 0+(n-2)*2+1=5 4、 第四条直线不与任何一条直线平行，交点数为：0+(n-3)*3+0=3 或0+ (n-3)*3+2=5 或0+ (n-3)*3+3=6 即n=4时，有0个，3个，4个，5个，6个不同交点数。
3、,重点分析n的情况：,2018/10/18,10,从上述n=4的分析过程中，我们发现： m条直线的交点方案数 =（m-r）条平行线与r条直线交叉的交点数+ r条直线本身的交点方案 =（m-r）*r+r条之间本身的交点方案数（0=r 109=10亿）。,试想一下：,2018/10/18,16,拒绝暴力，倡导和谐,2018/10/18,17,从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。如数字2，只
4、要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。,考虑一下：,2018/10/18,18,21,19,28,21,38,34,39,50,54,63,2018/10/18,19,二、思考题：最长有序子序列,2018/10/18,20,解决方案：,Fi的求法：maxi=1;for(j=0; jmaxi)maxi=Fj+1;Fi=maxi;,Fi的求法：Fi=1;for(j=0; jFi)Fi=Fj+1;,2018/10/18,21,三、1160 FatMouses Speed,Sample Input6008
5、 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900,Sample Output 4 4 5 9 7,2018/10/18,22,题目分析：,设Micei.W表示第i只老鼠的重量，Micei.S表示第i只老鼠的速度。 我们先对Mice进行排序，以W为第一关键字，从小到大，S为第二关键字，从大到小。 设fi为Micei至Micen最长的序列长度。考虑某一个fi，则有： fi = max( fi , fj+1) (1 Micej.W，Micei.S Micej.S) 其中，初始条件为
6、fi=1 (i=1, 2, ., n)。,2018/10/18,23,Qestion:,两个问题有本质区别吗？,2018/10/18,24,思考（期末考试题）：,1087 Super Jumping! Jumping! Jumping!,解题思路？,2018/10/18,26,解题思路,/子问题的构造，sumi表示最后一步落在第i格中的走法所得到的最高分数，sumi可以这样利用更小的子问题算出来， /在位于i之前且比ai小的那些格中找对应sum最大的记为max，则sumi=max+ai /注意原问题的解不是an，而是a1.n中的最大值,2018/10/18,27,四、1159 Common S
7、ubsequence,Sample Input abcfbc abfcab programming contest abcd mnp,Sample Output 4 2 0,2018/10/18,28,辅助空间变化示意图,2018/10/18,29,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(a),len(b)就得到所要求的解了.,f(i-1,j-1)+1 (ai=bj),max(f(i-1,j
8、),f(i,j-1) (ai!=bj),子结构特征：,2018/10/18,30,理论小结,2018/10/18,31,如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。,一、动态规划的基本思想,2018/10/18,32,二、动态规划的基本步骤,动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找
9、到具有最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可以按以下几个步骤进行：,2018/10/18,33,（1）找出最优解的性质，并刻画其结构特征。 （2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。 （4）根据计算最优值时得到的信息，构造一个最优解。其中（1）（3）步是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省去。若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解。,基本步骤,2018/10/18,34,三、动态规划问题的特征,动
10、态规划算法的有效性依赖于问题本身所具有的两个重要性质：1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。,2018/10/18,35,思考：免费馅饼,2018/10/18,36,如何解决？,子问题：最后1秒最多能接住几个，最后两秒、最后两秒. 还与当时他站的位置有关 子问题是二维的： Tij表示第i秒若站在位置j，从第i秒之后能
11、接住多少个馅饼,2018/10/18,37,Tij表示第i秒若站在位置j，从第i秒之后能接住多少个馅饼 Tij:若第i+1秒站在位置j，那么第i秒他可能到达的位置是j-1,j,j+1,去那个位置接到馅饼最多？ T(i,j-1) Tij =Ti+1j+max T(i,j) T(i,j+1),再考虑一下j=0和j=10的情况即可,2018/10/18,38,计算过程,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7,2018/10/18,39,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7,2018/10/18,40,有的同学用从1到最大t
12、的递推,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7,居然是正确的！ 这就是测试实例故意设的陷阱，让你意识不到自己的错误,2018/10/18,41,我给几个实例你试试： 6个馅饼： (3,1) (3,1) (2,2) (2,2）(1,3)(1,4),0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7,2018/10/18,42,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7,有的同学用从1到最大t的递推,得到答案是6； 而正确答案是1,因为一开始他站在位置5，第一秒根本到不了位置3，得不到那连个馅饼，第二秒也根本到不了位置2，第三秒也到不了位置1，第四秒能到位置1，得到一个馅饼 如果从第一秒正推下去，前三行都要特殊处理，所以倒推比较好,2018/10/18,43,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7,一开始它站在位置5, c05=1即所求解,
