【正文】 一類問題，它們的活動過程可以分為若干個階段，而且在任意一個階段 x，過程在階段 x以后的行為，僅依賴于x階段的過程狀態(tài)，而與 x之前過程如何達到這種狀態(tài)的方式無關，這樣的過程就構(gòu)成一個多階段決策過程。由此提出了解決這類問題的“最優(yōu)化原理”，創(chuàng)建了最優(yōu)化問題的一種新的算法設計方法 動態(tài)規(guī)劃。 動態(tài)規(guī)劃解題方法是一種高效率的解題方法，可以解決相當大的信息量，其時間復雜度通常為 O(n2)、 O(n3)等。它適用的原則是優(yōu)化原則，它可以將整體優(yōu)化分解為若干個局部優(yōu)化。 動態(tài)規(guī)劃算法 動態(tài)規(guī)劃算法的一般模式： 1）劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意有序或可排序。 2）確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處的各種情況用不同狀態(tài)表示出來。 3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程：一般是根據(jù)相鄰兩個階段各狀態(tài)之間的關系來確定決策。 4）尋找終止條件：給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式，必須有一個遞推的終止條件。 5）編寫程序。 例如：求從 A點到 D點的最短路徑。 通過三段路程的最短路徑可以用各自的最短路徑，求他們 的和。其和為 AB， BC， CD的最短路徑之和，將其作為整個問題的最短路徑，且其解法為最優(yōu)解。 [算法分析 ]：窮舉法：時間復雜度： n1*n2*n3, 貪心法：時間復雜度： n1+n2+n3,可行 。 動態(tài)規(guī)劃算法的應用 例 設有一個三角形的數(shù)塔，頂點為根結(jié)點，每個結(jié)點有一個整數(shù)值。從頂點出發(fā)，可以向左走或向右走，如圖： 從根結(jié)點 13出發(fā)向左、向右的路徑長度可以是： 13117147，其和為 52 1311121413，其和為 63 若要求從根結(jié)點開始，找出一條路徑，使路徑之和最大，若存在多條請輸出任意一條。 解析： 1）用窮舉法：從根結(jié)點開始，將所有可能的路徑求和，找出最大值，但算法時間復雜度使問題成為不可能。當 N=1， P=1 N=2， P=2 N=3， P=4 …… N=k,P=2k1。 當 N=50， P=249=500萬億條路徑。 2）用貪心法：本題若用貪心法則： 1311121413，其和為 63，實際上存在另一條路徑： 138261524，其和為 86；貪心法問題所在：眼光短淺。 3） 動態(tài)規(guī)劃求解：動態(tài)規(guī)劃求解問題的過程歸納為： 自頂向下分析，自底向上計算 ?；痉椒ǎ? 劃分階段：按三角形的行，劃分階段，若有 n行，則有 n1個階段，找到問題求解的最優(yōu)途徑。 A、從根結(jié)點 13出發(fā)，選取它的兩個方向中的一條支路，選擇的依據(jù)是比較兩個支路中其路徑和最大的支路； B、設 x為從 11出發(fā)到底端的最大路徑值， y為從 8到底端的最大路徑值。 C、 if xy then 選擇 x 且取得最大和為 13+x else 選擇 y 且取得最大和為 13+y 這樣，原先求根結(jié)點到底端的最大路徑問題，變?yōu)閺?11出發(fā)和和從 8出發(fā)求路徑和的子問題。 同理，求從 11出發(fā)到底端的最大路徑問題可以轉(zhuǎn)化為從 12出發(fā)和從 7出發(fā)的最大路徑問題。 [決策：路徑和最大 ] [狀態(tài)轉(zhuǎn)移方程： Fi=max(Fi1(左 ), Fi1(右 ))] A、當?shù)降箶?shù)第二層時，每個結(jié)點其后繼僅有兩個結(jié)點，可以直接比較，選擇最大值為前進方向，從而求得從根結(jié)點開始到底端的最大路徑。 [終止條件 ] B、自底向上計算 從底層開始，本身數(shù)即為最大數(shù)； 倒數(shù)第二層的計算，取決于底層的數(shù)據(jù)： 12+6=18， 13+14=27，24+15=39， 24+8=32 最后的路徑為： 13826824 4）數(shù)據(jù)結(jié)構(gòu)及算法設計： A、圖形轉(zhuǎn)化：直角三角形，便于搜索，向下或向右 B、用三維數(shù)組表示數(shù)塔： a[x,y,1]表示行、列及結(jié)點本身數(shù)據(jù) a[x,y,2]表示能夠取得最大值 a[x,y,3]表示前進方向， 0向下， 1向右。 C、算法：數(shù)組初始化，輸入每個結(jié)點值以及初始的最大路徑、前進方向 0；從倒數(shù)第二層開始向上一層求最大路徑，共循環(huán) n1次；從頂向下，輸出路徑：關鍵是 j的值，由于行逐漸遞增，表示向下，究竟是向下還是向右取決于列的值。若 j的值比原先多 1則向右，否則向下。 源程序分析 例 求一組數(shù)列的最長不下降序列 。 [ 問題描述 ] ：設有一個正整數(shù)序列 b1,b2,b3,… ,bn, 若下標為i1i2i3,… ik且有 bi1≤ bi2≤ … bik則稱存在一個長度為 k的不下降序列 。 在一個數(shù)列中可能有多個不下降序列 ， 輸出最長的序列 。 [解法分析 ]： 數(shù)據(jù)結(jié)構(gòu)：假設有 N個數(shù)的數(shù)列 ， 設定數(shù)組為 N行 3 列的整型數(shù)組 b。 b[i,1]表示第 i個數(shù)的數(shù)值本身； b[i,2]表示第 i項到最后一項最長不下降序列的長度； b[i,3]表示最長不下降序列經(jīng)過此項之后 ， 后面繼續(xù) 的項 ， 若 b[i,3] =0則表示后面沒有連接的數(shù) 。 算法 ： 初始化： b[i,1]存放本身數(shù)據(jù) ， b[i,2]表示最長的長度 ， 開始為1， b[i,3]開始為 0， 表示沒有連接 。 從倒數(shù)第二項開始計算 ， 由于在其后僅有一個數(shù)據(jù)項 ， 所以計算機做一次比較后保存最大數(shù) 。 同樣再從倒數(shù)第 3項開始 ， 其后有兩項 ， 因此必須在最后 2項中找出最長的作為連接項 。 用表格表示所構(gòu)造出的 b[1..n,1..3]初始表如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 13 7 9 16 38 24 37 18 44 19 21 22 63 15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 b[i,1] b[i,2] b[i,3] 求解過程 ： 從倒數(shù)第二項開始計算 ， 由于后面僅有 1項 ， 所以做一次比較 ， 因 6315， 不符合問題要求 ， 不作任何鏈接 ， 長度仍為 1。 從倒數(shù)第三項開始在其后有 2項 ， 因此需要做兩次比較 ， 得到目前最長的不下降序列長度為 2， 其鏈接情況如下表： ... 11 12 13 14 ... 22 63 15 ... 2 1 1 ... 13 0 0 ... 11 12 13 14 ... 21 22 63 15 ... 3 2 1 1 ... 12 13 0 0 一般處理過程： 在 i+1,i+2,...,n項中 ， 找出比 b[i,1]大的最長長度 m， 以及位置 K； 若 m0， 則 b[i,2]:=L+1。b[i,3]:=k。 本題通過計算 ， 最終結(jié)果為： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 13 7 9 16 38 24 37 18 44 19 21 22 63 15 7 8 7 6 3 4 3 5 2 4 3 2 1 1 4 3 4 8 9 7 9 10 13 11 12 13 0 0 源程序分析 題例 、 某國為了防御敵國的導彈襲擊 ， 發(fā)展出一種導彈攔截系統(tǒng) 。 但是這種攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度 ， 但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度 。 某天 ， 雷達捕捉到敵國的導彈來襲 ， 由于該系統(tǒng)還在試用階段 。 所以一套系統(tǒng)有可能不能攔截所有的導彈 。 輸入導彈依次飛來的高度 （ 雷達給出的高度不大于 30000的正整數(shù) ） 。 計算一套導彈攔截系統(tǒng)最多能夠攔截多少枚導彈 。 例 一個 n行 m列迷宮 （ 1 ≤ n,m ≤ 50） ,入口位于左上角 ， 規(guī)定只能往下或往右走 。 迷宮中存在一些障礙物無法通過 。 迷宮的某些地方里藏有不同價值的寶藏 。 求所能收集的寶藏的最大價值 。 子結(jié)構(gòu)劃分： 逐行掃描 。 考慮迷宮某一點 ， 要求走到這一點所 能收集的寶藏的最大價值 ， 先求出走到它在邊和 上邊所能收集的寶藏的最大價值 。 [算法分析 ]： 變量的定義： Ai,j=迷宮第 i行第 j列的寶藏價值 ， 1表示障礙物； F i,j=走到第 i行第 j列所能收集大寶藏的最大價值 。 狀態(tài)轉(zhuǎn)移方程 ： Fi,j=max{Fi,j1|j1, Fi1,j |i1}+ Ai,j 邊界條件： F1,1 = A1， 1 answer= Fn,m 源程序 在一個操場上擺放著一行共 n堆石子 。 現(xiàn)要將石子有序地合并成一堆 。 規(guī)定每次只能選相鄰的兩堆合并成新的一堆 ， 并將新的一堆石子數(shù)記為該次合并的得分 ， 請編程計算出將 n堆石子合并成一堆的最小得分 。 采藥 【 問題描述 】 辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個難題。醫(yī)師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大?！? 如果你是辰辰，你能完成這個任務嗎？ 【 輸入文件 】 輸入文件 T（ 1 = T = 1000）和 M（ 1 = M = 100），用一個空格隔開， T代表總共能夠用來采藥的時間， M代表山洞里的草藥的數(shù)目。接下來的 M行每行包括兩個在 1到 100之間（包括 1和100）的整數(shù)，分別表示采摘某株草藥的時間和這株草藥的價值。 【 輸出文件 】 輸出文件 ，這一行只包含一個整數(shù)，表示在規(guī)定的時間內(nèi)，可以采到的草藥的最大總價值。 【 數(shù)據(jù)規(guī)模 】 對于 30%的數(shù)據(jù) ， M = 10； 對于全部的數(shù)據(jù) ， M = 100。