動態(tài)規(guī)劃

1、動態(tài)規(guī)劃（四）,,求最長不下降序列,問題描述： 設有一個正整數(shù)的序列：b1, b2, …bn, 對于下標i1<i2<…ih, 若有bi1<bi2<…<bih，則稱存在一個長度為h的不下降序列。例如，下列數(shù)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

2、< 16 < 38 < 44 < 63則存在長度為5的不下降序列。但是，我們看到還存在其它的不下降序列。如7 < 9 < 16 < 18 < 19 < 21 < 22 < 63則存在長度為8的不下降序列。問題：當給定b1, b2, …bn后，求出最長的不下降序列h及這個序列中的各個數(shù)。,最長不下降序列-分析,動態(tài)規(guī)劃的難點之一：怎樣定義問題？你首先要能定義出

3、問題是什么，才能進一步定義出子問題是什么，然后才能證明或者直觀地感覺問題與子問題之間是否存在最優(yōu)子結(jié)構(gòu)性質(zhì)。從前往后分析。從序列長度為1開始，逐步放大序列長度，2，3，4……看看要求的結(jié)果的變化規(guī)律。我們可能會很直接地想到，把問題定義成當前最長不下降序列。序列長度序列 當前最長不下降序列長度1131213 71313 7 92413 7 9

4、163513 7 9 16 384613 7 9 16 38 244 （24<38, 長度不增加）713 7 9 16 38 24 27? (憑什么計算出當前值？) 由于當前記錄的最長不下降序列是 7 9 16 38 ，而實際上應該有了更長的子序列 7 9 16 24 27。,13 7 9 16 38 24 27 38

5、 44 49 21 52 63 15,最長不下降序列-分析,我們定義F(i) 為原始序列長度為I 的最長不下降序列，則F(I)只有一個子問題F(I-1)，即原始序列長度為I-1的最長不下降序列。而且我們無法得出問題與子問題之間的“最優(yōu)子結(jié)構(gòu)”性質(zhì)。重新思考關于問題的定義。我們定義問題F(i)為以bi結(jié)束的最長不下降序列。則得到如下的分析結(jié)果：下標I序列F(I)前趨結(jié)點下標131113 7

6、1213 7 92213 7 9 163313 7 9 16 384413 7 9 16 38 244413 7 9 16 38 24 275613 7 9 16 38 24 27 3867,13 7 9 16 38 24 27 38 44 49 21 52 63 15,最長不下降序列-分

7、析,當我們定義問題F(i)為以bi結(jié)束的最長不下降序列時，則問題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, 而它的前

8、趨結(jié)點下標是j,13 7 9 16 38 24 27 38 44 49 21 52 63 15,下標I序列F(I)前趨結(jié)點下標131113 7 1213 7 92213 7 9 163313 7 9 16 384413 7 9 16 38 244413 7 9 16 38 24 27

9、5613 7 9 16 38 24 27 3867,最長不下降序列-分析,這樣定義問題，我們就看到了“最優(yōu)子結(jié)構(gòu)”性質(zhì)。因此可以應用動態(tài)規(guī)劃方法求解問題。請你分析本問題的重疊子問題性質(zhì)。請你遞歸地定義問題的解。F(I) = Max{F(j)+1 | j < I 且 bj <= bi}本遞歸式的邊界條件是什么？F(1) = 1, f(I)= 1請你思考本題要求的結(jié)果是F(n)嗎？如果

10、不是，那么最后要求的結(jié)果怎樣利用用動態(tài)規(guī)劃求得的問題和子問題的值得到？怎樣輸出顯示最長不下降序列的各個結(jié)點？,13 7 9 16 38 24 27 38 44 49 21 52 63 15,最長不下降序列-分析,寫出完整的求最長不下降序列的程序。上機調(diào)試。,13 7 9 16 38 24 27 38 44 49 21 52 63 15,最長不下降序列-討論,如果從后向前分析原始序列，