動(dòng)態(tài)規(guī)劃經(jīng)典教程

31/31動(dòng)態(tài)規(guī)劃經(jīng)典教程動(dòng)態(tài)規(guī)劃經(jīng)典教程

引言：本人在做過(guò)一些題目后對(duì)DP有些感想，就寫(xiě)了這個(gè)總結(jié)：

第一節(jié)動(dòng)態(tài)規(guī)劃基本概念

一，動(dòng)態(tài)規(guī)劃三要素：階段，狀態(tài)，決策。

他們的概念到處都是，我就不多說(shuō)了，我只說(shuō)說(shuō)我對(duì)他們的理解：

如果把動(dòng)態(tài)規(guī)劃的求解過(guò)程看成一個(gè)工廠的生產(chǎn)線，階段就是生產(chǎn)某個(gè)商品的不同的環(huán)節(jié)，狀態(tài)就是工件當(dāng)前的形態(tài)，決策就是對(duì)工件的操作。顯然不同階段是對(duì)產(chǎn)品的一個(gè)前面各個(gè)狀態(tài)的小結(jié)，有一個(gè)個(gè)的小結(jié)構(gòu)成了最終的整個(gè)生產(chǎn)線。每個(gè)狀態(tài)間又有關(guān)聯(lián)（下一個(gè)狀態(tài)是由上一個(gè)狀態(tài)做了某個(gè)決策后產(chǎn)生的）。

下面舉個(gè)例子：

要生產(chǎn)一批雪糕，在這個(gè)過(guò)程中要分好多環(huán)節(jié)：購(gòu)買(mǎi)牛奶，對(duì)牛奶提純處理，放入工廠加工，加工后的商品要包裝，包裝后就去銷售……，這樣沒(méi)個(gè)環(huán)節(jié)就可以看做是一個(gè)階段；產(chǎn)品在不同的時(shí)候有不同的狀態(tài)，剛開(kāi)始時(shí)只是白白的牛奶，進(jìn)入生產(chǎn)后做成了各種造型，從冷凍庫(kù)拿出來(lái)后就變成雪糕（由液態(tài)變成固態(tài)=_=||）。每個(gè)形態(tài)就是一個(gè)狀態(tài)，那從液態(tài)變成固態(tài)經(jīng)過(guò)了冰凍這一操作，這個(gè)操作就是一個(gè)決策。

一個(gè)狀態(tài)經(jīng)過(guò)一個(gè)決策變成了另外一個(gè)狀態(tài)，這個(gè)過(guò)程就是狀態(tài)轉(zhuǎn)移，用來(lái)描述狀態(tài)轉(zhuǎn)移的方程就是狀態(tài)轉(zhuǎn)移方程。

經(jīng)過(guò)這個(gè)例子相信大家對(duì)動(dòng)態(tài)規(guī)劃有所了解了吧。

下面在說(shuō)說(shuō)我對(duì)動(dòng)態(tài)規(guī)劃的另外一個(gè)理解：

用圖論知識(shí)理解動(dòng)態(tài)規(guī)劃：把動(dòng)態(tài)規(guī)劃中的狀態(tài)抽象成一個(gè)點(diǎn)，在有直接關(guān)聯(lián)的狀態(tài)間連一條有向邊，狀態(tài)轉(zhuǎn)移的代價(jià)就是邊上的權(quán)。這樣就形成了一個(gè)有向無(wú)環(huán)圖AOE網(wǎng)（為什么無(wú)環(huán)呢？往下看）。對(duì)這個(gè)圖進(jìn)行拓?fù)渑判?，刪除一個(gè)邊后同時(shí)出現(xiàn)入度為0的狀態(tài)在同一階段。這樣對(duì)圖求最優(yōu)路徑就是動(dòng)態(tài)規(guī)劃問(wèn)題的求解。

二，動(dòng)態(tài)規(guī)劃的適用范圍

動(dòng)態(tài)規(guī)劃用于解決多階段決策最優(yōu)化問(wèn)題，但是不是所有的最優(yōu)化問(wèn)題都可以用動(dòng)態(tài)規(guī)劃解答呢？

一般在題目中出現(xiàn)求最優(yōu)解的問(wèn)題就要考慮動(dòng)態(tài)規(guī)劃了，但是否可以用還要滿足兩個(gè)條件：

最優(yōu)子結(jié)構(gòu)（最優(yōu)化原理）

無(wú)后效性

最優(yōu)化原理在下面的最短路徑問(wèn)題中有詳細(xì)的解答；

什么是無(wú)后效性呢？

就是說(shuō)在狀態(tài)i求解時(shí)用到狀態(tài)j而狀態(tài)j就解有用到狀態(tài)k…..狀態(tài)N。

而求狀態(tài)N時(shí)有用到了狀態(tài)i這樣求解狀態(tài)的過(guò)程形成了環(huán)就沒(méi)法用動(dòng)態(tài)規(guī)劃解答了，這也是上面用圖論理解動(dòng)態(tài)規(guī)劃中形成的圖無(wú)環(huán)的原因。

也就是說(shuō)當(dāng)前狀態(tài)是前面狀態(tài)的完美總結(jié)，現(xiàn)在與過(guò)去無(wú)關(guān)。。。

當(dāng)然，有是換一個(gè)劃分狀態(tài)或階段的方法就滿足無(wú)后效性了，這樣的問(wèn)題仍然可以用動(dòng)態(tài)規(guī)劃解。

三，動(dòng)態(tài)規(guī)劃解決問(wèn)題的一般思路。

拿到多階段決策最優(yōu)化問(wèn)題后，第一步要判斷這個(gè)問(wèn)題是否可以用動(dòng)態(tài)規(guī)劃解決，如果不能就要考慮搜索或貪心了。當(dāng)卻定問(wèn)題可以用動(dòng)態(tài)規(guī)劃后，就要用下面介紹的方法解決問(wèn)題了：（1）模型匹配法：

最先考慮的就是這個(gè)方法了。挖掘問(wèn)題的本質(zhì)，如果發(fā)現(xiàn)問(wèn)題是自己熟悉的某個(gè)基本的模型，就直接套用，但要小心其中的一些小的變動(dòng)，現(xiàn)在考題辦都是基本模型的變形套用時(shí)要小心條件，三思而后行。這些基本模型在先面的分類中將一一介紹。

（2）三要素法

仔細(xì)分析問(wèn)題嘗試著確定動(dòng)態(tài)規(guī)劃的三要素，不同問(wèn)題的卻定方向不同：

先確定階段的問(wèn)題：數(shù)塔問(wèn)題，和走路問(wèn)題（詳見(jiàn)解題報(bào)告）

先確定狀態(tài)的問(wèn)題：大多數(shù)都是先確定狀態(tài)的。

先確定決策的問(wèn)題：背包問(wèn)題。（詳見(jiàn)解題報(bào)告）

一般都是先從比較明顯的地方入手，至于怎么知道哪個(gè)明顯就是經(jīng)驗(yàn)問(wèn)題了，多做題就會(huì)發(fā)現(xiàn)。

（3）尋找規(guī)律法：

這個(gè)方法很簡(jiǎn)單，耐心推幾組數(shù)據(jù)后，看他們的規(guī)律，總結(jié)規(guī)律間的共性，有點(diǎn)貪心的意思。

（4）邊界條件法

找到問(wèn)題的邊界條件，然后考慮邊界條件與它的領(lǐng)接狀態(tài)之間的關(guān)系。這個(gè)方法也很起效。

（5）放寬約束和增加約束

這個(gè)思想是在陳啟鋒的論文里看到的，具體內(nèi)容就是給問(wèn)題增加一些條件或刪除一些條件使問(wèn)題變的清晰。

第二節(jié)動(dòng)態(tài)規(guī)劃分類討論

這里用狀態(tài)維數(shù)對(duì)動(dòng)態(tài)規(guī)劃進(jìn)行了分類：

1.狀態(tài)是一維的

1．1下降/非降子序列問(wèn)題：

問(wèn)題描述：{挖掘題目的本質(zhì)，一但抽象成這樣的描述就可以用這個(gè)方法解}

在一個(gè)無(wú)序的序列a1,a2,a3,a4…an里，找到一個(gè)最長(zhǎng)的序列滿足：aiaj>ak…>am,且i>j>k…>m.（最長(zhǎng)下降子序列）。

問(wèn)題分析：

如果前i-1個(gè)數(shù)中用到ak(ak>ai或akai(或ajai){最長(zhǎng)下降子序列}

實(shí)現(xiàn)求解的部分代碼：

opt[0]:=maxsize；{maxsize為maxlongint或-maxlongint}

fori:=1tondo

forj:=0toi-1do

if(a[j]>a[i])and(opt[j]+1>opt[i])then

opt[i]:=opt[j]+1;

ans:=-maxlongint;

fori:=1tondo

ifopt[i]>ansthenans:=opt[i];{ans為最終解}

復(fù)雜度：從上面的實(shí)現(xiàn)不難看出時(shí)間復(fù)雜度為O（N2），空間復(fù)雜度O（N）；

例題1攔截導(dǎo)彈(missile.pas/c/cpp)來(lái)源：NOIP1999(提高組)第一題

【問(wèn)題描述】

某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。

輸入導(dǎo)彈依次飛來(lái)的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。

【輸入文件】missile.in

單獨(dú)一行列出導(dǎo)彈依次飛來(lái)的高度。

【輸出文件】missile.out

兩行，分別是最多能攔截的導(dǎo)彈數(shù)，要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)

【輸入樣例】

38920715530029917015865

【輸出樣例】

6

2

【問(wèn)題分析】

有經(jīng)驗(yàn)的選手不難看出這是一個(gè)求最長(zhǎng)非升子序列問(wèn)題，顯然標(biāo)準(zhǔn)算法是動(dòng)態(tài)規(guī)劃。

以導(dǎo)彈依次飛來(lái)的順序?yàn)殡A段，設(shè)計(jì)狀態(tài)opt[i]表示前i個(gè)導(dǎo)彈中攔截了導(dǎo)彈i可以攔截最多能攔截到的導(dǎo)彈的個(gè)數(shù)。

狀態(tài)轉(zhuǎn)移方程：

opt[i]=max(opt[j])+1(h[i]>=h[j],0==a[i])and

(opt[j]+1>opt[i])then

opt[i]:=opt[j]+1;

anslen:=0;

fori:=1tondo

ifopt[i]>anslenthen

anslen:=opt[i];

fillchar(opt,sizeof(opt),0);

a[0]:=-maxlongint;

fori:=1tondo

forj:=i-1downto0do

if(a[j](opt[j]+1>opt[i])then

opt[i]:=opt[j]+1;

anstime:=0;

fori:=1tondo

ifopt[i]>anstimethen

anstime:=opt[i];

end;

procedureprint;

begin

writeln(anslen);

writeln(anstime);

close(input);

close(output);

end;

begin

init;

main;

print;

end.

例題二合唱隊(duì)形(chorus.pas/c/cpp)來(lái)源：NOIP2004(提高組)第一題

N位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。

合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1，2…，K，他們的身高分別為T(mén)1，T2，…，TK，則他們的身高滿足T1Ti+1>…>TK(1opt2[i])then

opt2[i]:=opt2[j]+1;

ans:=0;

fori:=1tondo

ifopt1[i]+opt2[i]>ansthen

ans:=opt1[i]+opt2[i];

end;

procedureprint;

begin

writeln(n-ans+1);

close(input);

close(output);

end;

begin

init;

main;

print;

end.

例題3BuyLowBuyLower(buylow.pas/c/cpp)來(lái)源:USACO4-3-1

【問(wèn)題描述】

“逢低吸納”是炒股的一條成功秘訣。如果你想成為一個(gè)成功的投資者，就要遵守這條秘訣:

"逢低吸納,越低越買(mǎi)"

這句話的意思是：每次你購(gòu)買(mǎi)股票時(shí)的股價(jià)一定要比你上次購(gòu)買(mǎi)時(shí)的股價(jià)低.按照這個(gè)規(guī)則購(gòu)買(mǎi)股票的次數(shù)越多越好，看看你最多能按這個(gè)規(guī)則買(mǎi)幾次。

給定連續(xù)的N天中每天的股價(jià)。你可以在任何一天購(gòu)買(mǎi)一次股票，但是購(gòu)買(mǎi)時(shí)的股價(jià)一定要比你上次購(gòu)買(mǎi)時(shí)的股價(jià)低。寫(xiě)一個(gè)程序，求出最多能買(mǎi)幾次股票。

以下面這個(gè)表為例,某幾天的股價(jià)是:

天數(shù)123456789101112

股價(jià)686954646864706778629887

這個(gè)例子中,聰明的投資者(按上面的定義)，如果每次買(mǎi)股票時(shí)的股價(jià)都比上一次買(mǎi)時(shí)低，那么他最多能買(mǎi)4次股票。一種買(mǎi)法如下(可能有其他的買(mǎi)法):

天數(shù)25610

股價(jià)69686462

【輸入文件】buylow.in

第1行:N(1=a[j],0=opt[i])then

opt[i]:=opt[j]+1;

fori:=1tondo

begin

j:=i-1;

while(j>0)and

((opt[i]1)and

(F[n+1][top]=0)do

dec(top);

write(F[n+1,top]);

fori:=top-1downto1do

begin

m:=F[n+1,i];

whilemD2那么一定會(huì)相交，反之則不會(huì)相交。

當(dāng)C1>C2時(shí)，如果D1Lthenquick(L,j);

ifiopt[i])then

opt[i]:=opt[j]+1;

ans:=-maxlongint;

fori:=1tondo

ifans0)do

begin

init;

main;

read(x,y);

end;

close(input);

close(output);

end.

1.2背包問(wèn)題

首先說(shuō)說(shuō)背包問(wèn)題的基本模型：

現(xiàn)有N個(gè)物品，每個(gè)物品的價(jià)值為V，重量為W。求用一個(gè)載重量為S的背包裝這寫(xiě)物品，使得所裝物品的總價(jià)值最高。

背包問(wèn)題用貪心和搜索解，當(dāng)然效果不佳，不過(guò)在我的貪心和搜索總結(jié)中會(huì)說(shuō)到。顯然標(biāo)準(zhǔn)的解法是動(dòng)態(tài)規(guī)化，我在解決這個(gè)問(wèn)題時(shí)習(xí)慣設(shè)計(jì)一維狀態(tài)，還可以設(shè)計(jì)二維的，二維狀態(tài)在下面會(huì)講，現(xiàn)在只討論用一維狀態(tài)實(shí)現(xiàn)背包問(wèn)題。

背包問(wèn)題的分類：

(1)小數(shù)背包:物品的重量是實(shí)數(shù)，如油，水等可以取1.67升……

(2)整數(shù)背包：0/1背包：每個(gè)物品只能選一次，或不選。不能只選一部分

部分背包：所選物品可以是一部分。

(3)多重背包：背包不只一個(gè)。

小數(shù)背包：在貪心總結(jié)中會(huì)細(xì)講。

整數(shù)背包：

部分背包：同小數(shù)背包。

0/1背包：這個(gè)問(wèn)題是最經(jīng)常出現(xiàn)的問(wèn)題，應(yīng)該熟練掌握。

我們先看一下0/1背包的簡(jiǎn)化版：

現(xiàn)有N個(gè)物品，每個(gè)物品重量為W，這些物品能否使在載重量為S的背包裝滿（即重量和正好為S）？如過(guò)不能那能使物品重量和最重達(dá)到多少？

針對(duì)這一問(wèn)題我們以物品的個(gè)數(shù)分階段，設(shè)計(jì)一個(gè)狀態(tài)opt[i]表示載重量為i的背包可否裝滿，顯然opt[i]的基類型是boolean。

決策是什么呢？

當(dāng)要裝第i個(gè)物品時(shí)，如果前i-1個(gè)物品可以使載重為k的背包裝滿，那么載重為k+w[i]的背包就可以裝滿。于是對(duì)于一個(gè)opt[j]來(lái)說(shuō)，只要opt[j-w[i]]是true（表示可裝滿）那opt[j]就可以裝滿，但要注意：針對(duì)每一個(gè)物品枚舉背包的載重量時(shí)如果這樣正向的推導(dǎo)會(huì)使同一個(gè)物品用好幾次，因?yàn)閗+w[i]可裝滿那k+w[i]+w[i]就可裝滿，但實(shí)際上是裝不滿的因?yàn)槲锲分挥幸粋€(gè)。解決這個(gè)問(wèn)題很簡(jiǎn)單，只要逆向推導(dǎo)就

OK了。

這樣劃分階段，設(shè)計(jì)狀態(tài)，滿足無(wú)后效性和么？

顯然對(duì)與一個(gè)每一個(gè)階段都是獨(dú)立的，物品的順序并不影響求解，因?yàn)檠b物品的次序不限。而對(duì)于opt[j]只考慮opt[j-w[i]]而不考慮后面的，所以滿足無(wú)后效性。

有了上面的分析不難寫(xiě)出狀態(tài)轉(zhuǎn)移方程：

opt[j]:=opt[j-w[1]]{opt[j-w[i]]=true}

時(shí)間復(fù)雜度：

階段數(shù)O(S)*狀態(tài)數(shù)（O(N)）*轉(zhuǎn)移代價(jià)（O(1)）=O（SN）

下面看幾個(gè)例題：

例題5裝箱問(wèn)題(pack.pas/c/cpp)來(lái)源：NOIP2001(普及組)第四題

【問(wèn)題描述】

有一個(gè)箱子容量為V（正整數(shù)，0＜＝V＜＝20000），同時(shí)有n個(gè)物品（0＜n＜＝30＝，每個(gè)物品有一個(gè)體積（正整數(shù)）。

要求n個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。

【輸入文件】

第一行一個(gè)正整數(shù)V表示箱子的容量，第二行一個(gè)正整數(shù)N表示物品個(gè)數(shù)，接下來(lái)N行列出這N個(gè)物品各自的體積。

【輸出文件】

單獨(dú)一行，表示箱子最小的剩余空間。

【輸入樣例】

24

6

8

3

12

7

9

7

【輸出樣例】

【問(wèn)題分析】

本題是經(jīng)典的0/1背包問(wèn)題，并且是0/1背包的簡(jiǎn)化版，把箱子看做背包，容量看做載重量，體積看做重量，剩余空間最小也就是盡量裝滿背包。于是這個(gè)問(wèn)題便成了：

有一個(gè)栽重量為V的背包，有N個(gè)物品，盡量多裝物品，使背包盡量的重。

設(shè)計(jì)一個(gè)狀態(tài)opt[i]表示重量i可否構(gòu)成。

狀態(tài)轉(zhuǎn)移方程：opt[j]:=opt[j-w[1]]{opt[j-w[i]]=true}

最終的解就是v-x（x0do

begin

inc(top);

a[top]:=m;

inc(tothig,m);

read(m);

end;

fori:=1totopdo

forj:=tothigdownto1do

if(j-a[i]>=0)and

(opt[ii,j-a[i]])then

opt[ii,j]:=true;

end;

ans:=maxhig;

whilenotopt[1,ans]do

dec(ans);

whilenotcan(ans)do

dec(ans);

writeln(ans);

end;

begin

init;

main;

end.

回顧上面的內(nèi)容充分說(shuō)明動(dòng)態(tài)規(guī)劃的本質(zhì)就是遞推。其實(shí)按照我的理解（動(dòng)規(guī)涉及最優(yōu)決策，遞推是單純的總結(jié)）背包問(wèn)題的簡(jiǎn)化版更準(zhǔn)確點(diǎn)算是遞推而非動(dòng)態(tài)規(guī)劃，至于動(dòng)歸和遞推之間的界線本來(lái)就很模糊（至少我這么認(rèn)為）把它看做什么都可以，沒(méi)必要咬文嚼字。

回到0/1背包的原問(wèn)題上（如果你忘了就去上面看看）。

如果在不知道這個(gè)模型的情況下我們?cè)趺醋鲞@個(gè)題呢？

這就要用到第一節(jié)提到的方法二：三要素法。

題目中明確說(shuō)明對(duì)于一個(gè)物品要不就拿走要不就放下，其實(shí)題目赤裸裸的告訴我們決策就是不拿（用0表示）或拿（用1表示）。這樣想都不用想就知道了決策，這也是本題的突破口。知道了決策寫(xiě)個(gè)搜索的程序應(yīng)該是很輕松的了。

那么階段是什么呢？

顯然，給你一堆東西讓你往包里塞，你當(dāng)然是一個(gè)一個(gè)的那來(lái)，塞進(jìn)去。那么階段很明顯就是物品的個(gè)數(shù)。

狀態(tài)又是什么呢？

有的人在裝東西是有個(gè)習(xí)慣（比如說(shuō)我）就是先把東西分類，然后把同類的東西打個(gè)小包，最后在把小包放進(jìn)去，我們可以按這個(gè)思想給物品打一些小包，也就是按照單位為1的遞增的順序準(zhǔn)備好多小包，比如載重是6的包，可以為它準(zhǔn)備載重是1，2，3，4，5的小包。這樣狀態(tài)就可以想出來(lái)了：設(shè)計(jì)狀態(tài)opt[i，j]表示裝第i個(gè)物品時(shí)載重為j的包可以裝到的最大價(jià)值。

opt[i-1,j](j-w[i]0)

狀態(tài)轉(zhuǎn)移方程：opt[i,j]=

max{opt[i-1,j],opt[i-1,j-w[i]]+v[i]}(j-w[i]>=0,i>0)

(w[i]:第i個(gè)物品的重量，v[i]第i個(gè)物品的價(jià)值)

解釋：要載重為j的背包空出w[i]（j-w[i]）的空間且裝上第i個(gè)物品，比不裝獲得的價(jià)值大就裝上它。

邊界條件：opt[0,i]=0;(i∈{1..S})

注：

這種二維的狀態(tài)表示應(yīng)該在下節(jié)講，但是為了方便理解先在這里說(shuō)了。

上面的方法動(dòng)態(tài)規(guī)劃三要素都很明顯，實(shí)現(xiàn)也很簡(jiǎn)單。但是在我初學(xué)背包時(shí)卻用另外一種一維的狀態(tài)表示法。

用第一節(jié)說(shuō)的思考方法五（放寬約束和增加約束）在重新思考一下這個(gè)問(wèn)題：

怎么放寬約束呢？

把題目中的價(jià)值去掉，不考慮價(jià)值即最優(yōu)就變成背包問(wèn)題的簡(jiǎn)化版了。那簡(jiǎn)化版的求解對(duì)我們有何啟示呢？

再一次增加約束：背包只能裝滿。

顯然對(duì)于N個(gè)裝滿背包的方案中只要找到一個(gè)價(jià)值最大的就是問(wèn)題的解。那么裝不滿怎么辦呢？其實(shí)

裝不滿背包，它總要達(dá)到一定的重量（X）。我們可以把這種情況看作是裝滿一個(gè)載重為X的小包。

總結(jié)一下上面的思維過(guò)程：

放寬約束讓我們找到問(wèn)題的突破口——和背包問(wèn)題簡(jiǎn)化版一樣，我們可以卻定載重為S的背包是否可以裝滿。

增加約束讓我們找到問(wèn)題的求解方法——在裝滿背包的方案中選擇最優(yōu)的一個(gè)方案。

這樣問(wèn)題就解決了。

設(shè)計(jì)一個(gè)狀態(tài)opt[j]表示裝滿載重為j的背包可獲得的最大價(jià)值。對(duì)于第i個(gè)物品，只要opt[j-w[i]]可以裝滿且opt[j-w[i]]+v[i]比opt[j]大就裝上這個(gè)物品（更新opt[j]）。

怎么使opt[j]既有是否構(gòu)成又有最優(yōu)的概念呢？

opt[j]只表示最優(yōu)，只不過(guò)使初始條件+1，判斷opt[j]是否為0，如果opt[j]=0說(shuō)明j裝不滿。

邊界條件：opt[0]=1;

狀態(tài)轉(zhuǎn)移方程：opt[j]=max{opt[j-w[i]]}(0ythenmax:=x

elsemax:=y;

end;

proceduremain;

var

i,j:longint;

begin

fillchar(opt,sizeof(opt),0);

fori:=1tondo

forj:=1totdo

ifj-w[i]0)and

(opt[j-w[i]]+v[i]>opt[j])then

opt[j]:=opt[j-w[i]]+v[i];

ans:=-maxlongint;

fori:=1totdo

ifopt[i]>ansthenans:=opt[i];

end;

procedureprint;

begin

writeln(ans-1);

close(output);

end;

begin

init;

main;

print;

end.

例題9開(kāi)心的金明來(lái)源：NOIP2006（普及組）第二題

【問(wèn)題描述】

金明今天很開(kāi)心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說(shuō)：“你的房間需要購(gòu)買(mǎi)哪些物品，怎么布置，你說(shuō)了算，只要不超過(guò)N元錢(qián)就行”。今天一早金明就開(kāi)始做預(yù)算，但是他想買(mǎi)的東西太多了，肯定會(huì)超過(guò)媽媽限定的N元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù)1~5表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是整數(shù)元）。他希望在不超過(guò)N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。設(shè)第j件物品的價(jià)格為v[j]，重要度為w[j]，共選中了k件物品，編號(hào)依次為j1...jk，則所求的總和為：v[j1]*w[j1]+..+v[jk]*w[jk]請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購(gòu)物單.

【輸入文件】

輸入的第1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：Nm

（其中N（=0)and

(opt[j-v[i]]>0)and

(opt[j-v[i]]+v[i]*p[i]>opt[j])then

opt[j]:=opt[j-v[i]]+v[i]*p[i];

end;

end;

end;procedureprint;var

i,ans:longint;beginans:=0;

fori:=1tondo

ifopt[i]>ansthen

ans:=opt[i];

writeln(ans-1);

end;

begin

init;

main;

print;

end.

例題10金明的預(yù)算方案(budget.pas/c/cpp)來(lái)源：NOIP2006第二題

【問(wèn)題描述】

金明今天很開(kāi)心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說(shuō)：“你的房間需要購(gòu)買(mǎi)哪些物品，怎么布置，你說(shuō)了算，只要不超過(guò)N元錢(qián)就行”。今天一早，金明就開(kāi)始做預(yù)算了，他把想買(mǎi)的物品分為兩類：主件與附件，附件是從屬于某個(gè)主件的，下表就是一些主件與附件的例子：

主件附件

電腦打印機(jī)，掃描儀

書(shū)柜圖書(shū)

書(shū)桌臺(tái)燈，文具

工作椅無(wú)

如果要買(mǎi)歸類為附件的物品，必須先買(mǎi)該附件所屬的主件。每個(gè)主件可以有0個(gè)、1個(gè)或2個(gè)附件。附件不再有從屬于自己的附件。金明想買(mǎi)的東西很多，肯定會(huì)超過(guò)媽媽限定的N元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù)1~5表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是10元的整數(shù)倍）。他希望在不超過(guò)N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。

設(shè)第j件物品的價(jià)格為v[j]，重要度為w[j]，共選中了k件物品，編號(hào)依次為j1，j2，……，jk，則所求的總和為：

v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]。（其中*為乘號(hào)）

請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購(gòu)物單。

【輸入文件】

輸入文件budget.in的第1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：

Nm（其中N（0說(shuō)明花i元可以買(mǎi)到物品。這樣就不難設(shè)計(jì)出這個(gè)狀態(tài)的轉(zhuǎn)移方程來(lái)：

opt[i]=max{opt[i],opt[i-wj]}((i-wj>0)and(opt[i-wj]>0))(0ythenexit(x);

exit(y);

end;

proceduremain;

var

i,j:longint;

begin

fillchar(opt,sizeof(opt),0);

opt[0]:=1;

forj:=1tomdo

fori:=ndowntov[j]do

ifq[j]=0then

begin

if(i-v[j]>=0)and

(opt[i-v[j]]>0)then

opt[i]:=max(opt[i],opt[i-v[j]]

+v[j]*p[j]);

if(i-v[j]-v[q1[j]]>=0)and

(opt[i-v[j]-v[q1[j]]]>0)then

opt[i]:=max(opt[i],opt[i-v[j]-

v[q1[j]]]+v[j]*p[j]+v[q1[j]]*p[q1[

j]]);

if(i-v[j]-v[q2[j]]>=0)and

(opt[i-v[j]-v[q2[j]]]>0)then

opt[i]:=max(opt[i],opt[i-v[j]-

v[q2[j]]]+v[j]*p[j]+v[q2[j]]*p[q2[

j]]);

if(i-v[j]-v[q1[j]]-v[q2[j]]>=0)

and

(opt[i-v[j]-v[q1[j]]-v[q2[j]]]>0)

then

opt[i]:=max(opt[i],opt[i-v[j]-

v[q1[j]]-v[q2[j]]]+v[j]*p[j]+v[q1[j

]]*p[q1[j]]+v[q2[j]]*p[q2[j]]);

ans:=max(ans,opt[i]);

end;

end;

procedureprint;

begin

writeln((ans-1)*10);

close(output);

end;

begin

init;

main;

print;

end.

上面提到的幾個(gè)例題都是最基礎(chǔ)的題目，而且把問(wèn)題抽象后就與背包問(wèn)題的基本模型一樣了，但有些題目用到了基本模型，要求的解卻不一定很模型一樣，下面看個(gè)例子：

例題11MoneySystems(money.pas/c/cpp)來(lái)源：USACO2.3

【問(wèn)題描述】

母牛們不但創(chuàng)建了他們自己的政府而且選擇了建立了自己的貨幣系統(tǒng)。[Intheirownrebelliousway],，他們對(duì)貨幣的數(shù)值感到好奇。

傳統(tǒng)地，一個(gè)貨幣系統(tǒng)是由1,5,10,20或25,50,和100的單位面值組成的。

母牛想知道有多少種不同的方法來(lái)用貨幣系統(tǒng)中的貨幣來(lái)構(gòu)造一個(gè)確定的數(shù)值。

舉例來(lái)說(shuō),使用一個(gè)貨幣系統(tǒng){1,2,5,10,...}產(chǎn)生18單位面值的一些可能的方法是:18x1,9x2,8x2+2x1,3x5+2+1,等等其它。寫(xiě)一個(gè)程序來(lái)計(jì)算有多少種方法用給定的貨幣系統(tǒng)來(lái)構(gòu)造一定數(shù)量的面值。保證總數(shù)將會(huì)適合longlong(C/C++)和Int64(FreePascal)。

【輸入文件】

貨幣系統(tǒng)中貨幣的種類數(shù)目是V(11then

begin

writeln('-1');

halt;

end;

i:=total;

whilei>0do

begin

ans[path[i]]:=false;

i:=i-w[path[i]];

end;

end;

procedureprint;

var

i:longint;

begin

fori:=1tondo

ifans[i]thenwrite(i,'');

end;

begin

init;

main;

print;

end.

1.3其它問(wèn)題

一維動(dòng)態(tài)規(guī)劃最常見(jiàn)的就是前面總結(jié)的最長(zhǎng)下降/非降子序列和0/1背包問(wèn)題了，當(dāng)然還有別的一寫(xiě)題。由于不是很常見(jiàn)所以沒(méi)有固定的解題模式，到時(shí)候具體問(wèn)題具體分析。下面在看一些例子：例題13挖地雷問(wèn)題(P3.pas/c/cpp)來(lái)源：NOIP1996（提高組）第三題（有改動(dòng)）

【問(wèn)題描述】

在一個(gè)地圖上有N個(gè)地窖（N3->4->5

max=27

【Hint】

題目中的路徑是有向的且無(wú)環(huán)路（這是我做的改動(dòng)原題中沒(méi)有要求）。

【問(wèn)題分析】

看到題目的第一影響是貪心——以一點(diǎn)出發(fā)找與他連接的地窖中地雷數(shù)最多的一個(gè)。

但很容易想到反例：

5

1211100

1100

010

01

按照貪心答案是3，但實(shí)際上答案是101。

于是就不得不放棄貪心的想法。

但是貪心給了我們啟示：從一個(gè)頂點(diǎn)出發(fā)要選擇向一個(gè)與他相連且以該點(diǎn)出發(fā)可以挖到較多雷的點(diǎn)走。（有點(diǎn)拗口）

另一種解釋：如果一個(gè)頂點(diǎn)連同N個(gè)分量，顯然要?jiǎng)t一個(gè)較大的就是問(wèn)題的解答，這個(gè)定義是滿足最優(yōu)化原理的。

那它滿足無(wú)后效性么？

因?yàn)閳D是有向的，所以以與該頂點(diǎn)相連的點(diǎn)在往下走的路線中不包括該點(diǎn)。也就是說(shuō)圖是一個(gè)AOV網(wǎng)（有向無(wú)環(huán)圖）。

既然滿足最優(yōu)化原理，且無(wú)后效性，我們就可以用動(dòng)態(tài)規(guī)劃解了。

這個(gè)問(wèn)題的階段就是拓?fù)湫蛄?，但由于輸入是倒三角形，所以我們沒(méi)必要求拓?fù)湫蛄?，只要從N到著求解就可以了。

設(shè)計(jì)狀態(tài)opt[i]表示以i點(diǎn)出發(fā)可以挖到最多的雷的個(gè)數(shù)。

狀態(tài)轉(zhuǎn)移方程：opt[i]=max{opt[j]}+w[i](g[i,j]=1)

(g存圖，w[i]存第i個(gè)地窖中的雷的個(gè)數(shù))。

時(shí)間復(fù)雜度：

狀態(tài)數(shù)O(n)*轉(zhuǎn)移代價(jià)O(n)=O(n2)

這個(gè)題目還要求出路徑，可以用一個(gè)輔助數(shù)組path來(lái)記錄，path[i]表示從第i個(gè)出發(fā)走到的下一個(gè)點(diǎn)的編號(hào)。求解完只要按path記錄的路徑輸出即可。

【源代碼】

programP3;

const

fin='P3.in';

fout='P3.out';

maxn=200;

var

g:array[0..maxn,0..maxn]oflongint;

n,ans:longint;

w,opt,path:array[0..maxn]of

longint;

procedureinit;

var

i,j:longint;

begin

assign(input,fin);

reset(input);

assign(output,fout);

rewrite(output);

read(n);

fillchar(g,sizeof(g),0);

fori:=1tondo

read(w[i]);

fori:=1tondo

forj:=i+1tondo

read(g[i,j]);

close(input);

end;

proceduremain;

var

i,j:longint;

begin

fillchar(opt,sizeof(opt),0);

fillchar(path,sizeof(path),0);

fori:=ndownto1do

begin

forj:=i+1tondo

if(g[i,j]=1)and(opt[j]>opt[i])then

begin

opt[i]:=opt[j];

path[i]:=j;

end;

inc(opt[i],w[i]);

end;

ans:=1;

fori:=2tondo

ifopt[i]>opt[ans]

thenans:=i;

end;

procedureprint;

var

i:longint;

begin

write(ans);

i:=path[ans];

whilei>0do

begin

write('-->',i);

i:=path[i];

end;

writeln;

writeln('max=',opt[ans]);

close(output);

end;

begin

init;

main;

print;

end.

2.狀態(tài)是二維的

通過(guò)前面的學(xué)習(xí)，我想因該對(duì)動(dòng)態(tài)規(guī)劃不陌生了，我學(xué)習(xí)動(dòng)態(tài)規(guī)劃是沒(méi)這么系統(tǒng)，二維，一維一起上。二維狀態(tài)的動(dòng)態(tài)規(guī)劃是重中之重。

所謂二維狀態(tài)就是說(shuō)一般設(shè)計(jì)的狀態(tài)是opt[i,j]形式的。那i,j可以代表什么呢？

有很多朋友問(wèn)過(guò)我這個(gè)問(wèn)題，我的回答是：

(1)i,j組合起來(lái)代表一個(gè)點(diǎn)的坐標(biāo)（顯然是平面坐標(biāo)系）（如：街道問(wèn)題）。

(2)i,j組合表示一個(gè)矩陣的單元的位置（第i行，第j列）（如：數(shù)塔問(wèn)題）

(3)起點(diǎn)為i長(zhǎng)度為j的區(qū)間。（如：回文詞）

(4)起點(diǎn)為i終點(diǎn)為j的區(qū)間。（如：石子合并問(wèn)題）

(5)兩個(gè)沒(méi)關(guān)聯(lián)的事物，事物1的第i個(gè)位置，對(duì)應(yīng)事物2的第j個(gè)位置（花店櫥窗設(shè)計(jì)）

(6)兩個(gè)序列，第一個(gè)序列的前i個(gè)位置或第i個(gè)位置對(duì)應(yīng)第2個(gè)序列的第j個(gè)位置或前j個(gè)位置。（最長(zhǎng)公共子序列）。

(7)其它

下面通過(guò)例題和基本模型進(jìn)一步說(shuō)明：

2.1數(shù)塔問(wèn)題

數(shù)塔問(wèn)題來(lái)源于一道經(jīng)典的IOI的題目，直接說(shuō)題通過(guò)題目總結(jié)公性。以后遇到類似的題目可以參照這個(gè)模型。

例題14數(shù)塔問(wèn)題(numtri.pas/c/cpp)來(lái)源：IOI94

【問(wèn)題描述】

考慮在下面被顯示的數(shù)字金字塔。

寫(xiě)一個(gè)程序來(lái)計(jì)算從最高點(diǎn)開(kāi)始在底部任意處結(jié)束的路徑經(jīng)過(guò)數(shù)字的和的最大。每一步可以走到左下方的點(diǎn)也可以到達(dá)右下方的點(diǎn)。

7

38

810

2744

45265

在上面的樣例中,從7到3到8到7到5的路徑產(chǎn)生了最大和:30

【輸入文件】

第一個(gè)行包含R(1max)then

max:=opt[i-1,k];

opt[i,j]:=max+a[i,j];

end;

ans:=-maxlongint;

i:=(1+m)div2;

forj:=i-2toi+2do

if(j>0)and(jans)thenans:=opt[n,j];end;procedureprint;beginwriteln(ans);close(input);close(output);end;begininit;main;print;end.

2.2街道問(wèn)題和數(shù)塔問(wèn)題一樣街道問(wèn)題也來(lái)源于一道典型的例題，下面我們看一下這道題。

例題16街道問(wèn)題(way.pas/c/cpp)來(lái)源：《奧賽經(jīng)典》（提高篇）

【問(wèn)題描述】

如圖所示的矩形圖中找到一條從左下角到右上角的最短路徑，圖中數(shù)字表示邊的長(zhǎng)度。只能向右或向上走。

【輸入文件】第一行兩個(gè)數(shù)，N，M矩形的點(diǎn)有N行M列。（0是X的子序列是指存在一個(gè)嚴(yán)格遞增的下標(biāo)序列，使得對(duì)于所有j=1,2,…,k有Xij=Zj

例如，序列Z=是序列X=的子序列，相應(yīng)的遞增下標(biāo)序列為。給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。例如，若X=和Y=，則序列是X和Y的一個(gè)公共子序列，序列也是X和Y的一個(gè)公共子序列。而且，后者是X和Y的一個(gè)最長(zhǎng)公共子序列，因?yàn)閄和Y沒(méi)有長(zhǎng)度大于4的公共子序列。

給定兩個(gè)序列X=和Y=，要求找出X和Y的一個(gè)最長(zhǎng)公共子序列。

【輸入文件】

輸入文件共有兩行，每行為一個(gè)由大寫(xiě)字母構(gòu)成的長(zhǎng)度不超過(guò)200的字符串，表示序列X和Y。

【輸出文件】

輸出文件第一行為一個(gè)非負(fù)整數(shù)，表示所求得的最長(zhǎng)公共子序列的長(zhǎng)度，若不存在公共子序列，則輸出文件僅有一行輸出一個(gè)整數(shù)0，否則在輸出文件的第二行輸出所求得的最長(zhǎng)公共子序列(也用一個(gè)大寫(xiě)字母組成的字符串表示。

【輸入樣例】

ABCBDAB

BDCBA

【輸出樣例】

4

BCBA

【問(wèn)題分析】

這個(gè)問(wèn)題也是相當(dāng)經(jīng)典的。。

這個(gè)題目的階段很不明顯，所以初看這個(gè)題目沒(méi)什么頭緒，不像前面講的有很明顯的上一步，上一層

之類的東西，只是兩個(gè)字符串而且互相沒(méi)什么關(guān)聯(lián)。

但仔細(xì)分析發(fā)現(xiàn)還是有入手點(diǎn)的：

既然說(shuō)是動(dòng)態(tài)規(guī)劃，那我們首先要考慮的就是怎么劃分子問(wèn)題，一般對(duì)于前面講到的街道問(wèn)題和數(shù)塔問(wèn)題涉及走向的，考慮子問(wèn)題時(shí)當(dāng)然是想上一步是什么？但這個(gè)問(wèn)題沒(méi)有涉及走向，也沒(méi)有所謂的上一步，該怎么辦呢？

既然是求公共子序列，也就有第一個(gè)序列的第i個(gè)字符和第二個(gè)序列的第j個(gè)字符相等的情況。

那么我們枚第一個(gè)序列（X）的字符，和第二個(gè)序列（Y）的字符。

顯然如果X[i]=Y[j]那么起點(diǎn)是1（下面說(shuō)的子序列都是起點(diǎn)為1的），長(zhǎng)度為i的子序列和長(zhǎng)度為j的子序列的最長(zhǎng)公共子序列就是長(zhǎng)度為i-1和長(zhǎng)度為j-1的子序列中最長(zhǎng)的公共子序列加上X[i]或Y[j]。

那要是不相等呢？

如果不相等，也就是說(shuō)第一個(gè)序列長(zhǎng)度為I的子序列和第二個(gè)序列中長(zhǎng)度為j的子序列的公共子序列中X[i]和Y[j]不同時(shí)出現(xiàn)。也就是說(shuō)第一個(gè)序列長(zhǎng)度為i的子序列和第二個(gè)序列中長(zhǎng)度為j的子序列的公共子序列是第一個(gè)序列長(zhǎng)度為i的子序列和第二個(gè)序列中長(zhǎng)度為j-1的子序列或第一個(gè)序列長(zhǎng)度為i-1的子序列和第二個(gè)序列中長(zhǎng)度為j的子序列的公共子序列中一個(gè)更長(zhǎng)的。

設(shè)計(jì)一個(gè)狀態(tài)opt[i,j]表示起點(diǎn)為1，第一序列長(zhǎng)度為i，第二序列長(zhǎng)度為j的子序列的最長(zhǎng)公共子序列。按照上面的分類就可以得到狀態(tài)轉(zhuǎn)移方程：

opt[i-1,j-1]+x[i](x[i]=y[j])

opt[i,j]=opt[i-1,j]+x[i](length(opt[i-1,j])>=length(opt[i,j-1]))

opt[i,j-1]+y[j](length(opt[i-1,j])=length(opt[i,j-

1])then

opt[i,j]:=opt[i-1,j]

elseopt[i,j]:=opt[i,j-1];

end;

procedureprint;

begin

writeln(length(opt[L1,L2]));

write(opt[L1,L2]);

close(output);

end;

begin

init;

main;

print;

end.

例題18回文詞(palin.pas/c/cpp)來(lái)源：IOI2000

【問(wèn)題描述】

回文詞是一種對(duì)稱的字符串——也就是說(shuō)，一個(gè)回文詞，從左到右讀和從右到左讀得到的結(jié)果是一樣的。任意給定一個(gè)字符串，通過(guò)插入若干字符，都可以變成一個(gè)回文詞。你的任務(wù)是寫(xiě)一個(gè)程序，求出將給定字符串變成回文詞所需插入的最少字符數(shù)。

比如字符串“Ab3bd”，在插入兩個(gè)字符后可以變成一個(gè)回文詞（“dAb3bAd”或“Adb3bdA”）。然而，插入兩個(gè)以下的字符無(wú)法使它變成一個(gè)回文詞。

【輸入文件】

第一行包含一個(gè)整數(shù)N，表示給定字符串的長(zhǎng)度，3ythenexit(x);

max:=y;

end;

proceduremain;

var

i,x,j,k0,k1:longint;

begin

fillchar(opt,sizeof(opt),0);

readln(n);

readln(a);

b:='';

fori:=ndownto1do

b:=b+a[i];

k0:=0;

k1:=1;

fori:=1tondo

begin

fillchar(opt[k1],sizeof(opt[k1

]),0);

forj:=1tondo

begin

opt[k1,j]:=max(opt[k0,j],opt[

k1,j-1]);

ifa[i]=b[j]then

opt[k1,j]:=max(opt[k1,j],opt[

k0,j-1]+1);

end;

x:=k0;

k0:=k1;

k1:=x;

end;

writeln(n-opt[k0,n]);

end;

begin

main;

end.

用這個(gè)方法AC了就該很高興了，但不要停止思考的步伐，還有別的方法么？

從原問(wèn)題出發(fā)，找這個(gè)問(wèn)題的子問(wèn)題。和上面說(shuō)的最長(zhǎng)公共子序列問(wèn)題一樣，設(shè)計(jì)序列的問(wèn)題我們一般要考慮它的子序列，也就是更短的序列。

這樣就回到了我第一節(jié)說(shuō)的邊界條件法了。

顯然單獨(dú)的字符就是邊界了，而且單獨(dú)的字符就是回文詞，添加0個(gè)字符就可以了。

如果是兩個(gè)字符組成的序列怎么辦呢？

只要看他們是否相同就可以了，如果相同那就是回文詞了，添加0個(gè)字符，如果不相同就在它的左邊或右邊添一個(gè)字符，讓另外一個(gè)當(dāng)對(duì)稱軸。

如果是3個(gè)字符呢？

我們用S存這個(gè)序列，如果S[1]=S[3]那么它就是回文詞了,

如果S[1]S[3]那么就在前面添S[3]或后面添S[1]

剩下的就要考慮S[1]S[2]和S[2]S[3]這兩個(gè)序列了。

通過(guò)前面的分析我們很容易想到這樣的算法：

對(duì)于一個(gè)序列S只要看它的左右端的字符是否相同，如果相同那么就看除掉兩端字符的新串要添的字符個(gè)數(shù)了；如果不同，就在它左面添上右斷的字符然后考慮去掉新序列兩端的字符后的串要添的字符?；蛘咴谟颐嫣砩献蠖说淖址诳紤]去掉添了字符后新串左右兩端字符得到的新串要添的字符。

設(shè)計(jì)一個(gè)二維狀態(tài)opt[L,i]表示長(zhǎng)度是L+1，起點(diǎn)是i的序列變成回文詞要添的字符的個(gè)數(shù)。階段就是字符的長(zhǎng)度，決策要分類，即S[i]和S[i+L]是否相等。

狀態(tài)轉(zhuǎn)移方程:

min(opt[L-1,i]+1,opt[L-1,i+1]+1)(s[i]s[i+L])

opt[L,i]=

min(opt[L-1,i]+1,opt[L-1,i+1]+1,opt[L-2,i+1])(s[i]=s[i+L])

復(fù)雜度：

空間復(fù)雜度=狀態(tài)數(shù)O（N2）

時(shí)間復(fù)雜度=狀態(tài)數(shù)O（N2）*轉(zhuǎn)移代價(jià)O（1）=O（N2）

由于空間復(fù)雜度較高，仍然要用滾動(dòng)數(shù)組。

【源代碼2】

programP1327;

const

maxn=5002;

var

a:array[0..maxn]ofchar;

opt:array[0..2,0..maxn]oflongint;

n,ans:longint;

function

min(x,y:longint):longint;

begin

min:=y;

ifxa[j],10then

begin

if

opt[j-rmb[i],k-rp[i]]+1>opt[j,k]

then

begin

opt[j,k]:=opt[j-rmb[i],k-rp[i]]

+1;

ct[j,k]:=ct[j-rmb[i],k-rp[i]]+ti

me[i];

end

elseif

(opt[j-rmb[i],k-rp[i]]+1=opt[j,k])

and

(ct[j-rmb[i],k-rp[i]]+time[i]maxthenbegin

max:=opt[j,k];ans:=ct[j,k];

end

elseif(opt[j,k]=max)and

(ct[j,k]ans:=ct[j,k];

end;

procedureprint;

begin

writeln(ans);

close(output);

end;

begin

init;

main;

print;

end.

例題21多多看DVD（加強(qiáng)版）(watchdvd.pas/c/cpp)來(lái)源：本人原創(chuàng)

【問(wèn)題描述】

多多進(jìn)幼兒園了，今天報(bào)名了。只有今晚可以好好放松一下了（以后上了學(xué)后會(huì)很忙）。她的叔叔決定給他買(mǎi)一些動(dòng)畫(huà)片DVD晚上看?？墒菭敔斠?guī)定他們只能在一定的時(shí)間段L看完。

（因?yàn)槭迨暹€要搞NOIP不能太早陪多多看碟，而多多每天很早就困了所以只能在一定的時(shí)間段里看碟）。多多列出一張表要叔叔給她買(mǎi)N張DVD碟，大多都是多多愛(ài)看的動(dòng)畫(huà)片（福音戰(zhàn)士，機(jī)器貓，火影忍者，櫻桃小丸子……）。這N張碟編號(hào)為（1，2，3……N）。多多給每張碟都打了分Mi（Mi>0），打分越高的碟說(shuō)明多多越愛(ài)看。每張碟有播放的時(shí)間Ti。多多想在今晚爺爺規(guī)定的時(shí)間里看的碟總分最高。（必須把要看的碟看完，也就是說(shuō)一張碟不能只看一半）。顯然叔叔在買(mǎi)碟是沒(méi)必要把N張全買(mǎi)了，只要買(mǎi)要看的就OK了，這樣節(jié)省資金啊。而且多多讓叔叔慣的特別任性只要他看到有幾張就一定會(huì)看完。

可是出現(xiàn)了一個(gè)奇怪的問(wèn)題，買(mǎi)碟的地方只買(mǎi)給顧客M（Mythenmax:=x;

end;

proceduremain;

var

i,j,k:longint;

begin

fillchar(opt,sizeof(opt),0);

fori:=1tondo

forj:=mdownto1do

ifj0)or((j=1)

and(k=w[i]))then

opt[j,k]:=max(opt[j-1,k-w[i]]

+val[i],opt[j,k]);

ans:=-maxlongint;

fori:=0tovdo

ifopt[m,i]>ansthen

ans:=opt[m,i];

end;

procedureprint;

begin

write(ans);

close(output);

end;

begin

init;

main;

print;

end.

2.5石子合并問(wèn)題

也有人把這類問(wèn)題叫做是區(qū)間上的動(dòng)態(tài)規(guī)劃。

例題22石子合并(stone.pas/c/cpp)來(lái)源：某年NOI（去巴蜀交）

【問(wèn)題描述】

在一個(gè)操場(chǎng)上擺放著一行共n堆的石子?，F(xiàn)要將石子有序地合并成一堆。規(guī)定每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。請(qǐng)編輯計(jì)算出將n堆石子合并成一堆的最小得分和將n堆石子合并成一堆的最大得分。

【輸入文件】

輸入第一行為n(nythenmax:=x;

end;

function

min(x,y:longint):longint;

begin

min:=y;

if(x0)then

min:=x;

end;

proceduremain;

var

i,j,L,k:longint;

begin

fillchar(minopt,sizeof(minopt

),200);

fillchar(maxopt,sizeof(maxop

t),0);

fori:=1to2*ndo

minopt[i,i]:=0;

forL:=1ton-1do

fori:=1to2*n-Ldo

begin

j:=i+L;

fork:=itoj-1do

begin

maxopt[i,j]:=max(maxopt[i,j]

,maxopt[i,k]+maxopt[k+1,j]);

minopt[i,j]:=min(minopt[i,j],

minopt[i,k]+minopt[k+1,j]);

end;

inc(maxopt[i,j],sum[j]-sum[i-

1]);

inc(minopt[i,j],sum[j]-sum[i-

1]);

end;

maxans:=-maxlongint;

minans:=maxlongint;

fori:=1tondo

maxans:=max(maxans,maxo

pt[i,i+n-1]);

fori:=1tondo

minans:=min(minans,minopt[

i,i+n-1]);

{fori:=1ton*2do

begin

forj:=1ton*2do

write(maxopt[i,j],'');

writeln;

end;}

end;

begin

init;

main;

writeln(minans,'',maxans);

end.

例題23能量項(xiàng)鏈(energy.pas/c/cpp)來(lái)源NOIP2006（提高組）

【問(wèn)題描述】

在Mars星球上，每個(gè)Mars人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有N顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。并且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因?yàn)橹挥羞@樣，通過(guò)吸盤(pán)（吸盤(pán)是Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時(shí)釋放出可以被吸盤(pán)吸收的能量。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)記為r，后一顆能量珠的頭標(biāo)記為r，尾標(biāo)記為n，則聚合后釋放的能量為（Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為m，尾標(biāo)記為n。

需要時(shí)，Mars人就用吸盤(pán)夾住相鄰的兩顆珠子，通過(guò)聚合得到能量，直到項(xiàng)鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請(qǐng)你設(shè)計(jì)一個(gè)聚合順序，使一串項(xiàng)鏈釋放出的總能量最大。

例如：設(shè)N=4，4顆珠子的頭標(biāo)記與尾標(biāo)記依次為(2，3)(3，5)(5，10)(10，2)⊕

。我們用記號(hào)表示兩顆珠子的聚合操作，(jk)表示第j，k兩顆珠子聚合后所釋放的能量。則第4、1兩顆珠子聚合后釋放的能

量為：

(41)=10*2*3=60。

這一串項(xiàng)鏈可以得到最優(yōu)值的一個(gè)聚合順序所釋放的總能量為

((41)2)3）=10*2*3+10*3*5+10*5*10=710。

【輸入文件】

輸入文件energy.in的第一行是一個(gè)正整數(shù)N（4≤N≤100），表示項(xiàng)鏈上珠子的個(gè)數(shù)。第二行是N個(gè)用空格隔開(kāi)的正整數(shù)，所有的數(shù)均不超過(guò)1000。第i個(gè)數(shù)為第i顆珠子的頭標(biāo)記（1≤i≤N），當(dāng)iythenexit(x);

exit(y);

end;

proceduremain;

var

i,j,k,L:longint;

begin

fillchar(opt,sizeof(opt),0);

forL:=2tondo

fori:=1ton*2-L+1do

begin

j:=i+L;

fork:=i+1toj-1do

opt[i,j]:=max(opt[i,j],opt[i,k]

+opt[k,j]+a[i]*a[j]*a[k]);

end;

fori:=1tondo

ans:=max(ans,opt[i,i+n]);

end;

procedureprint;

begin

writeln(ans);

close(output);

end;

begin

init;

main;

print;

end.

例題24統(tǒng)計(jì)單詞個(gè)數(shù)(.pas/c/cpp)來(lái)源：NOIP2001（提高組）

【問(wèn)題描述】

給出一個(gè)長(zhǎng)度不超過(guò)200的由小寫(xiě)英文字母組成的字母串(約定;該字串以每行20個(gè)字母的方式輸入，且保證每行一定為20個(gè))。要求將此字母串分成k份(1opt[n,ans]thenans:=i;

end;

procedure

outputway(i,j:longint);begin

ifi>0then

begin

outputway(i-1,path[i,j]);

write(j,'');

end;

end;

procedureprint;

var

i:longint;

begin

writeln(opt[n,ans]);

outputway(n,ans);

writeln;

end;

begin

init;

main;

print;

end.

例題26Divisibility來(lái)源：ZJU2042

【問(wèn)題描述】

Consideranarbitrarysequenceofintegers.Onecanplace+or-operatorsbetweenintegersinthesequence,thusderivingdifferentarithmeticalexpressionsthatevaluatetodifferentvalues.Letus,forexample,takethesequence:17,5,-21,15.Thereareeightpossibleexpressions:

17+5+-21+15=16

17+5+-21-15=-14

17+5--21+15=58

17+5--21-15=28

17-5+-21+15=6

17-5+-21-15=-24

17-5--21+15=48

17-5--21-15=18

WecallthesequenceofintegersdivisiblebyKif+or-operatorscanbeplacedbetweenintegersinthesequenceinsuchwaythatresultingvalueisdivisiblebyK.Intheaboveexample,thesequenceisdivisibleby7(17+5+-21-15=-14)butisnotdivisibleby5.

Youaretowriteaprogramthatwilldeterminedivisibilityofsequenceofintegers.

譯題：

給出N個(gè)數(shù)，你可以在這N個(gè)數(shù)中任意地添加+號(hào)或-號(hào)，求出能不能使算出的結(jié)果被K整除?？梢詣t打印“Divisible”，否則打印“Notdivisible”

(1ythenmax:=x;

end;

proceduremain;

var

i1,i2,j1,j2:longint;

begin

fori1:=1tondo

forj1:=1tondo

fori2:=i1tondo

forj2:=1toj1do

if(i1=i2)and(j1=j2)then

opt[i1,j1,i2,j2]:=opt[i1-1,j1,i2

,j2-1]+a[i1,j1]

elseif(i1=i2-1)and(j1=j2)

then

opt[i1,j1,i2,j2]:=max(opt[i1-1

,j1,i2,j2-1],opt[i1,j1-1,i2,j2-1])

+a[i1,j1]+a[i2,j2]

elseif(i1=i2)and(j1=j2+1)

then

opt[i1,j1,i2,j2]:=max(opt[i1-1

,j1,i2,j2-1],opt[i1-1,j1,i2-1,j2])

+a[i1,j1]+a[i2,j2]

elsebegin

opt[i1,j1,i2,j2]:=max(opt[i1-1

,j1,i2,j2-1],opt[i1-1,j1,i2-1,j2]);

opt[i1,j1,i2,j2]:=max(opt[i1,j

1,i2,j2],opt[i1,j1-1,i2,j2-1]);

opt[i1,j1,i2,j2]:=max(opt[i1,j

1,i2,j2],opt[i1,j1-1,i2-1,j2]);

inc(opt[i1,j1,i2,j2],a[i1,j1]+a[

i2,j2]);

end;

end;

procedureprint;

begin

writeln(opt[n,n,n,n]);

close(output);

end;

begin

init;

main;

print;

end.

如果這個(gè)題的數(shù)據(jù)范圍在大點(diǎn)就得優(yōu)化了，怎么優(yōu)化這個(gè)程序呢？

上面說(shuō)過(guò)對(duì)于時(shí)間空間都大的時(shí)候，首先想到的就是尋找特點(diǎn)，改變狀態(tài)的表示法，減少狀態(tài)的維數(shù)。

仔細(xì)分析我們發(fā)現(xiàn)，處于同行，同列的狀態(tài)，等價(jià)于另外一個(gè)點(diǎn)在對(duì)角線上的狀態(tài)。而這條對(duì)角線正是此題的階段。因?yàn)樵跔顟B(tài)轉(zhuǎn)移的時(shí)候后面的哪個(gè)點(diǎn)總是從固定的一個(gè)方向轉(zhuǎn)移來(lái)的。也就是說(shuō)我們只要對(duì)角先上的狀態(tài)就可以省掉那些同行同列的狀態(tài)了。

做過(guò)N皇的同學(xué)一定知道怎么表示右上到左下的這幾條對(duì)角線，不知道的同學(xué)也沒(méi)關(guān)系,對(duì)于一個(gè)點(diǎn)（i,j）他對(duì)角右上角的點(diǎn)就是（i-1，j+1）所以可以看出這些點(diǎn)的和是定值，且值從2到N*2。

這樣用三個(gè)變量就可以表示這兩個(gè)點(diǎn)了，于是設(shè)計(jì)狀態(tài)opt[k,i1,i2]表示處于階段K時(shí)走到i1,i2的兩條路徑所取得的數(shù)的最大和。

用上面的思維不難想出動(dòng)態(tài)轉(zhuǎn)移方程：

max(opt[k-1,i1-1,i2-1],opt[k-1,i1-1,i2],opt[k-1,i1,i2-1],opt[k-1,i1,i2])+a[i1,k-i1]+a[i2,k-i2](1ythenmax:=x;

end;

proceduremain;

va