多階段決策過程（multistep decision process）是指這樣一類特殊的活動(dòng)過程，過程可以按時(shí)間順序分解成若干個(gè)相互聯(lián)系的階段，在每一個(gè)階段都需要做出決策，全部過程的決策是一個(gè)決策序列。動(dòng)態(tài)規(guī)劃（dynamic programming）算法是解決多階段決策過程最優(yōu)化問題的一種常用方法，難度比較大，技巧性也很強(qiáng)。利用動(dòng)態(tài)規(guī)劃算法，可以優(yōu)雅而高效地解決很多貪婪算法或分治算法不能解決的問題。動(dòng)態(tài)規(guī)劃算法的基本思想是：將待求解的問題分解成若干個(gè)相互聯(lián)系的子問題，先求解子問題，然后從這些子問題的解得到原問題的解；對(duì)于重復(fù)出現(xiàn)的子問題，只在第一次遇到的時(shí)候?qū)λM(jìn)行求解，并把答案保存起來，讓以后再次遇到時(shí)直接引用答案，不必重新求解。動(dòng)態(tài)規(guī)劃算法將問題的解決方案視為一系列決策的結(jié)果，與貪婪算法不同的是，在貪婪算法中，每采用一次貪婪準(zhǔn)則，便做出一個(gè)不可撤回的決策；而在動(dòng)態(tài)規(guī)劃算法中，還要考察每個(gè)最優(yōu)決策序列中是否包含一個(gè)最優(yōu)決策子序列，即問題是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
動(dòng)態(tài)規(guī)劃算法的有效性依賴于待求解問題本身具有的兩個(gè)重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。
1、最優(yōu)子結(jié)構(gòu)性質(zhì)。如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，我們就稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（即滿足最優(yōu)化原理）。最優(yōu)子結(jié)構(gòu)性質(zhì)為動(dòng)態(tài)規(guī)劃算法解決問題提供了重要線索。
2、子問題重疊性質(zhì)。子問題重疊性質(zhì)是指在用遞歸算法自頂向下對(duì)問題進(jìn)行求解時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題會(huì)被重復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對(duì)每一個(gè)子問題只計(jì)算一次，然后將其計(jì)算結(jié)果保存在一個(gè)表格中，當(dāng)再次需要計(jì)算已經(jīng)計(jì)算過的子問題時(shí)，只是在表格中簡(jiǎn)單地查看一下結(jié)果，從而獲得較高的解題效率。
當(dāng)我們已經(jīng)確定待解決的問題需要用動(dòng)態(tài)規(guī)劃算法求解時(shí)，通?？梢园凑找韵虏襟E設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法：
1、分析問題的最優(yōu)解，找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；
2、遞歸地定義最優(yōu)值；
3、采用自底向上的方式計(jì)算問題的最優(yōu)值；
4、根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。
1～3步是動(dòng)態(tài)規(guī)劃算法解決問題的基本步驟，在只需要計(jì)算最優(yōu)值的問題中，完成這三個(gè)基本步驟就可以了。如果問題需要構(gòu)造最優(yōu)解，還要執(zhí)行第4步；此時(shí)，在第3步通常需要記錄更多的信息，以便在步驟4中，有足夠的信息快速地構(gòu)造出最優(yōu)解。
下面通過對(duì)具體實(shí)例的分析，幫助大家領(lǐng)會(huì)可用動(dòng)態(tài)規(guī)劃算法求解的問題應(yīng)具有的兩個(gè)性質(zhì)以及動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想。
例：攔截導(dǎo)彈（問題來源：1999年全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克分區(qū)聯(lián)賽高中組復(fù)賽試題第一題）
某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。
輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000 的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，并依次輸出被攔截的導(dǎo)彈飛來時(shí)候的高度。
樣例：
INPUT
389 207 155 300 299 170 158 65
OUTPUT
6（最多能攔截的導(dǎo)彈數(shù)）
389 300 299 170 158 65
分析：因?yàn)橹挥幸惶讓?dǎo)彈攔截系統(tǒng)，并且這套系統(tǒng)除了第一發(fā)炮彈能到達(dá)任意高度外，以后的每一發(fā)炮彈都不能高于前一發(fā)炮彈的高度；所以，被攔截的導(dǎo)彈應(yīng)該按飛來的高度組成一個(gè)非遞增序列。題目要求我們計(jì)算這套系統(tǒng)最多能攔截的導(dǎo)彈數(shù)，并依次輸出被攔截導(dǎo)彈的高度，實(shí)際上就是要求我們?cè)趯?dǎo)彈依次飛來的高度序列中尋找一個(gè)最長(zhǎng)非遞增子序列。
設(shè)X={x1,x2,…,xn}為依次飛來的導(dǎo)彈序列，Y={y1,y2,…,yk}為問題的最優(yōu)解（即X的最長(zhǎng)非遞增子序列），s為問題的狀態(tài)（表示導(dǎo)彈攔截系統(tǒng)當(dāng)前發(fā)送炮彈能夠到達(dá)的最大高度，初值為s=∞——第一發(fā)炮彈能夠到達(dá)任意的高度）。如果y1= x1，即飛來的第一枚導(dǎo)彈被成功攔截。那么，根據(jù)題意“每一發(fā)炮彈都不能高于前一發(fā)的高度”，問題的狀態(tài)將由s=∞變成s≤x1（x1為第一枚導(dǎo)彈的高度）；在當(dāng)前狀態(tài)下，序列Y1={y2,…,yk}也應(yīng)該是序列X1={x2,…,xn}的最長(zhǎng)非遞增子序列（大家用反證法很容易證明）。也就是說，在當(dāng)前狀態(tài)s≤x1下，問題的最優(yōu)解Y所包含的子問題（序列X1）的解（序列Y1）也是最優(yōu)的。這就是攔截導(dǎo)彈問題的最優(yōu)子結(jié)構(gòu)性質(zhì)。
設(shè)D(i) 為第i枚導(dǎo)彈被攔截之后，這套系統(tǒng)最多還能攔截的導(dǎo)彈數(shù)（包含被攔截的第i枚）。我們可以設(shè)想，當(dāng)系統(tǒng)攔截了第k枚導(dǎo)彈xk，而xk又是序列X={x1, x2,…,xn}中的最小值，即第k枚導(dǎo)彈為所有飛來的導(dǎo)彈中高度最低的，則有D(k)=1；當(dāng)系統(tǒng)攔截了最后一枚導(dǎo)彈xn，那么，系統(tǒng)最多也只能攔截這一枚導(dǎo)彈了，即D(n)=1；其它情況下，也應(yīng)該有D(i)≥1。根據(jù)以上分析，可歸納出問題的動(dòng)態(tài)規(guī)劃遞歸方程為：
假設(shè)系統(tǒng)最多能攔截的導(dǎo)彈數(shù)為dmax（即問題的最優(yōu)值），則
dmax （i為被系統(tǒng)攔截的第一枚導(dǎo)彈的順序號(hào)）
所以，要計(jì)算問題的最優(yōu)值dmax，需要分別計(jì)算出D(1)、D(2)、……D(n)的值，然后將它們進(jìn)行比較，找出其中的最大值。根據(jù)上面分析出來的遞歸方程，我們完全可以設(shè)計(jì)一個(gè)遞歸函數(shù)，采用自頂向下的方法計(jì)算D(i)的值。然后，對(duì)i從1到n分別調(diào)用這個(gè)遞歸函數(shù)，就可以計(jì)算出D(1)、D (2)、……D(n)。但這樣將會(huì)有大量的子問題被重復(fù)計(jì)算。比如在調(diào)用遞歸函數(shù)計(jì)算D(1)的時(shí)候，可能需要先計(jì)算D(5)的值；之后在分別調(diào)用遞歸函數(shù)計(jì)算D(2)、D(3)、D(4)的時(shí)候，都有可能需要先計(jì)算D(5)的值。如此一來，在整個(gè)問題的求解過程中，D(5)可能會(huì)被重復(fù)計(jì)算很多次，從而造成了冗余，降低了程序的效率。
其實(shí)，通過以上分析，我們已經(jīng)知道：D(n)=1。如果將n作為階段對(duì)問題進(jìn)行劃分，根據(jù)問題的動(dòng)態(tài)規(guī)劃遞歸方程，我們可以采用自底向上的方法依次計(jì)算出D(n-1)、D(n-2)、……D(1)的值。這樣，每個(gè)D(i)的值只計(jì)算一次，并在計(jì)算的同時(shí)把計(jì)算結(jié)果保存下來，從而避免了有些子問題被重復(fù)計(jì)算的情況發(fā)生，提高了程序的效率。算法代碼如下：
for i=1 to n
D(i)=1
next i
for i=n-1 to 1 step -1
for j=i+1 to n
if x(j)<=x(i) and D(i)<D(j)+1 then
D(i)=D(j)+1
endif
next j
next i
dmax=0:xh=1
rem dmax用來保存問題的最優(yōu)值（系統(tǒng)最多能攔截的導(dǎo)彈數(shù)）；xh用來保存第一枚被攔截的導(dǎo)彈的順序號(hào)，以便后面構(gòu)造最優(yōu)解
for i=1 to n
if D(i)>dmax then
dmax=D(i)
xh=i
endif
next i
我們?cè)谟?jì)算最優(yōu)值時(shí)保存了被攔截的第一枚導(dǎo)彈的順序號(hào)xh。接下來通過這個(gè)信息構(gòu)造問題的最優(yōu)解（由所有被攔截的導(dǎo)彈的高度組成的非遞增序列）。算法代碼如下：
print x(xh)
for i=xh+1 to n
if x(i)<=x(i-1) then
print x(i)
endif
next i
