動(dòng)態(tài)規(guī)劃

1、動(dòng)態(tài)規(guī)劃（四）,,求最長(zhǎng)不下降序列,問題描述： 設(shè)有一個(gè)正整數(shù)的序列：b1, b2, …bn, 對(duì)于下標(biāo)i1<i2<…ih, 若有bi1<bi2<…<bih，則稱存在一個(gè)長(zhǎng)度為h的不下降序列。例如，下列數(shù)13 7 9 16 38 24 27 38 44 49 21 52 63 15對(duì)于下標(biāo) i1=1,i2=4,i3=5,i4=9,i5=13, 且滿足13

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

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

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

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

7、析,當(dāng)我們定義問題F(i)為以bi結(jié)束的最長(zhǎng)不下降序列時(shí)，則問題F(I)有I-1個(gè)子問題：F(1), F(2),…, F(I-1)。我們要使F(I)最大，則要找到一個(gè)F(j)最大的子問題，且同時(shí)滿足Bj < Bi，這時(shí)F(I) := F(j) + 1例如 F(4) 有3個(gè)子問題，分別是F(1), F(2), F(3), 它們都滿足bj < bi的條件，而最大的F(j)=2, 因此F(4) := F(3)+1=3, 而它的前

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

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