最长不下降序列动态规划 4.ppt

《最长不下降序列动态规划 4.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划（四）求最长不下降序列问题描述：设有一个正整数的序列：b1,b2,…bn,对于下标i1

2、h及这个序列中的各个数。最长不下降序列-分析动态规划的难点之一：怎样定义问题？你首先要能定义出问题是什么，才能进一步定义出子问题是什么，然后才能证明或者直观地感觉问题与子问题之间是否存在最优子结构性质。从前往后分析。从序列长度为1开始，逐步放大序列长度，2，3，4……看看要求的结果的变化规律。我们可能会很直接地想到，把问题定义成当前最长不下降序列。序列长度序列当前最长不下降序列长度113121371313792413791635137916384613791638244（24<38,长度不增加）7137916382427

3、?(凭什么计算出当前值？)由于当前记录的最长不下降序列是791638，而实际上应该有了更长的子序列79162427。13791638242738444921526315最长不下降序列-分析我们定义F(i)为原始序列长度为I的最长不下降序列，则F(I)只有一个子问题F(I-1)，即原始序列长度为I-1的最长不下降序列。而且我们无法得出问题与子问题之间的“最优子结构”性质。重新思考关于问题的定义。我们定义问题F(i)为以bi结束的最长不下降序列。则得到如下的分析结果：下标I序列F(I)前趋结点下标13111371213792

4、213791633137916384413791638244413791638242756137916382427386713791638242738444921526315最长不下降序列-分析当我们定义问题F(i)为以bi结束的最长不下降序列时，则问题F(I)有I-1个子问题：F(1),F(2),…,F(I-1)。我们要使F(I)最大，则要找到一个F(j)最大的子问题，且同时满足Bj

5、j)=2,因此F(4):=F(3)+1=3,而它的前趋结点下标是j13791638242738444921526315下标I序列F(I)前趋结点下标131113712137922137916331379163844137916382444137916382427561379163824273867最长不下降序列-分析这样定义问题，我们就看到了“最优子结构”性质。因此可以应用动态规划方法求解问题。请你分析本问题的重叠子问题性质。请你递归地定义问题的解。F(I)=Max{F(j)+1

6、j

7、是什么？F(1)=1,f(I)=1请你思考本题要求的结果是F(n)吗？如果不是，那么最后要求的结果怎样利用用动态规划求得的问题和子问题的值得到？怎样输出显示最长不下降序列的各个结点？13791638242738444921526315最长不下降序列-分析写出完整的求最长不下降序列的程序。上机调试。13791638242738444921526315最长不下降序列-讨论如果从后向前分析原始序列，会得到正确的结果吗？又该怎样定义问题？写出从后向前求最长不下降序列的程序。13791638242738444921526315va

8、rf:array[1..5000]oflongint;a:array[1..5000]oflongint;i,n,j,k,l:longint;beginreadln(n);fori:=1tondoread(a[i]);f[1]:=1;fori:=2tondobeginf[i]:=1;forj:=1toi-1doifa[i]>=a[j]theniff[j]+1>f[i]thenf[i]:=f[j]+1;end;j:=0;fori:=1tondoifj

9、);end.