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