【正文】 可能需要先計算 D（ 5）的值；之后在分別調(diào)用遞歸函數(shù)計算 D（ 2）、 D（ 3）、 D（ 4）的時候，都有可能需要先計算 D（ 5）的值。然后，對 i從 1到 n分別調(diào)用這個遞歸函數(shù)，就可以計算出 D（ 1）、 D（ 2）、 …… D（ n）。 ? 根據(jù)以上分析，可歸納出問題的動態(tài)規(guī)劃遞歸方程為： ? 假設(shè)系統(tǒng)最多能攔截的導(dǎo)彈數(shù)為 dmax（即問題的最優(yōu)值），則 ? dmax （ i為被系統(tǒng)攔截的第一枚導(dǎo)彈的順序號） ? 所以，要計算問題的最優(yōu)值 dmax，需要分別計算出 D（ 1）、 D（ 2）、 …… D（ n）的值，然后將它們進行比較，找出其中的最大值。 ? 設(shè) D(i)為第 i枚導(dǎo)彈被攔截之后，這套系統(tǒng)最多還能攔截的導(dǎo)彈數(shù)（包含被攔截的第 i枚）。 ? 也就是說，在當前狀態(tài) s≤x1 下，問題的最優(yōu)解 Y所包含的子問題（序列 X1）的解（序列 Y1）也是最優(yōu)的。 ? 如果 y1=x1，即飛來的第一枚導(dǎo)彈被成功攔截。 ? 題目要求我們計算這套系統(tǒng)最多能攔截的導(dǎo)彈數(shù)，并依次輸出被攔截導(dǎo)彈的高度，實際上就是要求我們在導(dǎo)彈依次飛來的高度序列中尋找一個最長非遞增子序列。 ? 輸出 輸出只有一行是這套系統(tǒng)最多能攔截的導(dǎo)彈數(shù)。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。 ④ 決策過程是與階段發(fā)展過程逆向而行 。 ③ 各階段選取的決策 ， 一般與 “ 時序 ” 有關(guān) ， 決策依賴于當前的狀態(tài) ， 又隨即引起狀態(tài)的轉(zhuǎn)移 ， 整個決策序列就是在變化的狀態(tài)中產(chǎn)生出來 ， 故有 “ 動態(tài) ” 含義 。 如下圖所示： 決策 決策 決策狀態(tài) 狀態(tài) 狀態(tài) 狀態(tài) 狀態(tài)1 2 n② 在處理各階段決策的選取上 ， 不僅只依賴于當前面臨的狀態(tài) ， 而且還要注意對以后的發(fā)展 。 從引例的求解過程可以得到以下啟示： ① 對一個問題是否用上述方法求解 ， 其關(guān)鍵在于能否將問題轉(zhuǎn)化為相互聯(lián)系的決策過程相同的多個階段決策問題 。 即 A→B 3→C 2→D 2→E 上述最短路線問題的計算過程 ， 也可借助于圖形直觀的表示出來： A B1 B2 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 6 3 2 4 2 6 5 3 4 6 3 3 3 3 4 圖中各點上方框的數(shù) ， 表示該點到 E的最短距離 。 ? 由于我們考慮的是從全局上解決求 A到 E的最短路問題，而不是就某一階段解決最短路線，因此可考慮從最后一階段開始計算，由后向前逐步推至 A點： 第四階段 ， 由 D1到 E只有一條路線 ， 其長度 f4（ D1） =3， 同理 f4（ D2） =4。 A B1 B2 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 6 3 2 4 2 6 5 3 4 6 3 3 3 3 4 如果用完全枚舉法 ， 則可供選擇的路線有 3 3 2 1=18（條 ） ， 將其一一比較才可找出最短路線： A→B 1→C 2→D 3→E 其長度為 12。 一、例子（最短路問題） 假如上圖是一個線路網(wǎng)絡(luò)，兩點之間連線上的數(shù)字表示兩點間的距離（或費用），我們的問題是要將貨物從 A地運往 E地，中間通過 B、 C、 D三個區(qū)域，在區(qū)域內(nèi)有多條路徑可走，現(xiàn)求一條由 A到 E的線路，使總距離最短（或總費用最?。?。 ?通常不同的子問題個數(shù)隨問題的大小呈多項式增長。 這種性質(zhì)稱為 子問題的重疊性質(zhì) 。 a b c ?在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。一個問題滿足最優(yōu)化原理又稱其 為 最優(yōu)子結(jié)構(gòu)性質(zhì) 。 用空間換時間 動態(tài)規(guī)劃算法的基本要素 一、最優(yōu)子結(jié)構(gòu) ?一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。i++) f[i] = f[i1]+f[i2]。 for(i=3。 f[1]=f[2]=1。而不是可愛的AC Why？ 子問題的重疊性 ? 將上述遞歸算法展開 : ? 可以看出 f(n1) 被調(diào)用 1次 , f(n2)被調(diào)用 2次 , 等等 . ? 這將導(dǎo)致大量的調(diào)用 ? 最終解為： 樹形遞歸 計算過程中存在冗余計算，為了除去冗余計算，可以從已知條件開始計算，并記錄計算過程中的中間結(jié)果。 ? 如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計算，從而得到多項式時間算法。不同子問題的數(shù)目常常只有多項式量級。 幾類算法的經(jīng)典名言 ? 動態(tài)規(guī)劃：不做重復(fù)的事； ? 貪心法：只選最好的； ? 分支定界法：沒戲的就殺掉； ? 回溯法：碰壁就回頭。 如果一個問題可將其過程劃分為若干個相互聯(lián)系的階段問題 ，且它的每一階段都需進行決策 ， 則這類問題均可用動態(tài)規(guī)劃方法進行求解 。第二章 動態(tài)規(guī)劃及其應(yīng)用 本周 POJ上做題：動態(tài)規(guī)劃 ? 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 動態(tài)規(guī)劃是 1951年由美國數(shù)學(xué)家貝爾曼 （ Richard Bellman)提出 ， 它是解決一類多階段決策問題的優(yōu)化方法 ，也是考察問題的一種途徑 。 動態(tài)規(guī)劃方法是現(xiàn)代企業(yè)管理中的一種重要決策方法 。 根據(jù)多階段決策過程的時序和決策過程的演變 ， 動態(tài)規(guī)劃方法有以下四種類型：離散確定型 、 離散隨機型 、 連續(xù)確定型和連續(xù)隨機型 。 作人生規(guī)劃要善于利用動態(tài)規(guī)劃； 找女朋友要善于利用好貪心算法； 人生重大決策要活學(xué)活用回溯法； 算法總體思想 ? 動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = 為什么動態(tài)規(guī)劃比遞歸算法有效？ ? 但是經(jīng)分解得到的子問題往往不是互相獨立的。在用分治法求解時，有些子問題被重復(fù)計算了許多次，因此利用遞歸算法得到的算法往往是指數(shù)復(fù)雜度的算法。 n = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 n/2 T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n) POJ 2753 Fibonacci數(shù)列例子： ? 確定 Fibonacci sequence fn項的值 : ? 考慮 Fibonacci sequence的遞歸定義 : ? 我們將得到如下的遞歸算法 : 在 POJ上遞交之后，返回的結(jié)果是：Time Li