动态规划（四）

求最长不下降序列 问题描述： 设有一个正整数的序列：b1, b2, …bn, 对于下标i1<i2<…ih, 若有bi1<bi2<…<bih，则称存在一个长度为h的不下降序列。 例如，下列数 13 7 9 16 38 24 27 38 44 49 21 52 63 15 对于下标 i1=1,i2=4,i3=5,i4=9,i5=13, 且满足 13 < 16 < 38 < 44 < 63 则存在长度为5的不下降序列。 但是，我们看到还存在其它的不下降序列。如 7 < 9 < 16 < 18 < 19 < 21 < 22 < 63 则存在长度为8的不下降序列。 问题：当给定b1, b2, …bn后，求出最长的不下降序列h及这个序列中的各个数。

最长不下降序列-分析 动态规划的难点之一：怎样定义问题？你首先要能定义出问题是什么，才能进一步定义出子问题是什么，然后才能证明或者直观地感觉问题与子问题之间是否存在最优子结构性质。 从前往后分析。从序列长度为1开始，逐步放大序列长度，2，3，4……看看要求的结果的变化规律。我们可能会很直接地想到，把问题定义成当前最长不下降序列。 序列长度 序列 当前最长不下降序列长度 1 13 1 2 13 7 1 3 13 7 9 2 4 13 7 9 16 3 5 13 7 9 16 38 4 6 13 7 9 16 38 24 4 （24<38, 长度不增加） 7 13 7 9 16 38 24 27 ? (凭什么计算出当前值？) 由于当前记录的最长不下降序列是 7 9 16 38 ，而实际上应该有了更长的子序列 7 9 16 24 27。 13 7 9 16 38 24 27 38 44 49 21 52 63 15

最长不下降序列-分析 我们定义F(i) 为原始序列长度为I 的最长不下降序列，则F(I)只有一个子问题F(I-1)，即原始序列长度为I-1的最长不下降序列。而且我们无法得出问题与子问题之间的“最优子结构”性质。 重新思考关于问题的定义。我们定义问题F(i)为以bi结束的最长不下降序列。则得到如下的分析结果： 下标I 序列 F(I) 前趋结点下标 13 1 1 13 7 1 2 13 7 9 2 2 13 7 9 16 3 3 13 7 9 16 38 4 4 13 7 9 16 38 24 4 4 13 7 9 16 38 24 27 5 6 13 7 9 16 38 24 27 38 6 7 13 7 9 16 38 24 27 38 44 49 21 52 63 15

最长不下降序列-分析 当我们定义问题F(i)为以bi结束的最长不下降序列时，则问题F(I)有I-1个子问题：F(1), F(2),…, F(I-1)。我们要使F(I)最大，则要找到一个F(j)最大的子问题，且同时满足Bj < Bi，这时F(I) := F(j) + 1 例如 F(4) 有3个子问题，分别是F(1), F(2), F(3), 它们都满足bj < bi的条件，而最大的F(j)=2, 因此F(4) := F(3)+1=3, 而它的前趋结点下标是j 下标I 序列 F(I) 前趋结点下标 13 1 1 13 7 1 2 13 7 9 2 2 13 7 9 16 3 3 13 7 9 16 38 4 4 13 7 9 16 38 24 4 4 13 7 9 16 38 24 27 5 6 13 7 9 16 38 24 27 38 6 7 13 7 9 16 38 24 27 38 44 49 21 52 63 15

最长不下降序列-分析 这样定义问题，我们就看到了“最优子结构”性质。因此可以应用动态规划方法求解问题。 请你分析本问题的重叠子问题性质。 请你递归地定义问题的解。 F(I) = Max{F(j)+1 | j < I 且 bj <= bi} 本递归式的边界条件是什么？ F(1) = 1, f(I)= 1 请你思考本题要求的结果是F(n)吗？如果不是，那么最后要求的结果怎样利用用动态规划求得的问题和子问题的值得到？ 怎样输出显示最长不下降序列的各个结点？ 13 7 9 16 38 24 27 38 44 49 21 52 63 15

最长不下降序列-分析 写出完整的求最长不下降序列的程序。上机调试。 13 7 9 16 38 24 27 38 44 49 21 52 63 15

最长不下降序列-讨论 如果从后向前分析原始序列，会得到正确的结果吗？又该怎样定义问题？写出从后向前求最长不下降序列的程序。 13 7 9 16 38 24 27 38 44 49 21 52 63 15

最长不下降序列应用-导弹拦截 问题见《信息学竞赛指导》P323例题五十八。 请独立分析解出本问题。