第二次课动态规划.pptVIP

第二章动态规划及其应用 本周POJ上做题：动态规划 1037 A decorative fence、 1050 To the Max、1088 滑雪、 1125 Stockbroker Grapevine、1141 Brackets Sequence、 1159 Palindrome、1160 Post Office、 1163 The Triangle、1458 Common Subsequence、 1579 Function Run Fun、1887 Testing the CATCHER、 1953 World Cup Noise、2386 Lake Counting 几类算法的经典名言 动态规划：不做重复的事； 贪心法：只选最好的； 分支定界法：没戏的就杀掉； 回溯法：碰壁就回头。 算法总体思想 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题 为什么动态规划比递归算法有效？ 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次，因此利用递归算法得到的算法往往是指数复杂度的算法。 如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。 POJ 2753 Fibonacci数列例子： 确定Fibonacci sequence fn项的值: 考虑Fibonacci sequence的递归定义: 我们将得到如下的递归算法: 子问题的重叠性 将上述递归算法展开: 可以看出 f(n-1) 被调用 1次, f(n-2)被调用 2次, 等等. 这将导致大量的调用 最终解为： 树形递归 动态规划 例：POJ 2753 Fibonacci数列 int f[n+1]; f[1]=f[2]=1; int I; for(i=3;i=n;i++) f[i] = f[i-1]+f[i-2]; cout f[n] endl; 用空间换时间 显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。 由于我们考虑的是从全局上解决求A到E的最短路问题，而不是就某一阶段解决最短路线，因此可考虑从最后一阶段开始计算，由后向前逐步推至A点： 拦截导弹 （poj1887 ） 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入 输入数据为导弹依次飞来的高度，所有高度值均为不大于30000的正整数。 输出 输出只有一行是这套系统最多能拦截的导弹数。 输入样例 389 207 155 300 299 170 158 65 输入样例 6 题目分析 因为只有一套导弹拦截系统，并且这套系统除了第一发炮弹能到达任意高度外，以后的每一发炮弹都不能高于前一发炮弹的高度；所以，被拦截的导弹应该按飞来的高度组成一个非递增序列。 题目要求我们计算这套系统最多能拦截的导弹数，并依次输出被拦截导弹的高度，实际上就是要求我们在导弹依次飞来的高度序列中寻找一个最长非递增子序列。 设X={x1,x2,…,xn}为依次飞来的导弹序列，Y={y1,y2,…,yk}为问题的最优解（即X的最长非递增子序列），s为问题的状态（表示导弹拦截系统当前发送炮弹能够到达的最大高度，初值为s=∞——第一发炮弹能够到达任意的高度）。 如果y1=x1，即飞来的第一枚导弹被成功拦截。那么，根据题意“每一发炮弹都不能高于前一发的高度”，问题的状态将由s=∞变成s≤x1（x1为第一枚导弹的高度）； 在当前状态下，序列Y1={y2,…,yk}也应该是序列X1={x2,…,xn}的最长非递增子序列（大家用反证法很容易证明）。 也就是说，在当前状态s≤x1下，问题的最优解Y所包含的子问题（序列X1）的解（序列Y1）也是最优的。这就是拦截导弹问题的最优子结构性质。 设D(i)为第i枚导弹被拦截之后，这套系统最多还能拦截的导弹数（包含被拦截的第i枚）。 我们可以设想，当系统拦截了第k枚导弹xk，而xk又是序列X={x1,x2,…,xn}中的最小值，即第k枚导弹为所有飞来的导弹中高度最低的，