動態規劃經典教程
引言：本人在做過一些題目後對DP有些感想，就寫了這個總結：
第一節 動態規劃基本概念
一，動態規劃三要素：階段，狀態，決策。
他們的概唸到處都是，我就不多說了，我只說說我對他們的理解：
如果把動態規劃的求解過程看成一個工廠的生產線，階段就是生產某個商品的不同的環節，狀態就是工件當前的形態，決策就是對工件的操作。顯然不同階段是對產品的一個前面各個狀態的小結，有一個個的小結構成了最終的整個生產線。每個狀態間又有關聯（下一個狀態是由上一個狀態做了某個決策後產生的）。
下面舉個例子：
要生產一批雪糕，在這個過程中要分好多環節：購買牛奶，對牛奶提純處理，放入工廠加工，加工後的商品要包裝，包裝後就去銷售……，這樣沒個環節就可以看做是一個階段；產品在不同的時候有不同的狀態，剛開始時只是白白的牛奶，進入生產後做成了各種造型，從冷凍庫拿出來後就變成雪糕（由液態變成固態=_=||）。每個形態就是一個狀態，那從液態變成固態經過了冰凍這一操作，這個操作就是一個決策。
一個狀態經過一個決策變成了另外一個狀態，這個過程就是狀態轉移，用來描述狀態轉移的方程就是狀態轉移方程。
經過這個例子相信大家對動態規劃有所瞭解了吧。
下面在說說我對動態規劃的另外一個理解：
用圖論知識理解動態規劃：把動態規劃中的狀態抽象成一個點，在有直接關聯的狀態間連一條有向邊，狀態轉移的代價就是邊上的權。這樣就形成了一個有向無環圖AOE網（為什麼無環呢？往下看）。對這個圖進行拓撲排序，刪除一個邊後同時出現入度為0的狀態在同一階段。這樣對圖求最優路徑就是動態規劃問題的求解。
二，動態規劃的適用範圍
動態規劃用於解決多階段決策最優化問題，但是不是所有的最優化問題都可以用動態規劃解答呢？
一般在題目中出現求最優解的問題就要考慮動態規劃了，但是否可以用還要滿足兩個條件：
最優子結構（最優化原理）
無後效性
最優化原理在下面的最短路徑問題中有詳細的解答；
什麼是無後效性呢？
就是說在狀態i求解時用到狀態j而狀態j就解有用到狀態k…..狀態N。
而求狀態N時有用到了狀態i這樣求解狀態的過程形成了環就沒法用動態規劃解答了，這也是上面用圖論理解動態規劃中形成的圖無環的原因。
也就是說當前狀態是前面狀態的完美總結，現在與過去無關。。。
當然，有是換一個劃分狀態或階段的方法就滿足無後效性了，這樣的問題仍然可以用動態規劃解。
三，動態規劃解決問題的一般思路。
拿到多階段決策最優化問題後，第一步要判斷這個問題是否可以用動態規劃解決，如果不能就要考慮搜索或貪心了。當卻定問題可以用動態規劃後，就要用下面介紹的方法解決問題了：
（1）模型匹配法：
最先考慮的就是這個方法了。挖掘問題的本質，如果發現問題是自己熟悉的某個基本的模型，就直接套用，但要小心其中的一些小的變動，現在考題辦都是基本模型的變形套用時要小心條件，三思而後行。這些基本模型在先面的分類中將一一介紹。
（2）三要素法
仔細分析問題嘗試著確定動態規劃的三要素，不同問題的卻定方向不同：
先確定階段的問題：數塔問題，和走路問題（詳見解題報告）
先確定狀態的問題：大多數都是先確定狀態的。
先確定決策的問題：背包問題。（詳見解題報告）
一般都是先從比較明顯的地方入手，至於怎麼知道哪個明顯就是經驗問題了，多做題就會發現。
（3）尋找規律法：
這個方法很簡單，耐心推幾組數據後，看他們的規律，總結規律間的共性，有點貪心的意思。
（4）邊界條件法
找到問題的邊界條件，然後考慮邊界條件與它的領接狀態之間的關係。這個方法也很起效。
（5）放寬約束和增加約束
這個思想是在陳啟鋒的論文裡看到的，具體內容就是給問題增加一些條件或刪除一些條件使問題變的清晰。
第二節 動態規劃分類討論
這裡用狀態維數對動態規劃進行了分類：
1.狀態是一維的
1．1下降/非降子序列問題：
問題描述： {挖掘題目的本質，一但抽象成這樣的描述就可以用這個方法解}
在一個無序的序列a1,a2,a3,a4…an裡，找到一個最長的序列滿足：ai<=aj<=ak…<=am,且i<j<k…aj>ak…>am,且i>j>k…>m.（最長下降子序列）。
問題分析：
如果前i-1個數中用到ak (ak>ai或akai(或aj<=ai)，opt[j]+1就是opt[i]的值；用方程表示為：{我習慣了這種寫法，但不是狀態轉移方程的標準寫法 }
opt[i]=max(opt[j])+1 (0<=j<i 且aj<=ai) {最長非降子序列}
opt[i]=max(opt[j])+1 (0<=jai) {最長下降子序列}
實現求解的部分代碼：
opt[0]:=maxsize；{maxsize 為maxlongint或-maxlongint}
for i:=1 to n do
for j:=0 to i-1 do
if ( a[j]>a[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
ans:=-maxlongint;
for i:=1 to n do
if opt[i]>ans then ans:=opt[i]; {ans 為最終解}
複雜度：從上面的實現不難看出時間複雜度為O（N2），空間複雜度O（N）；
例題1 攔截導彈 (missile.pas/c/cpp) 來源：NOIP1999(提高組) 第一題
【問題描述】
某國為了防禦敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發砲彈能夠到達任意的高度，但是以後每一發砲彈都不能高於前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由於該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。
輸入導彈依次飛來的高度（雷達給出的高度數據是不大於30000的正整數），計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。
【輸入文件】missile.in
單獨一行列出導彈依次飛來的高度。
【輸出文件】missile.out
兩行，分別是最多能攔截的導彈數，要攔截所有導彈最少要配備的系統數
【輸入樣例】
389 207 155 300 299 170 158 65
【輸出樣例】
6
2
【問題分析】
有經驗的選手不難看出這是一個求最長非升子序列問題，顯然標準算法是動態規劃。
以導彈依次飛來的順序為階段，設計狀態opt[i]表示前i個導彈中攔截了導彈i可以攔截最多能攔截到的導彈的個數。
狀態轉移方程：
opt[i]=max(opt[j])+1 (h[i]>=h[j],0=<j=a[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
anslen:=0;
for i:=1 to n do
if opt[i]>anslen then
anslen:=opt[i];
fillchar(opt,sizeof(opt),0);
a[0]:=-maxlongint;
for i:=1 to n do
for j:=i-1 downto 0 do
if (a[j]opt[i]) then
opt[i]:=opt[j]+1;
anstime:=0;
for i:=1 to n do
if opt[i]>anstime then
anstime:=opt[i];
end;
procedure print;
begin
writeln(anslen);
writeln(anstime);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
例題二 合唱隊形 (chorus.pas/c/cpp) 來源：NOIP2004(提高組) 第一題
N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學排成合唱隊形。
合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1，2…，K，他們的身高分別為T1，T2，…，TK， 則他們的身高滿足T1<...Ti+1>…>TK(1<=i<=K)。
你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。
【輸入文件】
輸入文件chorus.in的第一行是一個整數N(2<=N<=100)，表示同學的總數。第一行有n個整數，用空格分隔，第i個整數Ti(130<=Ti<=230)是第i位同學的身高(釐米)。
【輸出文件】
輸出文件chorus.out包括一行，這一行只包含一個整數，就是最少需要幾位同學出列。
【樣例輸入】
8
186 186 150 200 160 130 197 220
【樣例輸出】
4
【數據規模】
對於50％的數據，保證有n<=20；
對於全部的數據，保證有n<=100。
【問題分析】
出列人數最少，也就是說留的人最多，也就是序列最長。
這樣分析就是典型的最長下降子序列問題。只要枚舉每一個人站中間時可以的到的最優解。顯然它就等於，包括他在內向左求最長上升子序列，向右求最長下降子序列。
我們看一下複雜度：
計算最長下降子序列的複雜度是O（N2），一共求N次，總複雜度是O（N3）。這樣的複雜度對於這個題的數據範圍來說是可以AC的。但有沒有更好的方法呢？
其實最長子序列只要一次就可以了。因為最長下降（上升）子序列不受中間人的影響。
只要用OPT1求一次最長上升子序列，OPT2求一次最長下降子序列。這樣答案就是N-max(opt1[i]+opt2[i]-1).
複雜度由O（N3）降到了O（N2）。
【源代碼】
program chorus;
const
fin='chorus.in';
fout='chorus.out';
maxn=200;
var
opt1,opt2,a:array[0..maxn] of longint;
n,ans:longint;
procedure init;
var
i:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
readln(n);
for i:=1 to n do
read(a[i]);
end;
procedure main;
var
i,j:longint;
begin
a[0]:=-maxlongint;
for i:=1 to n do
for j:=i-1 downto 0 do
if (a[j]opt1[i]) then
opt1[i]:=opt1[j]+1;
a[n+1]:=-maxlongint;
for i:=n downto 1 do
for j:=i+1 to n+1 do
if (a[j]opt2[i]) then
opt2[i]:=opt2[j]+1;
ans:=0;
for i:=1 to n do
if opt1[i]+opt2[i]>ans then
ans:=opt1[i]+opt2[i];
end;
procedure print;
begin
writeln(n-ans+1);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
例題3 Buy Low Buy Lower (buylow.pas/c/cpp) 來源: USACO 4-3-1
【問題描述】
「逢低吸納」是炒股的一條成功秘訣。如果你想成為一個成功的投資者，就要遵守這條秘訣:
"逢低吸納,越低越買"
這句話的意思是：每次你購買股票時的股價一定要比你上次購買時的股價低.按照這個規則購買股票的次數越多越好，看看你最多能按這個規則買幾次。
給定連續的N天中每天的股價。你可以在任何一天購買一次股票，但是購買時的股價一定要比你上次購買時的股價低。寫一個程序，求出最多能買幾次股票。
以下面這個表為例, 某幾天的股價是:
天數 1 2 3 4 5 6 7 8 9 10 11 12
股價 68 69 54 64 68 64 70 67 78 62 98 87
這個例子中, 聰明的投資者(按上面的定義)，如果每次買股票時的股價都比上一次買時低，那麼他最多能買4次股票。一種買法如下(可能有其他的買法):
天數 2 5 6 10
股價 69 68 64 62
【輸入文件】buylow.in
第1行: N (1 <= N =a[j],0=<j<i) {a[i]存第i天股價}
最大的opt[i]就是最終的解。
第二問呢，稍麻煩一點。
從問題的邊界出發考慮問題，當第一問求得一個最優解opt[i]=X時，
在1到N中如果還有另外一個opt[j]=x那麼選取J的這個方案肯定是成立的。
是不是統計所有的opt[j]=x 的個數就是解了呢？
顯然沒那麼簡單，因為選取Ｊ這天的股票構成的方案不見得＝１，看下面一個例子：
５ 6 4 3 １ 2
方案一：５４３１
方案二：５４３２
方案三：６４３１
方案四：６４３２
x=4
也就是所雖然opt[5]=X 和opt[6]=X但個數隻有兩個，而實際上應該有四個方案，但在仔細觀察發現，構成opt[5]=x 的這個方案中 opt[j]=x-1的方案數有兩個,opt[j]=x-2的有一個，opt[j]=x-3 的有一個……
顯然這是滿足低歸定義的設計函數F（i）表示前I張中用到第i張股票的方案數。
遞推式：
1 (i=0)
F(i)=
Sum(F(j)) (0<=ja[i],opt[j]=opt[i]-1) {sum 代表求和}
答案=sum(F(j)) {0<ja[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
for i:=1 to n do
begin
j:=i-1;
while (j>0) and ((opt[i]opt[j]) or (a[i]a[j])) do
dec(j);
next[i]:=j;
end;
F[0,1]:=1;
for i:=1 to n+1 do
for j:=i-1 downto next[i] do
if (opt[j]=opt[i]-1) and (a[j]>a[i]) then
Hinc(F[i],F[j]);
end;
procedure print;
var
i,top,m:longint;
begin
write(opt[n+1]-1,' ');
top:=maxsize;
while (top>1) and (F[n+1][top]=0) do
dec(top);
write(F[n+1,top]);
for i:=top-1 downto 1 do
begin
m:=F[n+1,i];
while m<maxsize div 10 do
begin
write('0');
m:=m*10;
end;
write(F[n+1,i]);
end;
writeln;
close(input);
close(output);
end;
begin
init;
main;
print;
end.
例題4 船 (ships.pas/c/cpp) 來源：《奧賽經典》（提高篇）
【問題描述】
PALMIA國家被一條河流分成南北兩岸，南北兩岸上各有N個村莊。北岸的每一個村莊有一個唯一的朋友在南岸，且他們的朋友村莊彼此不同。
每一對朋友村莊想要一條船來連接他們，他們向政府提出申請以獲得批准。由於河面上常常有霧，政府決定禁止船隻航線相交（如果相交，則很可能導致碰船）。
你的任務是編寫一個程序，幫助政府官員決定批准哪些船隻航線，使得不相交的航線數目最大。
【輸入文件】ships.in
輸入文件由幾組數據組成。每組數據的第一行有2個整數X，Y，中間有一個空格隔開，X代表PALMIA河的長度（10<=X<=6000），Y代表河的寬度（10<=Y<=100）。第二行包含整數N，表示分別坐落在南北兩岸上的村莊的數目（1<=N<=5000）。在接下來的N行中，每一行有兩個非負整數C，D，由一個空格隔開，分別表示這一對朋友村莊沿河岸與PALMIA河最西邊界的距離（C代表北岸的村莊，D代表南岸的村莊），不存在同岸又同位置的村莊。最後一組數據的下面僅有一行，是兩個0，也被一空格隔開。
【輸出文件】ships.out
對輸入文件的每一組數據，輸出文件應在連續的行中表示出最大可能滿足上述條件的航線的數目。
【輸入樣例】
30 4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
0 0
【輸出樣例】
4
【問題分析】
這道題目相對來說思考難度較高，從字面意義上看不出問題的本質來，有點無法下手的感覺。這裡我給大家推薦兩種思考這類問題的方法。
法一：尋找規律法（我前面總結提到的第3個方法）
尋找規律自然要推幾組數據，首先當然有從樣例入手；
仔細觀察上圖：紅色航線是合法的，那麼他們滿足什麼規律呢？
C1 C2 C3 C4
北岸紅線的端點： 4 9 15 17
南岸紅線的端點： 2 8 12 17
D1 D2 D3 D4
不難看出無論線的斜率如何，都有這樣的規律：
C1<C2<C3<C4 且 D1<D2<D3<D4
如果我們把輸入數據排升序，問題變抽象為：
在一個序列（D）裡找到最長的序列滿足DI<DJ<Dk……且i<j<k
這樣的話便是典型的最長非降子序列問題了。。。。
法二：邊界條件法（我前面總結提到的第4個方法）
邊界法其實就是把數據往小了縮，顯然N=1是答案是1。N=2時呢？
考慮這樣一組數據：
N=2
C1 D1
C2 D2
當 C1D2 那麼一定會相交，反之則不會相交。
當C1 >C2時，如果D1<D2 那麼一定會相交，反之則不會相交。
N=3
C1 D1
C2 D2
C3 D3
……
其實不用在推導N=3了，有興趣的可以推導去。看N=2時就能得出：
對於任意兩條航線如果滿足Ci<Cj 且Di<Dj 則兩條航線不相交。這樣的話要想在一個序列裡讓所有的航線都不相交那比然滿足，C1<C2<C3…Cans且D1<D2<D3…<Dans ，也就是將C排序後求出最長的滿足這個條件的序列的長度就是解。
這樣分析後顯然是一個最長非降子序列問題。
複雜度：排序可以用O（nlogn）的算法，求最長非降子序列時間複雜度是O(n2).
總複雜度為O（n2）.
【源代碼】
program ships;
const
fin='ships.in';
fout='ships.out';
maxn=5010;
type
retype=record
C,D:longint;
end;
var
x,y,n,ans:longint;
a:array[0..maxn] of retype;
opt:array[0..maxn] of longint;
procedure init;
var
i:longint;
begin
readln(n);
for i:=1 to n do
read(a[i].c,a[i].d);
end;
procedure quick(L,r:longint);
var
i,j,x:longint;
y:retype;
begin
i:=L;
j:=r;
x:=a[(i+j) div 2].c;
repeat
while a[i].cx do
dec(j);
if ij;
if j>L then quick(L,j);
if i<r then quick(i,r);
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),0);
quick(1,n);
for i:=1 to n do
for j:=0 to i-1 do
if (a[j].dopt[i]) then
opt[i]:=opt[j]+1;
ans:=-maxlongint;
for i:=1 to n do
if ans<opt[i] then
ans:=opt[i];
writeln(ans);
end;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(x,y);
while (x+y0) do
begin
init;
main;
read(x,y);
end;
close(input);
close(output);
end.
1.2背包問題
首先說說背包問題的基本模型：
現有N個物品，每個物品的價值為V，重量為W。求用一個載重量為S的背包裝這寫物品，使得所裝物品的總價值最高。
背包問題用貪心和搜索解，當然效果不佳，不過在我的貪心和搜索總結中會說到。顯然標準的解法是動態規化，我在解決這個問題時習慣設計一維狀態，還可以設計二維的，二維狀態在下面會講，現在只討論用一維狀態實現背包問題。
背包問題的分類：
(1)小數背包:物品的重量是實數，如油，水等可以取1.67升……
(2)整數背包：0/1背包：每個物品只能選一次，或不選。不能只選一部分
部分背包：所選物品可以是一部分。
(3)多重背包：背包不只一個。
小數背包：在貪心總結中會細講。
整數背包：
部分背包：同小數背包。
0/1背包：這個問題是最經常出現的問題，應該熟練掌握。
我們先看一下0/1背包的簡化版：
現有N個物品，每個物品重量為W，這些物品能否使在載重量為S的背包裝滿（即重量和正好為S）？如過不能那能使物品重量和最重達到多少？
針對這一問題我們以物品的個數分階段，設計一個狀態opt[i]表示載重量為i的背包可否裝滿，顯然opt[i]的基類型是boolean。
決策是什麼呢？
當要裝第i個物品時，如果前i-1個物品可以使載重為 k的背包裝滿，那麼載重為k+w[i]的背包就可以裝滿。於是對於一個opt[j]來說，只要opt[j-w[i]]是true（表示可裝滿）那opt[j]就可以裝滿，但要注意：針對每一個物品枚舉背包的載重量時如果這樣正向的推導會使同一個物品用好幾次，因為k+w[i]可裝滿那k+w[i]+w[i]就可裝滿，但實際上是裝不滿的因為物品只有一個。解決這個問題很簡單，只要逆向推導就OK了。
這樣劃分階段，設計狀態，滿足無後效性和麼？
顯然對與一個每一個階段都是獨立的，物品的順序並不影響求解，因為裝物品的次序不限。而對於opt[j]只考慮opt[j-w[i]]而不考慮後面的，所以滿足無後效性。
有了上面的分析不難寫出狀態轉移方程：
opt[j]:=opt[j-w[1]] {opt[j-w[i]]=true}
時間複雜度：
階段數O(S)*狀態數（O(N)）*轉移代價（O(1)）=O（SN）
下面看幾個例題：
例題5 裝箱問題 (pack.pas/c/cpp) 來源：NOIP2001(普及組) 第四題
【問題描述】
有一個箱子容量為V（正整數，0＜＝V＜＝20000），同時有n個物品（0＜n＜＝30＝，每個物品有一個體積（正整數）。
要求n個物品中，任取若干個裝入箱內，使箱子的剩餘空間為最小。
【輸入文件】
第一 行一個正整數V表示箱子的容量，第二行一個正整數N表示物品個數，接下來N行列出這N個物品各自的體積。
【輸出文件】
單獨一行，表示箱子最小的剩餘空間。
【輸入樣例】
24
6
8
3
12
7
9
7
【輸出樣例】
0
【問題分析】
本題是經典的0/1背包問題，並且是0/1背包的簡化版，把箱子看做背包，容量看做載重量，體積看做重量，剩餘空間最小也就是儘量裝滿背包。於是這個問題便成了：
有一個栽重量為V的背包，有N個物品，儘量多裝物品，使背包儘量的重。
設計一個狀態opt[i]表示重量i可否構成。
狀態轉移方程：opt[j]:=opt[j-w[1]] {opt[j-w[i]]=true}
最終的解就是v-x（x<=n 且opt[x]=true 且 opt[x+1..n]=false）。
【源代碼1】
program pack;
const
fin='pack.in';
fout='pack.out';
maxv=20010;
maxn=100;
var
opt:array[0..maxv] of boolean;
w:array[0..maxn] of longint;
v,n,x:longint;
procedure init;
var
i:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(v);
read(n);
for i:=1 to n do
read(w[i]);
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to n do
for j:=v downto w[i] do
if opt[j-w[i]] then opt[j] :=true;
x:=v;
while not opt[x] do dec(x);
end;
procedure print;
begin
writeln(v-x);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
例題6 砝碼稱重 來源：NOIP1996（提高組） 第四題
【問題描述】
設有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重<=1000），用他們能稱出的重量的種類數。
【輸入文件】
a1 a2 a3 a4 a5 a6
（表示1g砝碼有a1個，2g砝碼有a2個，…，20g砝碼有a6個，中間有空格）。
【輸出文件】
Total=N
（N表示用這些砝碼能稱出的不同重量的個數，但不包括一個砝碼也不用的情況）。
【輸入樣例】
1 1 0 0 0 0
【輸出樣例】
TOTAL=3
【問題分析】
把問題稍做一個改動，已知a1+a2+a3+a4+a5+a6個砝碼的重量w[i], w[i]∈{ 1,2,3,5,10,20} 其中砝碼重量可以相等，求用這些砝碼可稱出的不同重量的個數。
這樣一改就是經典的0/1背包問題的簡化版了，求解方法完全和上面說的一樣，這裡就不多說了，只是要注意這個題目不是求最大載重量，是統計所有的可稱出的重量的個數。
【源代碼1】
program P4;
const
maxn=1010;
w:array[1..6] of longint=(1,2,3,5,10,20);
var
opt:array[0..maxn] of boolean;
a:array[1..6] of longint;
procedure init;
var
i:longint;
begin
for i:=1 to 6 do
read(a[i]);
end;
procedure main;
var
i,j,k:longint;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to 6 do
for j:=1 to a[i] do
for k:=maxn downto w[i] do
if opt[k-w[i]] then opt[k]:=true;
end;
procedure print;
var
ans,i:longint;
begin
ans:=0;
for i:=1 to maxn do
if opt[i] then
inc(ans);
writeln(ans);
end;
begin
init;
main;
print;
end.
例題7 積木城堡 來源：vijos P1059
【問題描述】
XC的兒子小XC最喜歡玩的遊戲用積木壘漂亮的城堡。城堡是用一些立方體的積木壘成的，城堡的每一層是一塊積木。小XC是一個比他爸爸XC還聰明的孩子，他發現壘城堡的時候，如果下面的積木比上面的積木大，那麼城堡便不容易倒。所以他在壘城堡的時候總是遵循這樣的規則。
小XC想把自己壘的城堡送給幼兒園裡漂亮的女孩子們，這樣可以增加他的好感度。為了公平起見，他決定把送給每個女孩子一樣高的城堡，這樣可以避免女孩子們為了獲得更漂亮的城堡而引起爭執。可是他發現自己在壘城堡的時候並沒有預先考慮到這一點。所以他現在要改造城堡。由於他沒有多餘的積木了，他靈機一動，想出了一個巧妙的改造方案。他決定從每一個城堡中挪去一些積木，使得最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺得應該使最後的城堡都儘可能的高。
任務：
請你幫助小XC編一個程序，根據他壘的所有城堡的信息，決定應該移去哪些積木才能獲得最佳的效果。
【輸入文件】
第一行是一個整數N(N0 do
begin
inc(top);
a[top]:=m;
inc(tothig,m);
read(m);
end;
for i:=1 to top do
for j:=tothig downto 1 do
if (j-a[i]>=0) and (opt[ii,j-a[i]]) then
opt[ii,j]:=true;
end;
ans:=maxhig;
while not opt[1,ans] do
dec(ans);
while not can(ans) do
dec(ans);
writeln(ans);
end;
begin
init;
main;
end.
回顧上面的內容充分說明動態規劃的本質就是遞推。其實按照我的理解（動規涉及最優決策，遞推是單純的總結）背包問題的簡化版更準確點算是遞推而非動態規劃，至於動歸和遞推之間的界線本來就很模糊（至少我這麼認為）把它看做什麼都可以，沒必要咬文嚼字。
回到0/1背包的原問題上（如果你忘了就去上面看看）。
如果在不知道這個模型的情況下我們怎麼做這個題呢？
這就要用到第一節提到的方法二：三要素法。
題目中明確說明對於一個物品要不就拿走要不就放下，其實題目赤裸裸的告訴我們決策就是不拿（用0表示）或拿（用1表示）。這樣想都不用想就知道了決策，這也是本題的突破口。知道了決策寫個搜索的程序應該是很輕鬆的了。
那麼階段是什麼呢？
顯然，給你一堆東西讓你往包裡塞，你當然是一個一個的那來，塞進去。那麼階段很明顯就是物品的個數。
狀態又是什麼呢？
有的人在裝東西是有個習慣（比如說我）就是先把東西分類，然後把同類的東西打個小包，最後在把小包放進去，我們可以按這個思想給物品打一些小包，也就是按照單位為1的遞增的順序準備好多小包，比如載重是6的包，可以為它準備載重是1，2，3，4，5的小包。這樣狀態就可以想出來了：
設計狀態opt[i，j]表示裝第i個物品時載重為j的包可以裝到的最大價值。
opt[i-1,j] (j-w[i]0)
狀態轉移方程：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個物品的重量，v[i]第i個物品的價值)
解釋：要載重為j的背包空出w[i]（j-w[i]）的空間且裝上第i個物品，比不裝獲得的價值大就裝上它。
邊界條件：opt[0,i]=0; (i∈{1..S})
註：
這種二維的狀態表示應該在下節講，但是為了方便理解先在這裡說了。
上面的方法動態規劃三要素都很明顯，實現也很簡單。但是在我初學背包時卻用另外一種一維的狀態表示法。
用第一節說的思考方法五（放寬約束和增加約束）在重新思考一下這個問題：
怎麼放寬約束呢？
把題目中的價值去掉，不考慮價值即最優就變成背包問題的簡化版了。那簡化版的求解對我們有何啟示呢？
再一次增加約束：背包只能裝滿。
顯然對於N個裝滿背包的方案中只要找到一個價值最大的就是問題的解。那麼裝不滿怎麼辦呢？其實裝不滿背包，它總要達到一定的重量（X）。我們可以把這種情況看作是裝滿一個載重為X的小包。
總結一下上面的思維過程：
放寬約束讓我們找到問題的突破口——和背包問題簡化版一樣，我們可以卻定載重為S的背包是否可以裝滿。
增加約束讓我們找到問題的求解方法——在裝滿背包的方案中選擇最優的一個方案。
這樣問題就解決了。
設計一個狀態opt[j]表示裝滿載重為j的背包可獲得的最大價值。對於第i個物品，只要opt[j-w[i]]可以裝滿且opt[j-w[i]]+v[i]比opt[j]大就裝上這個物品（更新opt[j]）。
怎麼使opt[j]既有是否構成又有最優的概念呢？
opt[j]只表示最優，只不過使初始條件+1，判斷opt[j]是否為0，如果opt[j]=0說明j裝不滿。
邊界條件：opt[0]=1;
狀態轉移方程：opt[j]=max{opt[j-w[i]]} (0<i<n,w[i]<=j<=S)
問題解： ans=max{opt[i]}-1 (0<i<=s)
時間複雜度：階段數O(S)*狀態數（O(N)）*轉移代價（O(1)）=O（SN）
下面看幾個例題：
例題8 採藥 (medic.pas/c/cpp) 來源：NOIP2005（普及組） 第三題
【問題描述】
辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞裡對他說：「孩子，這個山洞裡有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間裡，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大。」
如果你是辰辰，你能完成這個任務嗎？
【輸入文件】
輸入文件medic.in的第一行有兩個整數T（1 <= T <= 1000）和M（1 <= M <= 100），用一個空格隔開，T代表總共能夠用來採藥的時間，M代表山洞裡的草藥的數目。接下來的M行每行包括兩個在1到100之間（包括1和100）的整數，分別表示採摘某株草藥的時間和這株草藥的價值。
【輸出文件】
輸出文件medic.out包括一行，這一行只包含一個整數，表示在規定的時間內，可以采到的草藥的最大總價值。
【輸入樣例】
70 3
71 100
69 1
1 2
【輸出樣例】
3
【數據規模】
對於30%的數據，M <= 10；
對於全部的數據，M y then max:=x
else max:=y;
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),0);
for i:=1 to n do
for j:=1 to t do
if j-w[i]0) and (opt[j-w[i]]+v[i]>opt[j]) then
opt[j]:=opt[j-w[i]]+v[i];
ans:=-maxlongint;
for i:=1 to t do
if opt[i]>ans then ans:=opt[i];
end;
procedure print;
begin
writeln(ans-1);
close(output);
end;
begin
init;
main;
print;
end.
例題9 開心的金明 來源：NOIP2006（普及組）第二題
【問題描述】
金明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：「你的房間需要購買哪些物品，怎麼佈置，你說了算，只要不超過N 元錢就行」。今天一早金明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的N 元。於是，他把每件物品規定了一個重要度，分為5 等：用整數1~5 表示，第5 等最重要。他還從因特網上查到了每件物品的價格（都是整數元）。他希望在不超過N 元（可以等於N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設第j 件物品的價格為v[j]，重要度為w[j]，共選中了k 件物品，編號依次為j1...jk，則所求的總和為：v[j1]*w[j1]+..+v[jk]*w[jk]請你幫助金明設計一個滿足要求的購物單.
【輸入文件】
輸入的第1 行，為兩個正整數，用一個空格隔開： N m
（其中N（<30000）表示總錢數，m(<25)為希望購買物品的個數。）
從第2 行到第m+1 行，第j 行給出了編號為j-1的物品的基本數據，每行有2 個非負整數 v p
（其中v 表示該物品的價格（v≦10000），p 表示該物品的重要度（1~5））
【輸出文件】
輸出只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（=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;
procedure print;
var
i,ans:longint;
begin
ans:=0;
for i:=1 to n do
if opt[i]>ans then
ans:=opt[i];
writeln(ans-1);
end;
begin
init;
main;
print;
end.
例題10 金明的預算方案 (budget.pas/c/cpp) 來源：NOIP2006 第二題
【問題描述】
金明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：「你的房間需要購買哪些物品，怎麼佈置，你說了算，只要不超過N元錢就行」。今天一早，金明就開始做預算了，他把想買的物品分為兩類：主件與附件，附件是從屬於某個主件的，下表就是一些主件與附件的例子：
主件 附件
電腦 打印機，掃瞄儀
書櫃 圖書
書桌 檯燈，文具
工作椅 無
如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有0個、1個或2個附件。附件不再有從屬於自己的附件。金明想買的東西很多，肯定會超過媽媽限定的N元。於是，他把每件物品規定了一個重要度，分為5等：用整數1~5表示，第5等最重要。他還從因特網上查到了每件物品的價格（都是10元的整數倍）。他希望在不超過N元（可以等於N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。
設第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1，j2，……，jk，則所求的總和為：
v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*為乘號）
請你幫助金明設計一個滿足要求的購物單。
【輸入文件】
輸入文件budget.in 的第1行，為兩個正整數，用一個空格隔開：
N m （其中N（<32000）表示總錢數，m（<60）為希望購買物品的個數。）
從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數據，每行有3個非負整數： v p q
（其中v表示該物品的價格（v0，表示該物品為附件，q是所屬主件的編號）
【輸出文件】
輸出文件budget.out只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（0說明花i元可以買到物品。這樣就不難設計出這個狀態的轉移方程來：
opt[i]=max{opt[i],opt[i-wj]} ((i-wj>0) and (opt[i-wj]>0)) (0<jy then exit(x);
exit(y);
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),0);
opt[0]:=1;
for j:=1 to m do
for i:=n downto v[j] do
if q[j]=0 then
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;
procedure print;
begin
writeln((ans-1)*10);
close(output);
end;
begin
init;
main;
print;
end.
上面提到的幾個例題都是最基礎的題目，而且把問題抽象後就與背包問題的基本模型一樣了，但有些題目用到了基本模型，要求的解卻不一定很模型一樣，下面看個例子：
例題11 Money Systems (money.pas/c/cpp) 來源：USACO 2.3
【問題描述】
母牛們不但創建了他們自己的政府而且選擇了建立了自己的貨幣系統。[In their own rebellious way],，他們對貨幣的數值感到好奇。
傳統地，一個貨幣系統是由1,5,10,20 或 25,50, 和 100的單位面值組成的。
母牛想知道有多少種不同的方法來用貨幣系統中的貨幣來構造一個確定的數值。
舉例來說, 使用一個貨幣系統 {1,2,5,10,...}產生 18單位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。寫一個程序來計算有多少種方法用給定的貨幣系統來構造一定數量的面值。保證總數將會適合long long (C/C++) 和 Int64 (Free Pascal)。
【輸入文件】
貨幣系統中貨幣的種類數目是 V (1<= V<=25)。要構造的數量錢是 N (1<= N<=10,000)。
第 1 行: 二整數， V 和 N
第 2 行： 可用的貨幣 V 個整數。
【輸出文件】
單獨的一行包含那個可能的構造的方案數。
【輸入樣例】
3 10
1 2 5
【輸出樣例】
10
【問題分析】
把錢面值，把要構造的前看做載重為N的背包，這個問題便是0/1背包的簡化版了，但這個問題和傳統模型有所差異，不是判斷N是否可構成，而是求構成N的方案，而且這裡的面值是可以重複利用的（你可以看做是物品有無限多）。
對與第一個問題，只要把原來BOOLEAN型的狀態改為INT64，在遞推過程中累加方案數即可。
對於第二個問題，基本模型中為了避免重複在內重循環枚舉背包載重時採用倒循環，現在只要正向循環就OK了。
複雜度與原模型相同。
【源代碼】
{
ID:hhzhaojia2
PROG:money
LANG:PASCAL
}
program money;
const
fin='money.in';
fout='money.out';
maxv=100;
maxn=10010;
var
a:array[0..maxv] of longint;
opt:array[0..maxn] of int64;
v,n:longint;
procedure init;
var
i:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(v,n);
for i:= 1 to v do
read(a[i]);
close(input);
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),0);
opt[0]:=1;
for i:=1 to v do
for j:=a[i] to n do
inc(opt[j],opt[j-a[i]]);
end;
procedure print;
begin
writeln(opt[n]);
close(output);
end;
begin
init;
main;
print;
end.
背包問題方案的求法：
和大多數DP問題的方案的求法一樣，增加一個數組path和狀態維數相同用來記錄當前狀態的決策就OK了。
輸出方案時候通過當前決策推出上一決策，這一連穿的決策序列就是要求的方案。
下面看這樣一個數據：
載重：6 物品個數：3
重量 價值
物品1： 3 10
物品2： 2 2
物品3： 1 9
一維狀態求解過程：
i=1 : (枚舉物品)
opt[0..6]= 1 0 0 11 0 0 0
path[0..6]=0 0 0 1 0 0 0 {記錄最後裝入包中的物品的編號}
i=2
opt[0..6]=1 0 3 11 0 13 0
path[0..6]=0 0 2 1 0 2 0
i=3
opt[0..6]=1 10 3 12 20 13 22
path[0..6]=0 3 2 3 3 2 3
二維狀態求解過程： （略）
可以看到一維狀態的最優解是正確的，但細心分析發現一個驚人的問題： 方案不對！！
什麼最優解正確而方案不正確呢？
因為在解i=3時opt[6]用到的方案數應該是9+2+10=21。顯然這個方案是真確的，所以最優解正確。但是求解完opt[6]後，接著求解opt[3]卻把原來的opt[3]=10改成了opt[3]=2+9=11這樣，在整個求解過程結束後最後的方案opt[6]=9+2+10就變成了opt[6]=9+2+2+9也就是說1，2兩個物品裝了兩次。
這也正是我要說的下面的問題；
背包問題一維狀態於二維狀態的優劣：
顯然，一維狀態的維數少空間複雜度低。甚至在一些問題上可以減輕思考負擔。既然這樣是不是我們就應該屏棄二維狀態解法呢？
由於一維狀態在求解方案是存在錯誤，所以二維狀態還是很有用啊。當然有些問題雖然也是在求解方案但要求方案唯一這樣就又可以用一維狀態了。
看到這裡覺得頭暈就上趟廁所，返回來看下面的例題：
例題12 新年趣事之打牌 來源： vijos P1071
【問題描述】
過年的時候，大人們最喜歡的活動，就是打牌了。xiaomengxian不會打牌，只好坐在一邊看著。
這天，正當一群人打牌打得起勁的時候，突然有人喊道：「這副牌少了幾張！」眾人一數，果然是少了。於是這副牌的主人得意地說：「這是一幅特製的牌，我知道整副牌每一張的重量。只要我們稱一下剩下的牌的總重量，就能知道少了哪些牌了。」大家都覺得這個辦法不錯，於是稱出剩下的牌的總重量，開始計算少了哪些牌。由於數據量比較大，過了不久，大家都算得頭暈了。
這時，xiaomengxian大聲說：「你們看我的吧！」於是他拿出筆記本電腦，編出了一個程序，很快就把缺少的牌找了出來。
如果是你遇到了這樣的情況呢？你能辦到同樣的事情嗎？
【輸入文件】
第一行一個整數TotalW，表示剩下的牌的總重量。
第二行一個整數N（1<N<=100），表示這副牌有多少張。
接下來N行，每行一個整數Wi（1<=Wi0 then
begin
if opt[j]=0 then
path[j]:=i; {只有當前狀態沒求過才記錄方案}
inc(opt[j],opt[j-w[i]]);
end;
if opt[total]=0 then
begin
writeln('0');
halt;
end;
if opt[total]>1 then
begin
writeln('-1');
halt;
end;
i:=total;
while i>0 do
begin
ans[path[i]]:=false;
i:=i-w[path[i]];
end;
end;
procedure print;
var
i:longint;
begin
for i:=1 to n do
if ans[i] then write(i,' ');
end;
begin
init;
main;
print;
end.
1.3其它問題
一維動態規劃最常見的就是前面總結的最長下降/非降子序列和0/1背包問題了，當然還有別的一寫題。由於不是很常見所以沒有固定的解題模式，到時候具體問題具體分析。下面在看一些例子：
例題13 挖地雷問題 (P3.pas/c/cpp) 來源：NOIP1996（提高組）第三題（有改動）
【問題描述】
在一個地圖上有N個地窖（N 3 -> 4 -> 5
max=27
【Hint】
題目中的路徑是有向的且無環路（這是我做的改動原題中沒有要求）。
【問題分析】
看到題目的第一影響是貪心——以一點出發找與他連接的地窖中地雷數最多的一個。
但很容易想到反例：
5
1 2 1 1 100
1 1 0 0
0 1 0
0 1
0
按照貪心答案是3，但實際上答案是101。
於是就不得不放棄貪心的想法。
但是貪心給了我們啟示：從一個頂點出發要選擇向一個與他相連且以該點出發可以挖到較多雷的點走。（有點拗口）
另一種解釋：如果一個頂點連同N個份量，顯然要則一個較大的就是問題的解答，這個定義是滿足最優化原理的。
那它滿足無後效性麼？
因為圖是有向的，所以以與該頂點相連的點在往下走的路線中不包括該點。也就是說圖是一個AOV網（有向無環圖）。
既然滿足最優化原理，且無後效性，我們就可以用動態規劃解了。
這個問題的階段就是拓撲序列，但由於輸入是倒三角形，所以我們沒必要求拓撲序列，只要從N到著求解就可以了。
設計狀態opt[i]表示以i點出發可以挖到最多的雷的個數。
狀態轉移方程：opt[i]=max{opt[j]}+w[i] (g[i,j]=1)
(g存圖，w[i]存第i個地窖中的雷的個數)。
時間複雜度：
狀態數O(n)*轉移代價O(n)=O(n2)
這個題目還要求出路徑，可以用一個輔助數組path來記錄，path[i]表示從第i個出發走到的下一個點的編號。求解完只要按path記錄的路徑輸出即可。
【源代碼】
program P3;
const
fin='P3.in';
fout='P3.out';
maxn=200;
var
g:array[0..maxn,0..maxn] of longint;
n,ans:longint;
w,opt,path:array[0..maxn] of longint;
procedure init;
var
i,j:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(n);
fillchar(g,sizeof(g),0);
for i:=1 to n do
read(w[i]);
for i:=1 to n do
for j:=i+1 to n do
read(g[i,j]);
close(input);
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),0);
fillchar(path,sizeof(path),0);
for i:=n downto 1 do
begin
for j:=i+1 to n do
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;
for i:=2 to n do
if opt[i]>opt[ans] then ans:=i;
end;
procedure print;
var
i:longint;
begin
write(ans);
i:=path[ans];
while i>0 do
begin
write('-->',i);
i:=path[i];
end;
writeln;
writeln('max=',opt[ans]);
close(output);
end;
begin
init;
main;
print;
end.
2.狀態是二維的
通過前面的學習，我想因該對動態規劃不陌生了，我學習動態規劃是沒這麼系統，二維，一維一起上。二維狀態的動態規劃是重中之重。
所謂二維狀態就是說一般設計的狀態是opt[i,j]形式的。那i,j可以代表什麼呢？
有很多朋友問過我這個問題，我的回答是：
(1)i,j組合起來代表一個點的坐標（顯然是平面坐標系）（如：街道問題）。
(2)i,j組合表示一個矩陣的單元的位置（第i行，第j列）（如：數塔問題）
(3)起點為i長度為j的區間。（如：回文詞）
(4)起點為i終點為j的區間。（如：石子合併問題）
(5)兩個沒關聯的事物，事物1的第i個位置，對應事物2的第j個位置（花店櫥窗設計）
(6)兩個序列，第一個序列的前i個位置或第i個位置對應第2個序列的第j個位置或前j個位置。（最長公共子序列）。
(7)其它
下面通過例題和基本模型進一步說明：
2.1數塔問題
數塔問題來源於一道經典的IOI的題目，直接說題通過題目總結公性。以後遇到類似的題目可以參照這個模型。
例題14 數塔問題 (numtri.pas/c/cpp) 來源：IOI94
【問題描述】
考慮在下面被顯示的數字金字塔。
寫一個程序來計算從最高點開始在底部任意處結束的路徑經過數字的和的最大。每一步可以走到左下方的點也可以到達右下方的點。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的樣例中,從7 到 3 到 8 到 7 到 5 的路徑產生了最大和:30
【輸入文件】
第一個行包含 R(1<= R<=1000) ,表示行的數目。
後面每行為這個數字金字塔特定行包含的整數。
所有的被供應的整數是非負的且不大於100。
【輸出文件】
單獨的一行包含那個可能得到的最大的和。
【輸入樣例】
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
【輸出樣例】
30
【問題分析】
這個問題是學習動態規劃最簡單最經典的問題，說它經典是因為它的階段，狀態決策都十分明顯。
剛看到題目覺得沒有如手點，連怎麼儲存，描述這個金字塔都是問題，看輸入樣例發現：數字金字塔可以變成像輸入樣例那樣的下三角，這樣可以用一個二維數組儲a存它，並且可以用（i,j）描述一個數字在金字塔中的位置。
對於中間的一個點來說，想經過它則必須經過它的上方或左上（針對變化後的三角形）。也就是說經過這個點的數字和最大等於經過上方或左上所得的「最大和」中一個更大的加上這個點中的數字。顯然這個定義滿足最優子結構。
這樣階段很明顯就是金字塔的層，設計一個二維狀態opt[i,j]表示走到第i行第j列時經過的數字的最大和。決策就是opt[i-1,j] 或opt[i-1,j-1]中一個更大的加上（i,j）點的數字。
對於一個點只考慮上面或左上即前一階段，滿足無後效性。
狀態轉移方程：
opt[i-1,j]+a[i,j] (j=1)
opt[i,j]= opt[i-1,j-1]+ a[i,j] (j=i)
max{opt[i-1,j],opt[i-1,j-1]}+ a[i,j] (1<j=0所以方程也可以這樣寫:
opt[i,j]=max{opt[i-1,j],opt[i-1,j-1]}+a[i,j]
同理 j=i時方程也可以寫成上面那樣，所以方程綜合為：
opt[i,j]=max{opt[i-1,j],opt[i-1,j-1]}+a[i,j]（0<j<=i）
顯然答案是走到底後的一個最大值，即：
ans=max{opt[n,i]} (1<=i<=n)
其實從上往下走和從下往上走結果是一樣的，但是如果從下往上走結果就是opt[1,1]省下求最大值了，所以方程進一不改動：
opt[i,j]=max{opt[i+1,j],opt[i+1,j+1]}+a[i,j]（0<jopt[i+1,j+1] then
opt[i,j]:=opt[i+1,j]+a[i,j]
else opt[i,j]:=opt[i+1,j+1]+a[i,j];
end;
procedure print;
begin
writeln(opt[1,1]);
close(output);
end;
begin
init;
main;
print;
end.
例題15 Henry撿錢 (money.pas/c/cpp) 來源：Dream Team邀請賽
【問題描述】
最近,Henry由於失戀(被某大牛甩掉！)心情很是鬱悶.所以,他去了大牛家,尋求Michael大牛的幫助,讓他盡快從失戀的痛苦中解脫出來.Michael大牛知道Henry是很愛錢的,所以他是費盡腦水,絞盡腦汁想出了一個有趣的遊戲,幫助Henry.....
Michael感覺自己簡直是個天才(我們從不這麼認為),就把這個遊戲取名為:Henry揀錢.為了幫助更多的人採用這種方法早日脫離失戀之苦,Michael特地選在這次DT比賽中把遊戲介紹給大家...(大家鼓掌!!!)
其實,這個遊戲相當垃圾,目的就是為了滿足Henry這種具有強烈好錢的心理的人.遊戲是這樣的:Michael首先找到了一塊方形的土地,面積為m*n(米^2).然後他將土地劃分為一平方米大小的方形小格.Michael在每個格子下都埋有錢(用非負數s表示,表示人民幣的價值為s)和炸彈(用負數s表示,表示Henry挖出該方格下的東西會花掉s的錢去看病，醫炸彈炸傷的傷口)...遊戲的要求就是讓Henry從一側的中間列出發,按照下圖的5種方式前進（前進最大寬度為5）,不能越出方格.他每到一個格子,必定要取走其下相應的東西.直到到達土地的另一側,遊戲結束.不用說也知道,Henry肯定想得到最多的人民幣.所以他偷窺了,Michael埋錢的全過程,繪成了一張距陣圖.由於他自己手動找會很麻煩,於是他就找到了學習編程的你.請給幫他找出,最大人民幣價值.
揀錢路線規則(只有5個方向，如下圖)：
H為Henry的出發點，每組數據的出發點都是最後一行的中間位置！
(前方5個格子為當前可以到達的)
【輸入文件】
第一行為m n.(n為奇數)，入口點在最後一行的中間
接下來為m*n的數字距陣.
共有m行,每行n個數字.數字間用空格隔開.代表該格子下是錢或炸彈.
為了方便Henry清算,數字全是整數.
【輸出文件】
一個數,為你所找出的最大人民幣價值.
【輸入樣例】
6 7
16 4 3 12 6 0 3
4 -5 6 7 0 0 2
6 0 -1 -2 3 6 8
5 3 4 0 0 -2 7
-1 7 4 0 7 -5 6
0 -1 3 4 12 4 2
【輸出樣例】
51
【數據範圍】
N and M<=200.
結果都在longint範圍內
【問題分析】
去掉題目華麗的偽裝，我們可以這樣描述這個題目：
給定一個數字矩陣，從最後一層的中間出發可以向圖上所示的5個方向走，直到走到第一層，使經過的數字和最大。
如果我們不考慮負數對問題的影響，這個問題的描述就是經典的數塔問題了，只不過將塔變成了矩陣。
這樣就可以用剛剛講過的數塔問題的模型解這個題目了，我就不多說了。
狀態轉移方程：
opt[i,j]=max(opt[i-1,k])+a[i,j] (j-2<=k0) and (kmax) then
max:=opt[i-1,k];
opt[i,j]:=max+a[i,j];
end;
ans:=-maxlongint;
i:=(1+m) div 2;
for j:=i-2 to i+2 do
if (j>0) and (jans) then
ans:=opt[n,j];
end;
procedure print;
begin
writeln(ans);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
2.2街道問題
和數塔問題一樣街道問題也來源於一道典型的例題，下面我們看一下這道題。
例題16 街道問題 (way.pas/c/cpp) 來源：《奧賽經典》（提高篇）
【問題描述】
如圖所示的矩形圖中找到一條從左下角到右上角的最短路徑，圖中數字表示邊的長度。只能向右或向上走。
【輸入文件】第一行兩個數，N，M 矩形的點有N行M列。（0<N，M<1000）接下來N行每行M-1個數描述橫向邊的長度。接下來N-1行每行M個數描述縱向邊的長度。邊的長度小於10。
【輸出文件】一個數——最短路徑長度。
【輸入樣例】
4 5
3 7 4 8
4 6 3 5
3 6 3 5
5 4 6 2
7 6 3 5 3
2 8 5 9 4
8 7 4 3 7
【輸出樣例】
28
【問題分析】
因為只能向右或向上走，所以階段應該是這樣的：
如果把圖再做個改動看看：
這樣就想是上面說的數塔問題了，只不過數塔問題的數在點上而街道問題的數在邊上。但是並不影響問題的求解我們可以用數塔問題的思路來解這個問題。
設計一個二維狀態opt[i,j]表示走到（i,j）的最短路徑，顯然這個路徑只可能是左邊或上邊走來的，所以決策就是這兩個方向上加上經過的邊的和中一個較短的路。於是有下面的狀態轉移方程：
opt[i+1,j]+z[i,j] (j=1)
opt[i,j]＝ opt[i,j-1]+h[i,j] (i=n)
min{opt[i+1,j]+z[i,j],opt[i,j-1]+h[i,j]} (0<i<=n,0<j<=m)
和數塔問題一樣，這個問題也可以做類似的預處理：初始化opt的值是一個很大的數，保證解不會超過他，但要注意不要太的了，太大了可能有２２５問題。opt[0,0]=0。這樣就可以把方程整理為：
opt[i,j]= min{opt[i+1,j]+z[i,j],opt[i,j-1]+h[i,j]}
複雜度：狀態數O（N2）*轉移代價O（1）=O（N2）
這一類問題是很經典的問題。
思考這樣一個問題：如果讓找出一條最短路徑，一條較短路徑，且兩條路徑不重合該怎麼辦呢？
這個問題先留給大家思考，在後面的多維狀態中會詳細的講。
【源代碼】
program way;
const
fin='way.in';
fout='way.out';
maxn=1010;
var
h,z,opt:array[0..maxn,0..maxn] of longint;
n,m:longint;
procedure init;
var
i,j:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(n,m);
for i:=1 to n do
for j:=2 to m do
read(h[i,j]);
for i:=1 to n-1 do
for j:=1 to m do
read(z[i,j]);
close(input);
end;
function min(x,y:longint):longint;
begin
min:=y;
if x<y then min:=x;
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),$7F);
opt[n,0]:=0;
for i:=n downto 1 do
for j:=1 to m do
opt[i,j]:=min(opt[i+1,j]+z[i,j],opt[i,j-1]+h[i,j]);
end;
procedure print;
begin
writeln(opt[1,m]);
close(output);
end;
begin
init;
main;
print;
end.
還有一道例題是街道問題的變形在記憶化搜索處會說。
2.3最長公共子序列問題
和前面講的有所區別，這個問題的不涉及走向。很經典的動態規劃問題。
例題17 最長公共子序列 (lcs.pas/c/cpp) 來源：《全國青少年信息學奧林匹克聯賽培訓教材》
【問題描述】
一個給定序列的子序列是在該序列中刪去若干元素後得到的序列。確切地說，若給定序列X= ，則另一序列Z= 是X的子序列是指存在一個嚴格遞增的下標序列 ，使得對於所有j=1,2,…,k有 Xij=Zj
例如，序列Z=是序列X=的子序列，相應的遞增下標序列為。給定兩個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。例如，若X= 和Y= ，則序列是X和Y的一個公共子序列，序列也是X和Y的一個公共子序列。而且，後者是X和Y的一個最長公共子序列，因為X和Y沒有長度大於4的公共子序列。
給定兩個序列X= 和Y= ，要求找出X和Y的一個最長公共子序列。
【輸入文件】
輸入文件共有兩行，每行為一個由大寫字母構成的長度不超過200的字符串，表示序列X和Y。
【輸出文件】
輸出文件第一行為一個非負整數，表示所求得的最長公共子序列的長度，若不存在公共子序列，則輸出文件僅有一行輸出一個整數0，否則在輸出文件的第二行輸出所求得的最長公共子序列(也用一個 大寫字母組成的字符串表示。
【輸入樣例】
ABCBDAB
BDCBA
【輸出樣例】
4
BCBA
【問題分析】
這個問題也是相當經典的。。
這個題目的階段很不明顯，所以初看這個題目沒什麼頭緒，不像前面講的有很明顯的上一步，上一層之類的東西，只是兩個字符串而且互相沒什麼關聯。
但仔細分析發現還是有入手點的：
既然說是動態規劃，那我們首先要考慮的就是怎麼劃分子問題，一般對於前面講到的街道問題和數塔問題涉及走向的，考慮子問題時當然是想上一步是什麼？但這個問題沒有涉及走向，也沒有所謂的上一步，該怎麼辦呢？
既然是求公共子序列，也就有第一個序列的第i個字符和第二個序列的第j個字符相等的情況。
那麼我們枚第一個序列（X）的字符，和第二個序列（Y）的字符。
顯然如果X[i]=Y[j]那麼起點是1（下面說的子序列都是起點為1的），長度為i的子序列和長度為j的子序列的最長公共子序列就是長度為i-1和長度為j-1 的子序列中最長的公共子序列加上X[i]或Y[j]。
那要是不相等呢？
如果不相等，也就是說第一個序列長度為I的子序列和第二個序列中長度為j的子序列的公共子序列中X[i]和Y[j]不同時出現。也就是說第一個序列長度為i的子序列和第二個序列中長度為j的子序列的公共子序列是第一個序列長度為i的子序列和第二個序列中長度為j-1的子序列或第一個序列長度為i-1的子序列和第二個序列中長度為j的子序列的公共子序列中一個更長的。
設計一個狀態opt[i,j] 表示起點為1，第一序列長度為i，第二序列長度為j的子序列的最長公共子序列。按照上面的分類就可以得到狀態轉移方程：
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]))
(0<i<=length(X),0<j=length(opt[i,j-1]) then
opt[i,j]:=opt[i-1,j]
else opt[i,j]:=opt[i,j-1];
end;
procedure print;
begin
writeln(length(opt[L1,L2]));
write(opt[L1,L2]);
close(output);
end;
begin
init;
main;
print;
end.
例題18 回文詞 (palin.pas/c/cpp) 來源：IOI 2000
【問題描述】
回文詞是一種對稱的字符串——也就是說，一個回文詞，從左到右讀和從右到左讀得到的結果是一樣的。任意給定一個字符串，通過插入若干字符，都可以變成一個回文詞。你的任務是寫一個程序，求出將給定字符串變成回文詞所需插入的最少字符數。
比如字符串「Ab3bd」，在插入兩個字符後可以變成一個回文詞（「dAb3bAd」或「Adb3bdA」）。然而，插入兩個以下的字符無法使它變成一個回文詞。
【輸入文件】
第一行包含一個整數N，表示給定字符串的長度，3<=Ny then exit(x);
max:=y;
end;
procedure main;
var
i,x,j,k0,k1:longint;
begin
fillchar(opt,sizeof(opt),0);
readln(n);
readln(a);
b:='';
for i:=n downto 1 do
b:=b+a[i];
k0:=0;
k1:=1;
for i:=1 to n do
begin
fillchar(opt[k1],sizeof(opt[k1]),0);
for j:=1 to n do
begin
opt[k1,j]:=max(opt[k0,j],opt[k1,j-1]);
if a[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.
用這個方法AC了就該很高興了，但不要停止思考的步伐，還有別的方法麼？
從原問題出發，找這個問題的子問題。和上面說的最長公共子序列問題一樣，設計序列的問題我們一般要考慮它的子序列，也就是更短的序列。
這樣就回到了我第一節說的邊界條件法了。
顯然單獨的字符就是邊界了，而且單獨的字符就是回文詞，添加0個字符就可以了。
如果是兩個字符組成的序列怎麼辦呢？
只要看他們是否相同就可以了，如果相同那就是回文詞了，添加0個字符，如果不相同就在它的左邊或右邊添一個字符，讓另外一個當對稱軸。
如果是3個字符呢？
我們用S存這個序列，如果S[1]=S[3]那麼它就是回文詞了,
如果S[1]S[3]那麼就在前面添S[3]或後面添S[1]
剩下的就要考慮S[1]S[2]和S[2]S[3]這兩個序列了。
通過前面的分析我們很容易想到這樣的算法：
對於一個序列S只要看它的左右端的字符是否相同，如果相同那麼就看除掉兩端字符的新串要添的字符個數了；如果不同，就在它左面添上右斷的字符然後考慮去掉新序列兩端的字符後的串要添的字符。或者在右面添上左端的字符，在考慮去掉添了字符後新串左右兩端字符得到的新串要添的字符。
設計一個二維狀態opt[L,i]表示長度是L+1，起點是i的序列變成回文詞要添的字符的個數。階段就是字符的長度，決策要分類，即S[i] 和S[i+L]是否相等。
狀態轉移方程:
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])
複雜度：
空間複雜度=狀態數O（N2）
時間複雜度=狀態數O（N2）* 轉移代價O（1）=O（N2）
由於空間複雜度較高，仍然要用滾動數組。
【源代碼2】
program P1327;
const
maxn=5002;
var
a:array[0..maxn] of char;
opt:array[0..2,0..maxn] of longint;
n,ans:longint;
function min(x,y:longint):longint;
begin
min:=y;
if x<y then min:=x;
end;
procedure main;
var
i,L,j,k0,k1,k2:longint;
begin
fillchar(opt,sizeof(opt),0);
readln(n);
for i:=1 to n do
read(a[i]);
k0:=0;
k1:=1;
k2:=2;
for L:=1 to n-1 do
begin
for i:=1 to n-L do
begin
opt[k2,i]:=min(opt[k1,i],opt[k1,i+1])+1;
if a[i]=a[i+L] then
opt[k2,i]:=min(opt[k2,i],opt[k0,i+1]);
end;
j:=k0;
k0:=k1;
k1:=k2;
k2:=j;
end;
writeln(opt[k1,1]);
end;
begin
main;
end.
例題19 調整隊形 (queue.pas/c/cpp) 來源：TJU P1006
【問題描述】
學校藝術節上，規定合唱隊要參加比賽，各個隊員的衣服顏色不能很混亂：合唱隊員應排成一橫排，且衣服顏色必須是左右對稱的。
例如：「紅藍綠藍紅」或「紅藍綠綠藍紅」都是符合的，而「紅藍綠紅」或「藍綠藍紅」就不符合要求。
合唱隊人數自然很多，僅現有的同學就可能會有3000個。老師希望將合唱隊調整得符合要求，但想要調整儘量少，減少麻煩。以下任一動作認為是一次調整：
1、在隊伍左或右邊加一個人（衣服顏色依要求而定）；
2、在隊伍中任兩個人中間插入一個人（衣服顏色依要求而定）；
3、剔掉一個人；
4、讓一個人換衣服顏色；
老師想知道就目前的隊形最少的調整次數是多少，請你編一個程序來回答他。
因為加入合唱隊很熱門，你可以認為人數是無限的，即隨時想加一個人都能找到人。同時衣服顏色也是任意的。
【輸入文件】
第一行是一個整數n(1≦n≦3000)。
第二行是n個整數，從左到右分別表示現有的每個隊員衣服的顏色號，都是1到3000的整數。
【輸出文件】
一個數，即對於輸入隊列，要調整得符合要求，最少的調整次數。
【輸入樣例】
5
1 2 2 4 3
【輸出樣例】
2
【問題分析】
讀完題目發現很熟悉，仔細想想這個題就是回文詞的加強版。不同與回文詞的是這個問題的決策多了，不僅可以插入一個人（詞），還可以剔人，還可以換服裝，其實剔人和插入是等價的。也就是說比原問題只多了一個條件就是可以換服裝。
這樣就不能用回文詞的第一個方法解了。（因為序列中的元素不固定，可以換）。只能用第二個方法解。
和回文詞一樣，階段是序列的長度，狀態是opt[i,j]表示[i,j]這段區間內要變成回文所需要的最少的調整次數。
決策比回文詞多了一個，即：如果左右兩端不一樣還可以通過換服裝這種方式只花費一次的代價調整好。
狀態轉移方程：
min{opt[i,j-1]+1,opt[i+1,j]+1,opt[i+1,j-1]+1}
opt[i,j]= (a[i]a[j],1<=i<j<=n)
min{opt[i,j-1]+1,opt[i+1,j]+1,opt[i+1,j-1]}
(a[i]=a[j],1<=i<j<=n)
邊界條件:opt[i,i]=0 (1<=i<=n)
時間複雜度：
狀態數O（N2）*轉移代價O（1）=總複雜度O（N2）
【源代碼】
program queue;
const
fin='queue.in';
fout='queue.out';
maxn=3000;
var
a:array[0..maxn] of longint;
opt:array[0..maxn,0..maxn] of longint;
n:longint;
procedure init;
var
i:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
readln(n);
for i:=1 to n do
read(a[i]);
end;
procedure main;
var
i,j,L:longint;
begin
fillchar(opt,sizeof(opt),0);
for L:=1 to n-1 do
for i:=1 to n-L do
begin
j:=i+L;
if opt[i+1,j]+1<opt[i,j-1]+1 then
opt[i,j]:=opt[i+1,j]+1
else opt[i,j]:=opt[i,j-1]+1;
if a[i]=a[j] then
begin
if opt[i+1,j-1]<opt[i,j] then
opt[i,j]:=opt[i+1,j-1]
end
else begin
if opt[i+1,j-1]+1<opt[i,j] then
opt[i,j]:=opt[i+1,j-1]+1;
end;
end;
end;
procedure print;
begin
writeln(opt[1,n]);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
2.4 背包問題的拓展
前面說的背包問題還有個有趣的變形，可以說是背包問題的拓展吧，下面看一下這個例題：
例題20 找啊找啊找GF (gf.pas/c/cpp) 來源：MM群2007七夕模擬賽（RQNOJ 57）
【問題描述】
"找啊找啊找GF,找到一個好GF,吃頓飯啊拉拉手,你是我的好GF.再見."
"誒,別再見啊..."
七夕...七夕...七夕這個日子,對於sqybi這種單身的菜鳥來說是多麼的痛苦...雖然他聽著這首叫做"找啊找啊找GF"的歌,他還是很痛苦.為了避免這種痛苦,sqybi決定要給自己找點事情幹.他去找到了七夕模擬賽的負責人zmc MM,讓她給自己一個出題的任務.經過幾天的死纏爛打,zmc MM終於同意了.
但是,拿到這個任務的sqybi發現,原來出題比單身更讓人感到無聊-_-....所以,他決定了,要在出題的同時去辦另一件能夠使自己不無聊的事情--給自己找GF.
sqybi現在看中了n個MM,我們不妨把她們編號1到n.請MM吃飯是要花錢的,我們假設請i號MM吃飯要花rmb[i]塊大洋.而希望騙MM當自己GF是要費人品的,我們假設請第i號MM吃飯試圖讓她當自己GF的行為(不妨稱作泡該MM)要耗費rp[i]的人品.而對於每一個MM來說,sqybi都有一個對應的搞定她的時間,對於第i個MM來說叫做time[i]. sqybi保證自己有足夠的魅力用time[i]的時間搞定第i個MM^_^.
sqybi希望搞到儘量多的MM當自己的GF,這點是毋庸置疑的.但他不希望為此花費太多的時間(畢竟七夕賽的題目還沒出),所以他希望在保證搞到MM數量最多的情況下花費的總時間最少.
sqybi現在有m塊大洋,他也通過一段時間的努力攢到了r的人品(這次為模擬賽出題也攢rp哦~~).他憑藉這些大洋和人品可以泡到一些MM.他想知道,自己泡到最多的MM花費的最少時間是多少.
注意sqybi在一個時刻只能去泡一個MM--如果同時泡兩個或以上的MM的話,她們會打起來的...
【輸入文件】
輸入的第一行是n,表示sqybi看中的MM數量.
接下來有n行,依次表示編號為1, 2, 3, ..., n的一個MM的信息.每行表示一個MM的信息,有三個整數:rmb, rp和time.
最後一行有兩個整數,分別為m和r.
【輸出文件】
你只需要輸出一行,其中有一個整數,表示sqybi在保證MM數量的情況下花費的最少總時間是多少.
【輸入樣例】
4
1 2 5
2 1 6
2 2 2
2 2 3
5 5
【輸出樣例】
13
【數據規模】
對於20%數據,1<=n<=10;
對於100%數據,1<=rmb<=100,1<=rp<=100,1<=time<=1000;
對於100%數據,1<=m<=100,1<=r<=100,1<=n0說明花費正好)
狀態轉移方程：
opt[j,k]=max{opt[j-rmb[i],k-rp[i]]+1}
(rmb[i]<=j<=m,rp[i]<=k<=r,0<i0)
ct[j,k]:=min{ct[j-rmb[i],k-rp[i]]}+time[i] (opt[j,k]=opt[j-rmb[i],k-rp[i]]+1)
時間複雜度：
階段數 O（N）*狀態數O（MR）*轉移代價O（1）= O（NMR）
註：數據挺小的。
問題拓展：
如果要加入別的條件，比如泡MM還要一定的SP，等也就是說一個價值要不同的條件確定，那麼這個問題的狀態就需要在加一維，多一個條件就多一維。
【源代碼】
program gf;
const
fin='gf.in';
fout='gf.out';
maxn=110;
var
rmb,rp,time:array[0..maxn] of longint;
opt,ct:array[0..maxn,0..maxn] of longint;
n,m,r,ans,max:longint;
procedure init;
var
i:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(n);
for i:=1 to n do
read(rmb[i],rp[i],time[i]);
read(m,r);
close(input);
end;
procedure main;
var
i,j,k:longint;
begin
fillchar(opt,sizeof(opt),0);
fillchar(ct,sizeof(ct),0);
opt[0,0]:=1;
for i:=1 to n do
for j:=m downto rmb[i] do
for k:=r downto rp[i] do
if opt[j-rmb[i],k-rp[i]]>0 then
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]]+time[i];
end
else if (opt[j-rmb[i],k-rp[i]]+1=opt[j,k])
and (ct[j-rmb[i],k-rp[i]]+time[i]max then
begin
max:=opt[j,k];
ans:=ct[j,k];
end
else if (opt[j,k]=max) and (ct[j,k]0），打分越高的碟說明多多越愛看。每張碟有播放的時間Ti。多多想在今晚爺爺規定的時間裡看的碟總分最高。（必須把要看的碟看完，也就是說一張碟不能只看一半）。顯然叔叔在買碟是沒必要把N張全買了，只要買要看的就OK了，這樣節省資金啊。而且多多讓叔叔慣的特別任性只要他看到有幾張就一定會看完。
可是出現了一個奇怪的問題，買碟的地方只買給顧客M（M<N）張碟，不會多也不會少。這可讓多多叔叔為難了。怎麼可以在N張碟中只買M張而且在規定時間看完，而且使總價值最高呢？
聰明的你幫幫多多的叔叔吧。
【輸入說明】(watchdvd.in)
輸入文件有三行
第一行：兩個數空格隔開的正整數，N，M，L（分別表示叔叔給多多買的碟的數量，商店要買給叔叔的碟的數量，爺爺規定的看碟的時間段）。
第二行到第N行，每行兩個數：T，M，給出多多列表中DVD碟的信息。
【輸出說明】(watchdvd.out)
單獨輸出一行
表示多多今晚看的碟的總分。
如果商店賣給叔叔的M張碟無法在爺爺規定的時間看完輸出0；
【輸入樣例】
3 2 10
11 100
1 2
9 1
【輸出樣例】
3
【數據範圍】
20%的數據 N <=20; L<=2000;
100%的數據 N<=100 L<=2000; M y then max:=x;
end;
procedure main;
var
i,j,k:longint;
begin
fillchar(opt,sizeof(opt),0);
for i:=1 to n do
for j:=m downto 1 do
if j0) 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;
for i:=0 to v do
if opt[m,i]>ans then ans:=opt[m,i];
end;
procedure print;
begin
write(ans);
close(output);
end;
begin
init;
main;
print;
end.
2.5石子合併問題
也有人把這類問題叫做是區間上的動態規劃。
例題22 石子合併 (stone.pas/c/cpp) 來源：某年NOI（去巴蜀交）
【問題描述】
在一個操場上擺放著一行共n堆的石子。現要將石子有序地合併成一堆。規定每次只能選相鄰的兩堆合併成新的一堆，並將新的一堆石子數記為該次合併的得分。請編輯計算出將n堆石子合併成一堆的最小得分和將n堆石子合併成一堆的最大得分。
【輸入文件】
輸入第一行為n(n<1000)，表示有n堆石子，第二行為n個用空格隔開的整數，依次表示這n堆石子的石子數量（y then max:=x;
end;
function min(x,y:longint):longint;
begin
min:=y;
if (x0) then min:=x;
end;
procedure main;
var
i,j,L,k:longint;
begin
fillchar(minopt,sizeof(minopt),200);
fillchar(maxopt,sizeof(maxopt),0);
for i:=1 to 2*n do
minopt[i,i]:=0;
for L:=1 to n-1 do
for i:=1 to 2*n-L do
begin
j:=i+L;
for k:=i to j-1 do
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;
for i:=1 to n do
maxans:=max(maxans,maxopt[i,i+n-1]);
for i:=1 to n do
minans:=min(minans,minopt[i,i+n-1]);
{for i:=1 to n*2 do
begin
for j:=1 to n*2 do
write(maxopt[i,j],' ');
writeln;
end;}
end;
begin
init;
main;
writeln(minans,' ',maxans);
end.
例題23 能量項鏈 (energy.pas/c/cpp) 來源NOIP2006（提高組）
【問題描述】
在Mars星球上，每個Mars人都隨身佩帶著一串能量項鏈。在項鏈上有N顆能量珠。能量珠是一顆有頭標記與尾標記的珠子，這些標記對應著某個正整數。並且，對於相鄰的兩顆珠子，前一顆珠子的尾標記一定等於後一顆珠子的頭標記。因為只有這樣，通過吸盤（吸盤是Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標記為m，尾標記為r，後一顆能量珠的頭標記為r，尾標記為n，則聚合後釋放的能量為（Mars單位），新產生的珠子的頭標記為m，尾標記為n。
需要時，Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請你設計一個聚合順序，使一串項鏈釋放出的總能量最大。
例如：設N=4，4顆珠子的頭標記與尾標記依次為(2，3) (3，5) (5，10) (10，2)。我們用記號⊕表示兩顆珠子的聚合操作，(j⊕k)表示第j，k兩顆珠子聚合後所釋放的能量。則第4、1兩顆珠子聚合後釋放的能量為：
(4⊕1)=10*2*3=60。
這一串項鏈可以得到最優值的一個聚合順序所釋放的總能量為
((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。
【輸入文件】
輸入文件energy.in的第一行是一個正整數N（4≦N≦100），表示項鏈上珠子的個數。第二行是N個用空格隔開的正整數，所有的數均不超過1000。第i個數為第i顆珠子的頭標記（1≦i≦N），當i2 3 5 10 2 3 5 10
這樣處理後其中任意長度為N+1的鏈就可代表一個環，那麼問題就轉化成合併任意長度為N+1的鏈所能釋放的總能量最大。
也就是說從任意一點(i<k<j)把鏈拆成兩段問題的解就是合併這兩段釋放出最大能量在加上合併後這兩顆珠子再一次合併釋放的能量。將這個子問題進一步分解就是分解到鏈長度為1也就是就有兩課珠子時，生成這兩顆柱子沒有釋放能量，而合併他們釋放的能量是m*r*n。（這就是邊界條件）。
我們設計一個狀態opt [i,j] 表示合併頭為i，尾為j的鏈狀項鏈所能釋放的最多的能量值。邊界條件是opt[i,i]=0 (1<=i<=n*2).
根據定義不難得到動規的狀態轉移方程:
opt[i,j]=max{opt[i,j],opt[i,k]+opt[k,j]+a[i]*a[k]*a[j]}(i<ky then exit(x);
exit(y);
end;
procedure main;
var
i,j,k,L:longint;
begin
fillchar(opt,sizeof(opt),0);
for L:=2 to n do
for i:=1 to n*2-L+1 do
begin
j:=i+L;
for k:=i+1 to j-1 do
opt[i,j]:=max(opt[i,j],opt[i,k]+opt[k,j]+a[i]*a[j]*a[k]);
end;
for i:=1 to n do
ans:=max(ans,opt[i,i+n]);
end;
procedure print;
begin
writeln(ans);
close(output);
end;
begin
init;
main;
print;
end.
例題24 統計單詞個數 (.pas/c/cpp) 來源：NOIP2001（提高組）
【問題描述】
給出一個長度不超過200的由小寫英文字母組成的字母串(約定;該字串以每行20個字母的方式輸入，且保證每行一定為20個)。要求將此字母串分成k份(1<k<=40)，且每份中包含的單詞個數加起來總數最大(每份中包含的單詞可以部分重疊。當選用一個單詞之後，其第一個字母不能再用。例如字符串this中可包含this和is，選用this之後就不能包含th)。
單詞在給出的一個不超過6個單詞的字典中。
要求輸出最大的個數。
【輸入文件】
去部輸入數據放在文本文件input3.dat中，其格式如下：
每組的第一行有二個正整數(p，k)
p表示字串的行數;
k表示分為k個部分。
接下來的p行，每行均有20個字符。
再接下來有一個正整數s，表示字典中單詞個數。(1<=s<=6)
接下來的s行，每行均有一個單詞。
【輸出文件】
結果輸出至屏幕，每行一個整數，分別對應每組測試數據的相應結果。
【輸入樣例】
1 3
thisisabookyouareaoh
4
is
a
ok
sab
【輸出樣例】
7
【問題分析】
剛看到這個題目覺得很迷茫，沒入手點但是突然看到了閃亮的突破口：題目中說this包含this和is 但不包含th這也就是說在一個串內對於一個固定了起點的單詞只能用一次，即使他還可以構成別的單詞但他還是用一次。比如：串：thisa
字典：this is th
串中有this is th這三個單詞，但是對於this 和 th 只用一次，也就是說枚舉一下構成單詞的起點，只要以該起點的串中包含可以構成一個以該起點開頭的單詞，那麼就說明這個串中多包含一個單詞。
這樣可一得出下面的結果：
每舉的起點 結論：
t 至少包含1個
h 至少包含1個
i 至少包含2個
s 至少包含2個
a 至少包含2個
考慮到這裡，就有點眉目了。
題目中要將串分K個部分也就是說從一個點截斷後一個單詞就未必可以構成了。比如上例要分3個部分合理的其中的一個部分至多有3個字母，這樣this 這個單詞就構不成了。
要是分5個部分，那就連一個單詞都夠不成了。
這樣就需要對上面做個改動，上面的只控制了起點，而在題目中還需要限制終點，分完幾個部分後，每部分終點不同可以構成的單詞就不同了。
這樣就需要再枚舉終點了。
設計一個二維數組sum[i,j]統計從i到j的串中包含的單詞的個數
狀態轉移方程:
sum[i+1,j]+1 (s[i,j]中包含以S[i]開頭的單詞)
sum[i,j]=
sum[i+1,j] (與上面相反)
註：(1)這裡枚舉字符的起點的順序是從尾到頭的。
(2)有人把上面這次也看做是一次動態規劃，但我覺得更準確的說是遞推。
求出所有的SUM還差一步，就是不同的劃分方法顯然結果是不一樣的，但是對於求解的問題我們可以這樣把原問題分解成子問題：求把一個串分成K部分的最多單詞個數可以看做是先把串的最後一部分分出來，在把前面一部分分解成K-1個部分，顯然決策就是找到一種劃分的方法是前面的K-1部分的單詞+最後一部分的單詞最多。
顯然這個問題滿足最優化原理，那滿足不滿足無後效性呢？
對於一個串分解出最後一部分在分解前面的那部分是更本就不會涉及分好的這部分，換句話說沒次分解都回把串分解的更小，對於分解這個更小的傳不會用到不屬於這個小串的元素。這就滿足無後效性。
具體求解過程：
設計一個狀態opt[i,j]表示把從１到j的串分成i份可以得到最多的單詞的個數。決策就是枚舉分割點使當前這種分割方法可以獲得最多的單詞。
狀態轉移方程：opt[I,j]=max(opt[i-1,t]+sum[t+1,j]) (i<t<j)
邊界條件：opt[1,i]=sum[1,i] (0<iy then max:=x;
end;
procedure main;
var
i,j,t:longint;
begin
L:=length(s);
for i:=L downto 1 do
for j:=i to L do
if find(i,j) then sum[i,j]:=sum[i+1,j]+1
else sum[i,j]:=sum[i+1,j];
fillchar(opt,sizeof(opt),0);
opt[1]:=sum[1];
for i:=2 to k do
for j:=i+1 to L do
for t:=i+1 to j-1 do
opt[i,j]:=max(opt[i,j],opt[i-1,t]+sum[t+1,j]);
writeln(opt[k,L]);
end;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
init;
main;
close(input);
close(output);
end.
2.6其他問題
還有一些題目雖和一寫基本模型相似但又有區別，我也就不總結共性了，列出它們，看看他們的狀態又是怎麼設計的：
例題25 花店櫥窗設計 (flower.pas/c/cpp) 來源：IOI或巴蜀評測系統
【問題描述】假設以最美觀的方式佈置花店的櫥窗，有F束花，每束花的品種都不一樣，同時，至少有同樣數量的花瓶，被按順序擺成一行，花瓶的位置是固定的，並從左到右，從1到V順序編號，V 是花瓶的數目，編號為1的花瓶在最左邊，編號為V的花瓶在最右邊，花束可以移動，並且每束花用1到F 的整數惟一標識，標識花束的整數決定了花束在花瓶中列的順序即如果I < J，則花束I 必須放在花束J左邊的花瓶中。
例如，假設杜鵑花的標識數為1，秋海棠的標識數為2，康乃馨的標識數為3，所有的花束在放人花瓶時必須保持其標識數的順序，即：杜鵑花必須放在秋海棠左邊的花瓶中，秋海棠必須放在康乃馨左邊的花瓶中。如果花瓶的數目大於花束的數目，則多餘的花瓶必須空，即每個花瓶中只能放一束花。
每一個花瓶的形狀和顏色也不相同，因此，當各個花瓶中放人不同的花束時會產生不同的美學效果，並以美學值(一個整數)來表示，空置花瓶的美學值為0。在上述例子中，花瓶與花束的不同搭配所具有的美學值，可以用如下表格表示。
根據表格，杜鵑花放在花瓶2中，會顯得非常好看，但若放在花瓶4中則顯得很難看。
為取得最佳美學效果，必須在保持花束順序的前提下，使花的擺放取得最大的美學值，如果具有最大美學值的擺放方式不止一種，則輸出任何一種方案即可。題中數據滿足下面條件：1≦F≦100，F≦V≦100，－50≦AIJ≦50，其中AII是花束I擺放在花瓶J中的美學值。輸入整數F，V 和矩陣(AIJ)，輸出最大美學值和每束花擺放在各個花瓶中的花瓶編號。
┌───┬───┬───┬───┬───┬───┐
│ │花瓶1│花瓶2 │花瓶3│花瓶4 │花瓶5│
├───┼───┼───┼───┼───┼───┤
│杜鵑花│ 7 │ 23 │ -5 │ -24 │ 16 │
├───┼───┼───┼───┼───┼───┤
│秋海棠│ 5 │ 21 │ -4 │ 10 │ 23 │
├───┼───┼──┼─── ┼── ─┼───┤
│康乃馨│ -21 │ 5 │ -4 │ -20 │ 20 │
\───┴───┴───┴───┴───┴───┘
【輸入文件】
第一行包含兩個數：F，V。 隨後的F 行中，每行包含V 個整數，Aij 即為輸入文件中第（i+1 ）行中的第j 個數
【輸出文件】
包含兩行:第一行是程序所產生擺放方式的美學值。第二行必須用F 個數表示擺放方式，即該行的第K個數表示花束K所在的花瓶的編號。
【輸入樣例】
3 5
7 23 –5 –24 16
5 21 -4 10 23
-21 5 -4 -20 20
【輸出樣例】
53
2 4 5
【題目鏈接】
http://mail.bashu.cn:8080/JudgeOnline/showproblem?problem_id=1597
【問題分析】
這個問題很奇怪題目中給定的條件是花瓶和花束，似乎是兩個沒有關聯的事物啊，但著兩個看似沒關聯的東西，卻有一點聯繫：不同的花放在不同的花瓶中產生不同的美學價值。
一般人的思維都是拿來花一個一個的放，假設要放第i束花時，把它放到哪裡好呢？
很容易想到一個貪心的策略：找到一個符合條件（第i束花要放在前i-1束花的後面）下的它放如後能產生最大的美學價值的花瓶放。但和容易舉出反例：
│ │花瓶1│花瓶2 │花瓶3│
├───┼───┼───┼───|
│杜鵑花│ 1 │ 2 │ -5 |
├───┼───┼───┼─——|
│秋海棠│ 5 │ 10 │ 1 │
按照貪心策略是：杜鵑花放在2號瓶裡，秋海棠放在3號瓶裡，美學值：3
答案是： 杜鵑花放在1號瓶裡，秋海棠放在2號瓶裡，美學值：11
數據量很大搜索顯然不行。
那要是動態規劃，階段，狀態，決策有是什麼呢？
既然要拿來花束一個一個的放，我們就以花束劃分階段。設計一個狀態opt[i,j]表示將第i束花放在第j個花瓶中可使前i束花或得的最大美學價值，那麼決策就很容易想到了：將第i束花放在第j個瓶中，那麼第i-1束花只能放在前j-1個瓶裡，顯然我們要找到一個放在前j-1個瓶中的一個最大的美學價值在加上當前第i束放在第j個瓶中的美學價值就是OPT[I，J]的值。
顯然符合最優化原理和無後效性。
狀態轉移方程：
opt[i,j]=max{opt[i-1,k]}+a[i,j] (i<=k<=j-1) 為什麼是iopt[i,j] then
begin
opt[i,j]:=opt[i-1,k];
path[i,j]:=k;
end;
inc(opt[i,j],a[i,j]);
end;
ans:=n;
for i:=n+1 to m do
if opt[n,i]>opt[n,ans]then ans:=i;
end;
procedure outputway(i,j:longint);
begin
if i>0 then
begin
outputway(i-1,path[i,j]);
write(j,' ');
end;
end;
procedure print;
var
i:longint;
begin
writeln(opt[n,ans]);
outputway(n,ans);
writeln;
end;
begin
init;
main;
print;
end.
例題26 Divisibility 來源：ZJU2042
【問題描述】
Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions:
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
We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.
You are to write a program that will determine divisibility of sequence of integers.
譯題：
給出N個數，你可以在這N個數中任意地添加+號或-號，求出能不能使算出的結果被K整除。可以則打印「Divisible」，否則打印「Not divisible」
(1 <= N <= 10000, 2 <= K <= 100)
下面是一個例子：
有4個數，分別是17 5 -21 15
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
有8種添法，其中第二種求出的-14能被7整除。
【輸入文件】
The first line of the input contains two integers, N and K (1 <= N <= 10000, 2 <= K <= 100) separated by a space.
The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value.
注意第一個數是測試數據的組數，多組測試數據一起測。。
【輸出文件】
Write to the output file the word "Divisible" if given sequence of integers is divisible by K or "Not divisible" if it's not.
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.
注意：輸出每組結果之間有空格，最後一行無空格，格式不對不能AC，我就是因為格式不對調了一上午。。。。
【輸入樣例】
2
4 7
17 5 -21 15
4 5
17 5 -21 15
【輸出樣例】
Divisible
Not divisible
【問題分析】
看到題目第一個反映就是枚舉中間添的運算符，算出值在MOD K如果有一個值MOD K=0則輸出「Divisible」。
時間複雜度是O（2N-1）。
但是題目給出的數據量很大，這樣做效率太低了。
因為題目涉及MOD運算，要想簡化問題就需要知道一些基本的MOD運算性質：
A*B mod C=(A mod C*B mod C) mod C
(A+B) mod C=(A mod C+B mod C) mod C
有了這個性質，我們就可以把累加後求余轉化成求余後累加（我們把減法看作加負數以後分析只說加法）再求余。這樣我們的讀入數據就控制在了1-K到K-1的範圍內了。
我們要判斷的就是
所有結果的累加和 MOD K 是否為0。簡記為:
（A+B）mod K=0 or (A+B) mod K0
如果我們按數的個數劃分階段，前N-1個數的運算結果 MOD K看做A，第N個數看作B就OK了。
於是我們想到了這樣的狀態：opt[i,j]表示前i個數是否可以得到餘數為J的結果。
那麼狀態轉移方程就是
opt[i,(j-a[i] mod k )mod k]=opt[i-1,j] (opt[i-1,j]=true);
opt[i,(j+a[i] mod k) mod k]=opt[i-1,j] (opt[i-1,j]=true);
如果opt[n,0]=true就輸出『Divisible'
注意上面
【源代碼】
program P2042;
const
maxk=110;
maxn=10010;
var
a:array[0..maxn] of longint;
opt:array[1..2,-maxk..maxk] of boolean;
n,k,tim,ii:longint;
vis:array[0..maxn] of boolean;
procedure init;
var
i:longint;
begin
read(n,k);
for i:=1 to n do
read(a[i]);
end;
procedure main;
var
i,j,p1,p2,p3:longint;
begin
fillchar(opt,sizeof(opt),false);
fillchar(vis,sizeof(vis),false);
for i:=1 to n do
if a[i] mod k=0 then vis[i]:=true;
for i:=1 to n do
a[i]:=a[i] mod k;
opt[1,a[1]]:=true;
p1:=1;
p2:=2;
for i:=2 to n do
if not vis[i] then
begin
fillchar(opt[p2],sizeof(opt[p2]),false);
for j:=1-k to k-1 do
if opt[p1,j] then
begin
opt[p2,(j-a[i]) mod k]:=true;
opt[p2,(j+a[i]) mod k]:=true;
end;
p3:=p1;
p1:=p2;
p2:=p3;
end;
if opt[p1,0] then writeln('Divisible')
else writeln('Not divisible');
end;
begin
read(tim);
for ii:=1 to tim do
begin
if ii>1 then
writeln;
init;
main;
end;
end.
3.多維狀態和動態規劃的優化
一般多維動態規劃的時，空間複雜度較高，所以我們要想辦法將其優化，我就把多維動態規劃和動態規劃的優化放到一起了……
多維動態規劃以三，四維最為常見，在多的也沒有太大的研究價值，其實多維動態規劃大多也就是上面的一維，和二維的加一些條件，或是在多進程動態規劃中要用到。當然除了這些特點外，狀態的表示也有一些共性。
三維：狀態opt[i,j,k]一般可表示下面的含義：
（1）二維狀態的基礎上加了某個條件，或其中一維變成兩個。
比如opt[L,i]表示起點為I，長度為L的序列的最優值。opt[L,i,j]就可表示起點是i和起點是j，長度是L的兩個序列的最優值。
（2）I，J，K組合表示一個正方形（（i,j）點為一角，邊長為K）。
（3）I，J，K組合表示一個等邊三角形（（i,j）點為一角，邊長為K）。
四維：除了二維和三維加條件外，還可以用i,j,k,t組合來描述一個矩形，
（i,j）點和（k,t）點是兩個對頂點。
四維以上的一般都是前幾維加了條件了，這裡就不多說了。
動態規劃的優化：
動態規劃的優化往往需要較強的數學功底。
常見空間優化：
滾動數組，滾動數組在前面也提到過，其實很簡單，如果一個狀態的決策的步長為N就只保留以求出的最後N（一般N=1）個階段的狀態，因為當前狀態只和後N個階段中的狀態有關，再以前的已經利用過了，沒用了就可以替換掉了。具體實現是最好只讓下標滾動（這樣更省時間）。
X：=K1，K1：=K2，K2；=K3，K3：=X這樣就實現了一個N=3的下標的滾動，在滾動完如果狀態是涉及累加，累乘類的操作要注意將當前要求的狀態初始化。
常見時間優化：利用一些數據結構（堆，並查集，HASH）降低查找複雜度。
時間空間雙重優化：改變狀態的表示法，降低狀態維數。
具體的多維動態規劃和動態規劃的優化，我們從題目裡體會吧！
3.1矩陣問題
先看一道題
例題27 蓋房子 來源：VIJOS P1057
【問題描述】
永恆の靈魂最近得到了面積為n*m的一大塊土地（高興ING^_^），他想在這塊土地上建造一所房子，這個房子必須是正方形的。
但是，這塊土地並非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。這些瑕疵十分噁心，以至於根本不能在上面蓋一磚一瓦。
他希望找到一塊最大的正方形無瑕疵土地來蓋房子。
不過，這並不是什麼難題，永恆の靈魂在10分鐘內就輕鬆解決了這個問題。現在，您也來試試吧。
【輸入文件】
輸入文件第一行為兩個整數n,m（1<=n,m<=1000），接下來n行，每行m個數字，用空格隔開。0表示該塊土地有瑕疵，1表示該塊土地完好。
【輸出文件】
一個整數，最大正方形的邊長。
【輸入樣例】
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
【輸出樣例】
2
【問題分析】
題目中說要求一個最大的符合條件的正方形，所以就想到判斷所有的正方形是否合法。
這個題目直觀的狀態表示法是opt[i,j,k]基類型是boolean，判斷以（i,j）點為左上角（其實任意一個角都可以，依據個人習慣）,長度為K的正方形是否合理，再找到一個K值最大的合法狀態就可以了（用true表示合理，false表示不合理）。其實這就是遞推，（決策唯一）。
遞推式：
opt[i,j,k]=opt[i+1,j+1,k-1] and opt[i+1,j,k-1] and opt[i,j+1,k-1] and (a[i,j]=1)
時間複雜度：
狀態數O（N3）*轉移代價O（1）=總複雜度O（N3）
空間複雜度：
O（N3）
由於空間複雜度和時間複雜度都太高，不能AC，我們就的再想想怎麼優化？
顯然何以用滾動數組優化空間，但是時間複雜度仍然是O（N3）。這就需要我們找另外一種簡單的狀態表示法來解了。
仔細分析這個題目，其實我們沒必要知道正方形的所有長度，只要知道以一個點為左上角的正方形的最大合理長度就可以了。
如果這個左上角是0那麼它的最大合理長度自然就是0（不可能合理）。
如果這個左上角是1呢？
回顧上面的遞推式，我們考慮的是以它的右面，下面，右下這個三個方向的正方形是否合理，所以我們還是要考慮這三個方向。具體怎麼考慮呢？
如果這三個方向合理的最大邊長中一個最小的是X，那麼它的最大合理邊長就是X+1。為什麼呢？
看個例子：
0 1 1 1 1 1
1 1 1 1 1 1
0 1 0 1 1 0
1 1 0 1 1 1
上例中紅色的正方形，以（1,3）點為左上角，以（1，4），（2，3），（2，4）這三個點的最大合理邊長分別是2，1，2。其中最小的是以（2，3）為左上角的正方形，最大合理邊長是1。因為三個方向的最大合理邊長大於等於1，所以三個方向上邊長為1的正方形是合理的，即上面低推式中:
opt[1,3,2]=opt[1,4,1] and opt[2,3,1] and opt[2,4,1] and (a[1,3]=1) = true 成立
這樣就把一個低推判定性問題轉化成最優化問題從而節省空間和時間。
具體實現：
設計一個狀態opt[i,j]表示以（i,j）為左上角的正方形的最大合理邊長。
狀態轉移方程：
min{opt[i+1,j],opt[i,j+1],opt[i+1,j+1]}+1 (a[i,j]=1)
opt[i,j]=0 (a[i,j]=0)
時間複雜度：狀態數O（N2）*轉移代價O（1）=總代價O（N2）
空間複雜度：O（N2）
【源代碼】
program P1057;
const
maxn=1010;
var
opt,a:array[0..maxn,0..maxn] of longint;
n,m,ans:longint;
procedure init;
var
i,j:longint;
begin
read(n,m);
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),0);
for i:=n downto 1 do
for j:=m downto 1 do
if a[i,j]0 then
begin
opt[i,j]:=opt[i+1,j];
if opt[i,j+1]<opt[i,j] then
opt[i,j]:=opt[i,j+1];
if opt[i+1,j+1]ans then ans:=opt[i,j];
writeln(ans);
end;
begin
init;
main;
end.
3.2多進程動態規劃
從字面上就可以看出，所謂多進程就是在原文題的基礎上要求將這個問題重複多次的總和最大。
具體怎麼做看個例題吧。
例題28 方格取數 (fgqs.pas/c/cpp) 來源：NOIP2000(提高組)
【問題描述】
設有N*N的方格圖(N<=10,我們將其中的某些方格中填入正整數,而其他的方格中則放入數字0。如下圖所示（見樣例）：
某人從圖的左上角的A 點出發，可以向下行走，也可以向右走，直到到達右下角的B點。在走過的路上，他可以取走方格中的數（取走後的方格中將變為數字0）。
此人從A點到B 點共走兩次，試找出2條這樣的路徑，使得取得的數之和為最大。
【輸入文件】
輸入的第一行為一個整數N（表示N*N的方格圖），接下來的每行有三個整數，前兩個表示位置，第三個數為該位置上所放的數。一行單獨的0表示輸入結束。
【輸出文件】
只需輸出一個整數，表示2條路徑上取得的最大的和。
【輸入樣例】
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
【輸出樣例】
67
【問題分析】
這是一道很經典的多進程動態規劃題，如果只取一次，它的模型就是我們前面講的街道問題了，很簡單就可以實現。現在要求取兩次，怎麼辦呢？
一個自然的想法是：將前面的取過的數全賦成0，然後在取一次，感覺挺對的，樣例也過了。
但這樣做是錯的，第一次取的顯然是最大值，但第二次取的未必次大，所以也許兩條非最大的路，也許比一條最大一條小一點的路更優。
看個例子：
0 0 2 0 3 0 0 0 2 0 3 0
0 0 2 0 0 0 0 0 2 0 0 0
0 0 2 0 2 0 0 0 2 0 2 0
0 0 0 0 2 0 0 0 0 0 2 0
0 0 0 0 2 0 0 0 0 0 2 0
0 0 2 0 2 0 0 0 2 0 2 0
圖1 圖2
如上圖，圖1是按找上訴思路求得的解。圖中紅色路線是第一求得的最大值，顯然圖1紅色和紫色兩條路徑不如圖2藍色和綠色兩條路徑大。
既然這樣做不行，我們還得回到動態規劃的本質來看代問題，我們在想想這個問題的狀態，對於走一次，走到矩陣的任意一個位置就是一個狀態，而要是走兩次，顯然走到矩陣的某個位置只是一個狀態的一部分，不能完整的描述整個狀態。那另一部分顯然就是第二次走到的位置了。如果我們把這兩部分合起來就是一個完整的狀態了。
於是，設計一個狀態opt[i1,j1,i2,j2]表示兩條路分別走到（i1,j1）點和（i2,j2）點時取到的最大值。顯然決策有4中（乘法原理一個點兩種*另一個點的兩中）
即（上，上）（上，左）（左，上）（左，左）上和左表示從哪個方向走到該點，當然要注意走到同行，同列，同點時的情況（因為要求路徑不重複）。
狀態轉移方程：
max(opt[i1-1,j1,i2-1,j2],opt[i1,j1-1,i2-1,j2])+a[i1,j1]+a[i2,j2] (1<=i1=i2<=n,1<=j1<=j2<=n)
max(opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2,j2-1])
(1<=j1=j2<=n,1<=i1<=i2<=n)
opt[i,j]= max(opt[i1-1,j1,i2-1,j2],opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2-1,j2],
opt[i1,j1-1,i2,j2-2])+a[i1,j1]+a[i2,j2] (1<=i1,j1<=i2,j2<=n)
max(opt[i1-1,j1,i2-1,j2],opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2-1,j2],
opt[i1,j1-1,i2,j2-2])+a[i1,j1] (1<=i1=i2<=n,1<=j1=j2y then max:=x;
end;
procedure main;
var
i1,i2,j1,j2:longint;
begin
for i1:=1 to n do
for j1:=1 to n do
for i2:=i1 to n do
for j2:=1 to j1 do
if (i1=i2) and (j1=j2) then
opt[i1,j1,i2,j2]:=opt[i1-1,j1,i2,j2-1]+a[i1,j1]
else if (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]
else if (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]
else begin
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,j1,i2,j2],opt[i1,j1-1,i2,j2-1]);
opt[i1,j1,i2,j2]:=max(opt[i1,j1,i2,j2],opt[i1,j1-1,i2-1,j2]);
inc(opt[i1,j1,i2,j2],a[i1,j1]+a[i2,j2]);
end;
end;
procedure print;
begin
writeln(opt[n,n,n,n]);
close(output);
end;
begin
init;
main;
print;
end.
如果這個題的數據範圍在大點就得優化了，怎麼優化這個程序呢？
上面說過對於時間空間都大的時候，首先想到的就是尋找特點，改變狀態的表示法，減少狀態的維數。
仔細分析我們發現，處於同行，同列的狀態，等價於另外一個點在對角線上的狀態。而這條對角線正是此題的階段。因為在狀態轉移的時候後面的哪個點總是從固定的一個方向轉移來的。也就是說我們只要對角先上的狀態就可以省掉那些同行同列的狀態了。
做過N皇的同學一定知道怎麼表示右上到左下的這幾條對角線，不知道的同學也沒關係,對於一個點（i,j）他對角右上角的點就是（i-1，j+1）所以可以看出這些點的和是定值，且值從2到N*2。
這樣用三個變量就可以表示這兩個點了，於是設計狀態opt[k,i1,i2]表示處於階段K時走到i1,i2的兩條路徑所取得的數的最大和。
用上面的思維不難想出動態轉移方程：
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](1<=i1,i2<=n,2<=k<=n*2,i1i2)
otp[k,i1,i2]=opt[k-1,i1-1,i2]+a[i1,k-i1](1<=i1,i2<=n,2<=ky then max:=x;
end;
procedure main;
var
k,i1,i2,j1,j2,mid:longint;
begin
for k:=2 to n*2 do
begin
for i1:=1 to n do
if (k-i1>0) and (k-i10) and (k-i2=1）子樹的最優解，決策會很多。以至於我們沒發寫出準確的狀態轉移方程。這就是我們為什麼要把多叉數轉化成二叉數的原因。（當然，如果問題是求所有子樹的和，就沒必要轉化了，如URAL P1039 沒有上司的舞會）。
如果把多叉樹或森林轉化成二叉樹要注意，左兒子和根結點是父子關係，而右兒子在原問題中和跟結點是兄弟關係。（這個數據結構掌握紮實的應該能明白，不理解的就去看數據結構方面的知識）。
用鄰接矩陣存多叉樹，轉化成二叉樹的部分代碼（可能有語法錯誤）
G: 存圖，F[i] 表示第i個結點的兒子應該插入的位置
W：結點的值 BT：二叉樹
Procedure creat_tree(T:tree);
Var
i:longint;
Begin
for i:=1 to n do
Begin
for j:=1 to n do
If g[i,j] then
Begin
If F[i]=0 then
BT[i].L:=j
Else BT[F[i]].r:=j;
F[i]:=j;
End;
End;
End;
下面同過例題看一下樹型動態規劃的具體實現：
例題29 加分二叉樹 (binary.pas/c/cpp) 來源：NOIP2003（提高組）
【問題描述】
設一個n個節點的二叉樹tree的中序遍歷為（l,2,3,…,n），其中數字1,2,3,…,n為節點編號。每個節點都有一個分數（均為正整數），記第i個節點的分數為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下：
subtree的左子樹的加分× subtree的右子樹的加分＋subtree的根的分數
若某個子樹為空，規定其加分為1，葉子的加分就是葉節點本身的分數。不考慮它的空
子樹。
試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。要求輸出；
（1）tree的最高加分
（2）tree的前序遍歷
【輸入格式】
第1行：一個整數n（n＜30），為節點個數。
第2行：n個用空格隔開的整數，為每個節點的分數（分數＜100）。
【輸出格式】
第1行：一個整數，為最高加分（結果不會超過4,000,000,000）。
第2行：n個用空格隔開的整數，為該樹的前序遍歷。
【輸入樣例】
5
5 7 1 2 10
【輸出樣例】
145
3 1 2 4 5
【問題分析】
根據題目描述就可以看出是典型的樹型動態規劃，而且題目中已經給出了加分的求法：
subtree的左子樹的加分× subtree的右子樹的加分＋subtree的根的分數
這估計是最簡單的題目了。
但是有一點需要注意：我們應該怎麼建樹？
其實這個題不用建樹，這就需要我們對數據結構掌握的很紮實。
題目中說這個樹的中序遍歷是1，2，3……N，我們要求的是樹的先序，這樣馬上就想到怎樣用中序和先序確定一棵樹。
枚舉樹根i那麼1，2……i-1就是它的左子樹中的結點，i+1……N就是它右子樹中的結點。這樣一顆樹按這樣的低歸定義就構造出來了，（當然我們只要這個過程並不需要存儲這棵樹）。在構造過程中順便求出加分來，在一個序列裡不同的元素做根顯然加分不同，我們只要記錄一個最大的就可以了。
具體實現方法：
設計狀態opt[L,r]表示以L為起點，以r為終點的結點所組成的樹的最高加分，階段就是樹的層數。決策就是在這些結點中找一個結點做根使樹的加分最大，狀態轉移方程：
1 (L>r)
opt[L,r] = a[L] (L=r)
max{opt[L,i-1]*opt[i+1,r]+a[i]} (L<r,L<=ir then
begin
opt[L,r]:=1;
path[L,r]:=0;
end
else if L=r then
begin
opt[L,r]:=a[L];
path[L,r]:=L;
end
else begin
for i:=L to r do
begin
x:=TreeDp(L,i-1)*TreeDp(i+1,r)+a[i];
if x>opt[L,r] then
begin
opt[L,r]:=x;
path[L,r]:=i;
end;
end;
end;
end;
TreeDp:=opt[L,r];
end;
procedure print(L,r:longint);
begin
if path[L,r]>0 then
begin
write(path[L,r],' ');
print(L,path[L,r]-1);
print(path[L,r]+1,r);
end;
end;
begin
init;
writeln(TreeDp(1,n));
print(1,n);
close(output);
end.
例題30 A Binary Apple Tree 蘋果二叉樹 來源：URAL P1018
【問題描述】
設想蘋果樹很像二叉樹，每一枝都是生出兩個分支。我們用自然數來數這些枝和根那麼必須區分不同的枝（結點），假定樹根編號都是定為1，並且所用的自然數為1到N。N為所有根和枝的總數。例如下圖的N為5，它是有4條枝的樹。
2 5
\ /
3 4
\ /
1
當一棵樹太多枝條時，採摘蘋果是不方便的，這就是為什麼有些枝要剪掉的原因。現在我們關心的是，剪枝時，如何令到損失的蘋果最少。給定蘋果樹上每條枝的蘋果數目，及必須保留的樹枝的數目。你的任務是計算剪枝後，能保留多少蘋果。
【輸入文件】
首行為N，Q (1 <= Q <= N, 1 < N <= 100), N為一棵樹上的根和枝的編號總數，Q為要保留的樹枝的數目。以下N-1行為每條樹枝的描述，用3個空格隔開的整數表示，前2個數為樹枝兩端的編號,第三個數為該枝上的蘋果數。假設每條枝上的蘋果數不超過3000個。
【輸出文件】
輸出能保留的蘋果數。（剪枝時，千萬不要連根拔起哦）
【輸入樣例】
5 2
1 3 1
1 4 10
2 3 20
3 5 20
【輸出樣例】
21
【問題分析】
和上一道題一樣，題目描述就很明確的說是關於樹的題目，在加上是求最優值，和上一道題不同的是，這個題目邊有值，並非點有值，還有一個不同點就是這個題需要建樹。
建樹是要注意，給每個結點增加一個域：SUM用來存以它為根的樹中的邊的數目。
其實樹型動態規劃是最好分析的，因為樹這種數據結構本來就符合遞歸定義，這樣的話子問題很好找，顯然這個問題的子問題就是一棵樹要保留M個枝分三種情況：
剪掉左子樹：讓右子樹保留M-1個枝可保留最多的蘋果數+連接右子樹的枝上的蘋果數
剪掉右子樹：讓左子樹保留M-1個枝可保留最多的蘋果數+連接左子樹的枝上的蘋果數
都不剪掉： 讓左子樹保留i個枝，讓右子樹保留M-2-i個枝可保留最多的蘋果數+連接右子樹的枝上的蘋果數+連接左子樹的枝上的蘋果數
顯然邊界條件就是如果要保留的枝子數比當前的子樹的枝多，或著一個樹要保留0個枝子，則結果就是0。
應為一顆樹中根接點是對子樹的完美總結，所以滿足最優化原理。
沒次求解只和子樹有關所以也滿足無後效性，可見用動態規劃做是正確的。
設計一個狀態opt[num,i]表示要讓結點編號為i的樹保留num個枝可得到的最優解。
狀態轉移方程：
opt[num,i]=max{opt[num-1,BT[i].L]+T[i,BT[i].L],opt[num-1,BT[i].r]+T[i,BT[i].r],opt[k,BT[i].L]+opt[num-2-k,BT[i].r]+T[i,BT[i].L]+T[i,BT[i].r]}
(0<=k0) and (not vis[j]) then
begin
creat_tree(j);
BT[i].L:=Bt[i].r;
Bt[i].r:=j;
inc(Bt[i].sum,BT[j].sum+1);
end;
end;
Function max(x,y:longint):longint;
begin
max:=y;
if x>y then max:=x;
end;
Function F(num,i:longint):longint;
var
k:longint;
begin
if opt[num,i]BT[i].sum) or (num=0) then opt[num,i]:=0
else begin
opt[num,i]:=F(num-1,BT[i].L)+T[i,BT[i].L];
opt[num,i]:=max(opt[num,i],F(num-1,BT[i].r)+T[i,BT[i].r]);
for k:=0 to num-2 do
opt[num,i]:=max(opt[num,i],F(k,BT[i].L)+F(num-2-k,BT[i].r)
+T[i,BT[i].L]+T[i,BT[i].r]);
end;
end;
F:=opt[num,i];
end;
begin
init;
creat_tree(1);
fillchar(opt,sizeof(opt),200);
writeln(F(m,1));
close(output);
end.
例題31 選課 來源：VIJOS P1180
【問題描述】
學校實行學分制。每門的必修課都有固定的學分，同時還必須獲得相應的選修課程學分。學校開設了N（N<300）門的選修課程，每個學生可選課程的數量M是給定的。學生選修了這M門課並考核通過就能獲得相應的學分。
在選修課程中，有些課程可以直接選修，有些課程需要一定的基礎知識，必須在選了其它的一些課程的基礎上才能選修。例如《Frontpage》必須在選修了《Windows操作基礎》之後才能選修。我們稱《Windows操作基礎》是《Frontpage》的先修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。每門課都有一個課號，依次為1，2，3，…。例如:
表中1是2的先修課，2是3、4的先修課。如果要選3，那麼1和2都一定已被選修過。 你的任務是為自己確定一個選課方案，使得你能得到的學分最多，並且必須滿足先修課優先的原則。假定課程之間不存在時間上的衝突。
【輸入文件】
輸入文件的第一行包括兩個整數N、M（中間用一個空格隔開）其中1≦N≦300,1≦M≦N。
以下N行每行代表一門課。課號依次為1，2，…，N。每行有兩個數（用一個空格隔開），第一個數為這門課先修課的課號（若不存在先修課則該項為0），第二個數為這門課的學分。學分是不超過10的正整數。
【輸出文件】
輸出文件只有一個數,實際所選課程的學分總數。
【輸入樣例】
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
【輸出樣例】
13
【問題分析】
事先說明題目描述有個漏洞，應該是二個以上的課程可能有同一個先修課。
換句話講，一個課程可能是多個課程的先修課，可是一個課最多只有一個先修課。這樣的描述好像和我們以前學過的一種數據結構的描述一樣。
你想對了，就是樹。
因為是建立在樹這種數據結構上的最優化問題，我們自然想到了樹型動態規劃。想到樹型動態規劃，那麼第一步就是想這課樹是否是二叉樹，如果不是，是否需要轉化呢？
顯然這個問題不是二叉樹，有應為問題是在多個課程中選M個，也就是說是樹中一棵或多棵子樹的最優解，這樣問題就需要轉化成二叉樹了。注意題目中說一個課程沒有先修課是0，也就是說這課樹的根是0。
把數據結構確定了以後就要想動態規劃的三要素了。
樹型動態規劃階段的具有共性：樹的層數，
狀態是結點，但是只描述結點顯然不夠，需要在加一個參數。於是我們想到設計一個狀態opt[i,j]表示以i為跟的樹，選j個課程可獲得的最優解。
因為樹是以0為根的而0又必須要選所以問題的解不是opt[0,m]而是opt[0,m+1]。
決策是什麼呢？
對於二叉樹我在設計決策時習慣分類討論這樣結構清晰。
這棵樹只有左子樹：
要選左子樹中的課程，那麼根結點一定要選，所以決策就是在左子樹中選j-1個課程，在加上選根結點可獲得的分數。
這棵樹只有右子樹：
因為右子樹和根在原問題中是兄弟關係，所以選右子樹中的課程未必要選根，這樣決策就有兩條：（1）在右子樹中選j個的最優值。（2）在右子樹中選j-1個的最優值加上選根結點可獲得的分數。
都有：
這種情況的決策很容易想到，從左子樹中選k-1個，從右子樹中選j-k個的最優值加上根結點可獲得的分數。
但要注意，當K=1也就是左子樹選0個時，根結點可以不選，右子樹可以選j個而不是j-1個；當然根結點也可以選，選了根結點右子樹就得選j-1個了。
針對不同情況寫出狀態轉移方程：
max(opt[t[i].L,j-1]+t[i].data) （只有左子樹）
opt[i,j] = max(opt[t[i].r,j-1]+t[i].data, opt[t[i].r,j]) （只有右子樹）
max(opt[t[i].L,k-1]+opt[t[i].r,j-k]+t[i].data,opt[t[i].r,j])（都有）
(1<=ky then max:=x;
end;
function TreeDp(i,j:longint):longint;
var
k:longint;
begin
if opt[i,j]<0 then
begin
if (T[i].L<0) and (T[i].r<0) then
begin
if j1 then opt[i,j]:=0
else opt[i,j]:=T[i].data;
end
else if (T[i].L>=0) and (T[i].r<0) then
opt[i,j]:=max(opt[i,j],TreeDp(T[i].L,j-1)+T[i].data)
else if (T[i].L=0) then
begin
opt[i,j]:=max(opt[i,j],TreeDp(T[i].r,j));
opt[i,j]:=max(opt[i,j],TreeDp(T[i].r,j-1)+T[i].data);
end
else begin
opt[i,j]:=max(opt[i,j],TreeDp(T[i].r,j));
for k:=1 to j do
opt[i,j]:=max(opt[i,j],TreeDp(T[i].L,k-1)+
TreeDp(T[i].r,j-k)+T[i].data);
end;
end;
TreeDp:=opt[i,j];
end;
begin
init;
writeln(TreeDp(0,m+1));
end.
引言：本人在做過一些題目後對DP有些感想，就寫了這個總結：
第一節 動態規劃基本概念
一，動態規劃三要素：階段，狀態，決策。
他們的概唸到處都是，我就不多說了，我只說說我對他們的理解：
如果把動態規劃的求解過程看成一個工廠的生產線，階段就是生產某個商品的不同的環節，狀態就是工件當前的形態，決策就是對工件的操作。顯然不同階段是對產品的一個前面各個狀態的小結，有一個個的小結構成了最終的整個生產線。每個狀態間又有關聯（下一個狀態是由上一個狀態做了某個決策後產生的）。
下面舉個例子：
要生產一批雪糕，在這個過程中要分好多環節：購買牛奶，對牛奶提純處理，放入工廠加工，加工後的商品要包裝，包裝後就去銷售……，這樣沒個環節就可以看做是一個階段；產品在不同的時候有不同的狀態，剛開始時只是白白的牛奶，進入生產後做成了各種造型，從冷凍庫拿出來後就變成雪糕（由液態變成固態=_=||）。每個形態就是一個狀態，那從液態變成固態經過了冰凍這一操作，這個操作就是一個決策。
一個狀態經過一個決策變成了另外一個狀態，這個過程就是狀態轉移，用來描述狀態轉移的方程就是狀態轉移方程。
經過這個例子相信大家對動態規劃有所瞭解了吧。
下面在說說我對動態規劃的另外一個理解：
用圖論知識理解動態規劃：把動態規劃中的狀態抽象成一個點，在有直接關聯的狀態間連一條有向邊，狀態轉移的代價就是邊上的權。這樣就形成了一個有向無環圖AOE網（為什麼無環呢？往下看）。對這個圖進行拓撲排序，刪除一個邊後同時出現入度為0的狀態在同一階段。這樣對圖求最優路徑就是動態規劃問題的求解。
二，動態規劃的適用範圍
動態規劃用於解決多階段決策最優化問題，但是不是所有的最優化問題都可以用動態規劃解答呢？
一般在題目中出現求最優解的問題就要考慮動態規劃了，但是否可以用還要滿足兩個條件：
最優子結構（最優化原理）
無後效性
最優化原理在下面的最短路徑問題中有詳細的解答；
什麼是無後效性呢？
就是說在狀態i求解時用到狀態j而狀態j就解有用到狀態k…..狀態N。
而求狀態N時有用到了狀態i這樣求解狀態的過程形成了環就沒法用動態規劃解答了，這也是上面用圖論理解動態規劃中形成的圖無環的原因。
也就是說當前狀態是前面狀態的完美總結，現在與過去無關。。。
當然，有是換一個劃分狀態或階段的方法就滿足無後效性了，這樣的問題仍然可以用動態規劃解。
三，動態規劃解決問題的一般思路。
拿到多階段決策最優化問題後，第一步要判斷這個問題是否可以用動態規劃解決，如果不能就要考慮搜索或貪心了。當卻定問題可以用動態規劃後，就要用下面介紹的方法解決問題了：
（1）模型匹配法：
最先考慮的就是這個方法了。挖掘問題的本質，如果發現問題是自己熟悉的某個基本的模型，就直接套用，但要小心其中的一些小的變動，現在考題辦都是基本模型的變形套用時要小心條件，三思而後行。這些基本模型在先面的分類中將一一介紹。
（2）三要素法
仔細分析問題嘗試著確定動態規劃的三要素，不同問題的卻定方向不同：
先確定階段的問題：數塔問題，和走路問題（詳見解題報告）
先確定狀態的問題：大多數都是先確定狀態的。
先確定決策的問題：背包問題。（詳見解題報告）
一般都是先從比較明顯的地方入手，至於怎麼知道哪個明顯就是經驗問題了，多做題就會發現。
（3）尋找規律法：
這個方法很簡單，耐心推幾組數據後，看他們的規律，總結規律間的共性，有點貪心的意思。
（4）邊界條件法
找到問題的邊界條件，然後考慮邊界條件與它的領接狀態之間的關係。這個方法也很起效。
（5）放寬約束和增加約束
這個思想是在陳啟鋒的論文裡看到的，具體內容就是給問題增加一些條件或刪除一些條件使問題變的清晰。
第二節 動態規劃分類討論
這裡用狀態維數對動態規劃進行了分類：
1.狀態是一維的
1．1下降/非降子序列問題：
問題描述： {挖掘題目的本質，一但抽象成這樣的描述就可以用這個方法解}
在一個無序的序列a1,a2,a3,a4…an裡，找到一個最長的序列滿足：ai<=aj<=ak…<=am,且i<j<k…aj>ak…>am,且i>j>k…>m.（最長下降子序列）。
問題分析：
如果前i-1個數中用到ak (ak>ai或akai(或aj<=ai)，opt[j]+1就是opt[i]的值；用方程表示為：{我習慣了這種寫法，但不是狀態轉移方程的標準寫法 }
opt[i]=max(opt[j])+1 (0<=j<i 且aj<=ai) {最長非降子序列}
opt[i]=max(opt[j])+1 (0<=jai) {最長下降子序列}
實現求解的部分代碼：
opt[0]:=maxsize；{maxsize 為maxlongint或-maxlongint}
for i:=1 to n do
for j:=0 to i-1 do
if ( a[j]>a[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
ans:=-maxlongint;
for i:=1 to n do
if opt[i]>ans then ans:=opt[i]; {ans 為最終解}
複雜度：從上面的實現不難看出時間複雜度為O（N2），空間複雜度O（N）；
例題1 攔截導彈 (missile.pas/c/cpp) 來源：NOIP1999(提高組) 第一題
【問題描述】
某國為了防禦敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發砲彈能夠到達任意的高度，但是以後每一發砲彈都不能高於前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由於該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。
輸入導彈依次飛來的高度（雷達給出的高度數據是不大於30000的正整數），計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。
【輸入文件】missile.in
單獨一行列出導彈依次飛來的高度。
【輸出文件】missile.out
兩行，分別是最多能攔截的導彈數，要攔截所有導彈最少要配備的系統數
【輸入樣例】
389 207 155 300 299 170 158 65
【輸出樣例】
6
2
【問題分析】
有經驗的選手不難看出這是一個求最長非升子序列問題，顯然標準算法是動態規劃。
以導彈依次飛來的順序為階段，設計狀態opt[i]表示前i個導彈中攔截了導彈i可以攔截最多能攔截到的導彈的個數。
狀態轉移方程：
opt[i]=max(opt[j])+1 (h[i]>=h[j],0=<j=a[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
anslen:=0;
for i:=1 to n do
if opt[i]>anslen then
anslen:=opt[i];
fillchar(opt,sizeof(opt),0);
a[0]:=-maxlongint;
for i:=1 to n do
for j:=i-1 downto 0 do
if (a[j]opt[i]) then
opt[i]:=opt[j]+1;
anstime:=0;
for i:=1 to n do
if opt[i]>anstime then
anstime:=opt[i];
end;
procedure print;
begin
writeln(anslen);
writeln(anstime);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
例題二 合唱隊形 (chorus.pas/c/cpp) 來源：NOIP2004(提高組) 第一題
N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學排成合唱隊形。
合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1，2…，K，他們的身高分別為T1，T2，…，TK， 則他們的身高滿足T1<...Ti+1>…>TK(1<=i<=K)。
你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。
【輸入文件】
輸入文件chorus.in的第一行是一個整數N(2<=N<=100)，表示同學的總數。第一行有n個整數，用空格分隔，第i個整數Ti(130<=Ti<=230)是第i位同學的身高(釐米)。
【輸出文件】
輸出文件chorus.out包括一行，這一行只包含一個整數，就是最少需要幾位同學出列。
【樣例輸入】
8
186 186 150 200 160 130 197 220
【樣例輸出】
4
【數據規模】
對於50％的數據，保證有n<=20；
對於全部的數據，保證有n<=100。
【問題分析】
出列人數最少，也就是說留的人最多，也就是序列最長。
這樣分析就是典型的最長下降子序列問題。只要枚舉每一個人站中間時可以的到的最優解。顯然它就等於，包括他在內向左求最長上升子序列，向右求最長下降子序列。
我們看一下複雜度：
計算最長下降子序列的複雜度是O（N2），一共求N次，總複雜度是O（N3）。這樣的複雜度對於這個題的數據範圍來說是可以AC的。但有沒有更好的方法呢？
其實最長子序列只要一次就可以了。因為最長下降（上升）子序列不受中間人的影響。
只要用OPT1求一次最長上升子序列，OPT2求一次最長下降子序列。這樣答案就是N-max(opt1[i]+opt2[i]-1).
複雜度由O（N3）降到了O（N2）。
【源代碼】
program chorus;
const
fin='chorus.in';
fout='chorus.out';
maxn=200;
var
opt1,opt2,a:array[0..maxn] of longint;
n,ans:longint;
procedure init;
var
i:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
readln(n);
for i:=1 to n do
read(a[i]);
end;
procedure main;
var
i,j:longint;
begin
a[0]:=-maxlongint;
for i:=1 to n do
for j:=i-1 downto 0 do
if (a[j]opt1[i]) then
opt1[i]:=opt1[j]+1;
a[n+1]:=-maxlongint;
for i:=n downto 1 do
for j:=i+1 to n+1 do
if (a[j]opt2[i]) then
opt2[i]:=opt2[j]+1;
ans:=0;
for i:=1 to n do
if opt1[i]+opt2[i]>ans then
ans:=opt1[i]+opt2[i];
end;
procedure print;
begin
writeln(n-ans+1);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
例題3 Buy Low Buy Lower (buylow.pas/c/cpp) 來源: USACO 4-3-1
【問題描述】
「逢低吸納」是炒股的一條成功秘訣。如果你想成為一個成功的投資者，就要遵守這條秘訣:
"逢低吸納,越低越買"
這句話的意思是：每次你購買股票時的股價一定要比你上次購買時的股價低.按照這個規則購買股票的次數越多越好，看看你最多能按這個規則買幾次。
給定連續的N天中每天的股價。你可以在任何一天購買一次股票，但是購買時的股價一定要比你上次購買時的股價低。寫一個程序，求出最多能買幾次股票。
以下面這個表為例, 某幾天的股價是:
天數 1 2 3 4 5 6 7 8 9 10 11 12
股價 68 69 54 64 68 64 70 67 78 62 98 87
這個例子中, 聰明的投資者(按上面的定義)，如果每次買股票時的股價都比上一次買時低，那麼他最多能買4次股票。一種買法如下(可能有其他的買法):
天數 2 5 6 10
股價 69 68 64 62
【輸入文件】buylow.in
第1行: N (1 <= N =a[j],0=<j<i) {a[i]存第i天股價}
最大的opt[i]就是最終的解。
第二問呢，稍麻煩一點。
從問題的邊界出發考慮問題，當第一問求得一個最優解opt[i]=X時，
在1到N中如果還有另外一個opt[j]=x那麼選取J的這個方案肯定是成立的。
是不是統計所有的opt[j]=x 的個數就是解了呢？
顯然沒那麼簡單，因為選取Ｊ這天的股票構成的方案不見得＝１，看下面一個例子：
５ 6 4 3 １ 2
方案一：５４３１
方案二：５４３２
方案三：６４３１
方案四：６４３２
x=4
也就是所雖然opt[5]=X 和opt[6]=X但個數隻有兩個，而實際上應該有四個方案，但在仔細觀察發現，構成opt[5]=x 的這個方案中 opt[j]=x-1的方案數有兩個,opt[j]=x-2的有一個，opt[j]=x-3 的有一個……
顯然這是滿足低歸定義的設計函數F（i）表示前I張中用到第i張股票的方案數。
遞推式：
1 (i=0)
F(i)=
Sum(F(j)) (0<=ja[i],opt[j]=opt[i]-1) {sum 代表求和}
答案=sum(F(j)) {0<ja[i]) and (opt[j]+1>opt[i]) then
opt[i]:=opt[j]+1;
for i:=1 to n do
begin
j:=i-1;
while (j>0) and ((opt[i]opt[j]) or (a[i]a[j])) do
dec(j);
next[i]:=j;
end;
F[0,1]:=1;
for i:=1 to n+1 do
for j:=i-1 downto next[i] do
if (opt[j]=opt[i]-1) and (a[j]>a[i]) then
Hinc(F[i],F[j]);
end;
procedure print;
var
i,top,m:longint;
begin
write(opt[n+1]-1,' ');
top:=maxsize;
while (top>1) and (F[n+1][top]=0) do
dec(top);
write(F[n+1,top]);
for i:=top-1 downto 1 do
begin
m:=F[n+1,i];
while m<maxsize div 10 do
begin
write('0');
m:=m*10;
end;
write(F[n+1,i]);
end;
writeln;
close(input);
close(output);
end;
begin
init;
main;
print;
end.
例題4 船 (ships.pas/c/cpp) 來源：《奧賽經典》（提高篇）
【問題描述】
PALMIA國家被一條河流分成南北兩岸，南北兩岸上各有N個村莊。北岸的每一個村莊有一個唯一的朋友在南岸，且他們的朋友村莊彼此不同。
每一對朋友村莊想要一條船來連接他們，他們向政府提出申請以獲得批准。由於河面上常常有霧，政府決定禁止船隻航線相交（如果相交，則很可能導致碰船）。
你的任務是編寫一個程序，幫助政府官員決定批准哪些船隻航線，使得不相交的航線數目最大。
【輸入文件】ships.in
輸入文件由幾組數據組成。每組數據的第一行有2個整數X，Y，中間有一個空格隔開，X代表PALMIA河的長度（10<=X<=6000），Y代表河的寬度（10<=Y<=100）。第二行包含整數N，表示分別坐落在南北兩岸上的村莊的數目（1<=N<=5000）。在接下來的N行中，每一行有兩個非負整數C，D，由一個空格隔開，分別表示這一對朋友村莊沿河岸與PALMIA河最西邊界的距離（C代表北岸的村莊，D代表南岸的村莊），不存在同岸又同位置的村莊。最後一組數據的下面僅有一行，是兩個0，也被一空格隔開。
【輸出文件】ships.out
對輸入文件的每一組數據，輸出文件應在連續的行中表示出最大可能滿足上述條件的航線的數目。
【輸入樣例】
30 4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
0 0
【輸出樣例】
4
【問題分析】
這道題目相對來說思考難度較高，從字面意義上看不出問題的本質來，有點無法下手的感覺。這裡我給大家推薦兩種思考這類問題的方法。
法一：尋找規律法（我前面總結提到的第3個方法）
尋找規律自然要推幾組數據，首先當然有從樣例入手；
仔細觀察上圖：紅色航線是合法的，那麼他們滿足什麼規律呢？
C1 C2 C3 C4
北岸紅線的端點： 4 9 15 17
南岸紅線的端點： 2 8 12 17
D1 D2 D3 D4
不難看出無論線的斜率如何，都有這樣的規律：
C1<C2<C3<C4 且 D1<D2<D3<D4
如果我們把輸入數據排升序，問題變抽象為：
在一個序列（D）裡找到最長的序列滿足DI<DJ<Dk……且i<j<k
這樣的話便是典型的最長非降子序列問題了。。。。
法二：邊界條件法（我前面總結提到的第4個方法）
邊界法其實就是把數據往小了縮，顯然N=1是答案是1。N=2時呢？
考慮這樣一組數據：
N=2
C1 D1
C2 D2
當 C1D2 那麼一定會相交，反之則不會相交。
當C1 >C2時，如果D1<D2 那麼一定會相交，反之則不會相交。
N=3
C1 D1
C2 D2
C3 D3
……
其實不用在推導N=3了，有興趣的可以推導去。看N=2時就能得出：
對於任意兩條航線如果滿足Ci<Cj 且Di<Dj 則兩條航線不相交。這樣的話要想在一個序列裡讓所有的航線都不相交那比然滿足，C1<C2<C3…Cans且D1<D2<D3…<Dans ，也就是將C排序後求出最長的滿足這個條件的序列的長度就是解。
這樣分析後顯然是一個最長非降子序列問題。
複雜度：排序可以用O（nlogn）的算法，求最長非降子序列時間複雜度是O(n2).
總複雜度為O（n2）.
【源代碼】
program ships;
const
fin='ships.in';
fout='ships.out';
maxn=5010;
type
retype=record
C,D:longint;
end;
var
x,y,n,ans:longint;
a:array[0..maxn] of retype;
opt:array[0..maxn] of longint;
procedure init;
var
i:longint;
begin
readln(n);
for i:=1 to n do
read(a[i].c,a[i].d);
end;
procedure quick(L,r:longint);
var
i,j,x:longint;
y:retype;
begin
i:=L;
j:=r;
x:=a[(i+j) div 2].c;
repeat
while a[i].cx do
dec(j);
if ij;
if j>L then quick(L,j);
if i<r then quick(i,r);
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),0);
quick(1,n);
for i:=1 to n do
for j:=0 to i-1 do
if (a[j].dopt[i]) then
opt[i]:=opt[j]+1;
ans:=-maxlongint;
for i:=1 to n do
if ans<opt[i] then
ans:=opt[i];
writeln(ans);
end;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(x,y);
while (x+y0) do
begin
init;
main;
read(x,y);
end;
close(input);
close(output);
end.
1.2背包問題
首先說說背包問題的基本模型：
現有N個物品，每個物品的價值為V，重量為W。求用一個載重量為S的背包裝這寫物品，使得所裝物品的總價值最高。
背包問題用貪心和搜索解，當然效果不佳，不過在我的貪心和搜索總結中會說到。顯然標準的解法是動態規化，我在解決這個問題時習慣設計一維狀態，還可以設計二維的，二維狀態在下面會講，現在只討論用一維狀態實現背包問題。
背包問題的分類：
(1)小數背包:物品的重量是實數，如油，水等可以取1.67升……
(2)整數背包：0/1背包：每個物品只能選一次，或不選。不能只選一部分
部分背包：所選物品可以是一部分。
(3)多重背包：背包不只一個。
小數背包：在貪心總結中會細講。
整數背包：
部分背包：同小數背包。
0/1背包：這個問題是最經常出現的問題，應該熟練掌握。
我們先看一下0/1背包的簡化版：
現有N個物品，每個物品重量為W，這些物品能否使在載重量為S的背包裝滿（即重量和正好為S）？如過不能那能使物品重量和最重達到多少？
針對這一問題我們以物品的個數分階段，設計一個狀態opt[i]表示載重量為i的背包可否裝滿，顯然opt[i]的基類型是boolean。
決策是什麼呢？
當要裝第i個物品時，如果前i-1個物品可以使載重為 k的背包裝滿，那麼載重為k+w[i]的背包就可以裝滿。於是對於一個opt[j]來說，只要opt[j-w[i]]是true（表示可裝滿）那opt[j]就可以裝滿，但要注意：針對每一個物品枚舉背包的載重量時如果這樣正向的推導會使同一個物品用好幾次，因為k+w[i]可裝滿那k+w[i]+w[i]就可裝滿，但實際上是裝不滿的因為物品只有一個。解決這個問題很簡單，只要逆向推導就OK了。
這樣劃分階段，設計狀態，滿足無後效性和麼？
顯然對與一個每一個階段都是獨立的，物品的順序並不影響求解，因為裝物品的次序不限。而對於opt[j]只考慮opt[j-w[i]]而不考慮後面的，所以滿足無後效性。
有了上面的分析不難寫出狀態轉移方程：
opt[j]:=opt[j-w[1]] {opt[j-w[i]]=true}
時間複雜度：
階段數O(S)*狀態數（O(N)）*轉移代價（O(1)）=O（SN）
下面看幾個例題：
例題5 裝箱問題 (pack.pas/c/cpp) 來源：NOIP2001(普及組) 第四題
【問題描述】
有一個箱子容量為V（正整數，0＜＝V＜＝20000），同時有n個物品（0＜n＜＝30＝，每個物品有一個體積（正整數）。
要求n個物品中，任取若干個裝入箱內，使箱子的剩餘空間為最小。
【輸入文件】
第一 行一個正整數V表示箱子的容量，第二行一個正整數N表示物品個數，接下來N行列出這N個物品各自的體積。
【輸出文件】
單獨一行，表示箱子最小的剩餘空間。
【輸入樣例】
24
6
8
3
12
7
9
7
【輸出樣例】
0
【問題分析】
本題是經典的0/1背包問題，並且是0/1背包的簡化版，把箱子看做背包，容量看做載重量，體積看做重量，剩餘空間最小也就是儘量裝滿背包。於是這個問題便成了：
有一個栽重量為V的背包，有N個物品，儘量多裝物品，使背包儘量的重。
設計一個狀態opt[i]表示重量i可否構成。
狀態轉移方程：opt[j]:=opt[j-w[1]] {opt[j-w[i]]=true}
最終的解就是v-x（x<=n 且opt[x]=true 且 opt[x+1..n]=false）。
【源代碼1】
program pack;
const
fin='pack.in';
fout='pack.out';
maxv=20010;
maxn=100;
var
opt:array[0..maxv] of boolean;
w:array[0..maxn] of longint;
v,n,x:longint;
procedure init;
var
i:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(v);
read(n);
for i:=1 to n do
read(w[i]);
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to n do
for j:=v downto w[i] do
if opt[j-w[i]] then opt[j] :=true;
x:=v;
while not opt[x] do dec(x);
end;
procedure print;
begin
writeln(v-x);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
例題6 砝碼稱重 來源：NOIP1996（提高組） 第四題
【問題描述】
設有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重<=1000），用他們能稱出的重量的種類數。
【輸入文件】
a1 a2 a3 a4 a5 a6
（表示1g砝碼有a1個，2g砝碼有a2個，…，20g砝碼有a6個，中間有空格）。
【輸出文件】
Total=N
（N表示用這些砝碼能稱出的不同重量的個數，但不包括一個砝碼也不用的情況）。
【輸入樣例】
1 1 0 0 0 0
【輸出樣例】
TOTAL=3
【問題分析】
把問題稍做一個改動，已知a1+a2+a3+a4+a5+a6個砝碼的重量w[i], w[i]∈{ 1,2,3,5,10,20} 其中砝碼重量可以相等，求用這些砝碼可稱出的不同重量的個數。
這樣一改就是經典的0/1背包問題的簡化版了，求解方法完全和上面說的一樣，這裡就不多說了，只是要注意這個題目不是求最大載重量，是統計所有的可稱出的重量的個數。
【源代碼1】
program P4;
const
maxn=1010;
w:array[1..6] of longint=(1,2,3,5,10,20);
var
opt:array[0..maxn] of boolean;
a:array[1..6] of longint;
procedure init;
var
i:longint;
begin
for i:=1 to 6 do
read(a[i]);
end;
procedure main;
var
i,j,k:longint;
begin
fillchar(opt,sizeof(opt),false);
opt[0]:=true;
for i:=1 to 6 do
for j:=1 to a[i] do
for k:=maxn downto w[i] do
if opt[k-w[i]] then opt[k]:=true;
end;
procedure print;
var
ans,i:longint;
begin
ans:=0;
for i:=1 to maxn do
if opt[i] then
inc(ans);
writeln(ans);
end;
begin
init;
main;
print;
end.
例題7 積木城堡 來源：vijos P1059
【問題描述】
XC的兒子小XC最喜歡玩的遊戲用積木壘漂亮的城堡。城堡是用一些立方體的積木壘成的，城堡的每一層是一塊積木。小XC是一個比他爸爸XC還聰明的孩子，他發現壘城堡的時候，如果下面的積木比上面的積木大，那麼城堡便不容易倒。所以他在壘城堡的時候總是遵循這樣的規則。
小XC想把自己壘的城堡送給幼兒園裡漂亮的女孩子們，這樣可以增加他的好感度。為了公平起見，他決定把送給每個女孩子一樣高的城堡，這樣可以避免女孩子們為了獲得更漂亮的城堡而引起爭執。可是他發現自己在壘城堡的時候並沒有預先考慮到這一點。所以他現在要改造城堡。由於他沒有多餘的積木了，他靈機一動，想出了一個巧妙的改造方案。他決定從每一個城堡中挪去一些積木，使得最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺得應該使最後的城堡都儘可能的高。
任務：
請你幫助小XC編一個程序，根據他壘的所有城堡的信息，決定應該移去哪些積木才能獲得最佳的效果。
【輸入文件】
第一行是一個整數N(N0 do
begin
inc(top);
a[top]:=m;
inc(tothig,m);
read(m);
end;
for i:=1 to top do
for j:=tothig downto 1 do
if (j-a[i]>=0) and (opt[ii,j-a[i]]) then
opt[ii,j]:=true;
end;
ans:=maxhig;
while not opt[1,ans] do
dec(ans);
while not can(ans) do
dec(ans);
writeln(ans);
end;
begin
init;
main;
end.
回顧上面的內容充分說明動態規劃的本質就是遞推。其實按照我的理解（動規涉及最優決策，遞推是單純的總結）背包問題的簡化版更準確點算是遞推而非動態規劃，至於動歸和遞推之間的界線本來就很模糊（至少我這麼認為）把它看做什麼都可以，沒必要咬文嚼字。
回到0/1背包的原問題上（如果你忘了就去上面看看）。
如果在不知道這個模型的情況下我們怎麼做這個題呢？
這就要用到第一節提到的方法二：三要素法。
題目中明確說明對於一個物品要不就拿走要不就放下，其實題目赤裸裸的告訴我們決策就是不拿（用0表示）或拿（用1表示）。這樣想都不用想就知道了決策，這也是本題的突破口。知道了決策寫個搜索的程序應該是很輕鬆的了。
那麼階段是什麼呢？
顯然，給你一堆東西讓你往包裡塞，你當然是一個一個的那來，塞進去。那麼階段很明顯就是物品的個數。
狀態又是什麼呢？
有的人在裝東西是有個習慣（比如說我）就是先把東西分類，然後把同類的東西打個小包，最後在把小包放進去，我們可以按這個思想給物品打一些小包，也就是按照單位為1的遞增的順序準備好多小包，比如載重是6的包，可以為它準備載重是1，2，3，4，5的小包。這樣狀態就可以想出來了：
設計狀態opt[i，j]表示裝第i個物品時載重為j的包可以裝到的最大價值。
opt[i-1,j] (j-w[i]0)
狀態轉移方程：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個物品的重量，v[i]第i個物品的價值)
解釋：要載重為j的背包空出w[i]（j-w[i]）的空間且裝上第i個物品，比不裝獲得的價值大就裝上它。
邊界條件：opt[0,i]=0; (i∈{1..S})
註：
這種二維的狀態表示應該在下節講，但是為了方便理解先在這裡說了。
上面的方法動態規劃三要素都很明顯，實現也很簡單。但是在我初學背包時卻用另外一種一維的狀態表示法。
用第一節說的思考方法五（放寬約束和增加約束）在重新思考一下這個問題：
怎麼放寬約束呢？
把題目中的價值去掉，不考慮價值即最優就變成背包問題的簡化版了。那簡化版的求解對我們有何啟示呢？
再一次增加約束：背包只能裝滿。
顯然對於N個裝滿背包的方案中只要找到一個價值最大的就是問題的解。那麼裝不滿怎麼辦呢？其實裝不滿背包，它總要達到一定的重量（X）。我們可以把這種情況看作是裝滿一個載重為X的小包。
總結一下上面的思維過程：
放寬約束讓我們找到問題的突破口——和背包問題簡化版一樣，我們可以卻定載重為S的背包是否可以裝滿。
增加約束讓我們找到問題的求解方法——在裝滿背包的方案中選擇最優的一個方案。
這樣問題就解決了。
設計一個狀態opt[j]表示裝滿載重為j的背包可獲得的最大價值。對於第i個物品，只要opt[j-w[i]]可以裝滿且opt[j-w[i]]+v[i]比opt[j]大就裝上這個物品（更新opt[j]）。
怎麼使opt[j]既有是否構成又有最優的概念呢？
opt[j]只表示最優，只不過使初始條件+1，判斷opt[j]是否為0，如果opt[j]=0說明j裝不滿。
邊界條件：opt[0]=1;
狀態轉移方程：opt[j]=max{opt[j-w[i]]} (0<i<n,w[i]<=j<=S)
問題解： ans=max{opt[i]}-1 (0<i<=s)
時間複雜度：階段數O(S)*狀態數（O(N)）*轉移代價（O(1)）=O（SN）
下面看幾個例題：
例題8 採藥 (medic.pas/c/cpp) 來源：NOIP2005（普及組） 第三題
【問題描述】
辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞裡對他說：「孩子，這個山洞裡有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間裡，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大。」
如果你是辰辰，你能完成這個任務嗎？
【輸入文件】
輸入文件medic.in的第一行有兩個整數T（1 <= T <= 1000）和M（1 <= M <= 100），用一個空格隔開，T代表總共能夠用來採藥的時間，M代表山洞裡的草藥的數目。接下來的M行每行包括兩個在1到100之間（包括1和100）的整數，分別表示採摘某株草藥的時間和這株草藥的價值。
【輸出文件】
輸出文件medic.out包括一行，這一行只包含一個整數，表示在規定的時間內，可以采到的草藥的最大總價值。
【輸入樣例】
70 3
71 100
69 1
1 2
【輸出樣例】
3
【數據規模】
對於30%的數據，M <= 10；
對於全部的數據，M y then max:=x
else max:=y;
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),0);
for i:=1 to n do
for j:=1 to t do
if j-w[i]0) and (opt[j-w[i]]+v[i]>opt[j]) then
opt[j]:=opt[j-w[i]]+v[i];
ans:=-maxlongint;
for i:=1 to t do
if opt[i]>ans then ans:=opt[i];
end;
procedure print;
begin
writeln(ans-1);
close(output);
end;
begin
init;
main;
print;
end.
例題9 開心的金明 來源：NOIP2006（普及組）第二題
【問題描述】
金明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：「你的房間需要購買哪些物品，怎麼佈置，你說了算，只要不超過N 元錢就行」。今天一早金明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的N 元。於是，他把每件物品規定了一個重要度，分為5 等：用整數1~5 表示，第5 等最重要。他還從因特網上查到了每件物品的價格（都是整數元）。他希望在不超過N 元（可以等於N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設第j 件物品的價格為v[j]，重要度為w[j]，共選中了k 件物品，編號依次為j1...jk，則所求的總和為：v[j1]*w[j1]+..+v[jk]*w[jk]請你幫助金明設計一個滿足要求的購物單.
【輸入文件】
輸入的第1 行，為兩個正整數，用一個空格隔開： N m
（其中N（<30000）表示總錢數，m(<25)為希望購買物品的個數。）
從第2 行到第m+1 行，第j 行給出了編號為j-1的物品的基本數據，每行有2 個非負整數 v p
（其中v 表示該物品的價格（v≦10000），p 表示該物品的重要度（1~5））
【輸出文件】
輸出只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（=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;
procedure print;
var
i,ans:longint;
begin
ans:=0;
for i:=1 to n do
if opt[i]>ans then
ans:=opt[i];
writeln(ans-1);
end;
begin
init;
main;
print;
end.
例題10 金明的預算方案 (budget.pas/c/cpp) 來源：NOIP2006 第二題
【問題描述】
金明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：「你的房間需要購買哪些物品，怎麼佈置，你說了算，只要不超過N元錢就行」。今天一早，金明就開始做預算了，他把想買的物品分為兩類：主件與附件，附件是從屬於某個主件的，下表就是一些主件與附件的例子：
主件 附件
電腦 打印機，掃瞄儀
書櫃 圖書
書桌 檯燈，文具
工作椅 無
如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有0個、1個或2個附件。附件不再有從屬於自己的附件。金明想買的東西很多，肯定會超過媽媽限定的N元。於是，他把每件物品規定了一個重要度，分為5等：用整數1~5表示，第5等最重要。他還從因特網上查到了每件物品的價格（都是10元的整數倍）。他希望在不超過N元（可以等於N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。
設第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1，j2，……，jk，則所求的總和為：
v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*為乘號）
請你幫助金明設計一個滿足要求的購物單。
【輸入文件】
輸入文件budget.in 的第1行，為兩個正整數，用一個空格隔開：
N m （其中N（<32000）表示總錢數，m（<60）為希望購買物品的個數。）
從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數據，每行有3個非負整數： v p q
（其中v表示該物品的價格（v0，表示該物品為附件，q是所屬主件的編號）
【輸出文件】
輸出文件budget.out只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（0說明花i元可以買到物品。這樣就不難設計出這個狀態的轉移方程來：
opt[i]=max{opt[i],opt[i-wj]} ((i-wj>0) and (opt[i-wj]>0)) (0<jy then exit(x);
exit(y);
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),0);
opt[0]:=1;
for j:=1 to m do
for i:=n downto v[j] do
if q[j]=0 then
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;
procedure print;
begin
writeln((ans-1)*10);
close(output);
end;
begin
init;
main;
print;
end.
上面提到的幾個例題都是最基礎的題目，而且把問題抽象後就與背包問題的基本模型一樣了，但有些題目用到了基本模型，要求的解卻不一定很模型一樣，下面看個例子：
例題11 Money Systems (money.pas/c/cpp) 來源：USACO 2.3
【問題描述】
母牛們不但創建了他們自己的政府而且選擇了建立了自己的貨幣系統。[In their own rebellious way],，他們對貨幣的數值感到好奇。
傳統地，一個貨幣系統是由1,5,10,20 或 25,50, 和 100的單位面值組成的。
母牛想知道有多少種不同的方法來用貨幣系統中的貨幣來構造一個確定的數值。
舉例來說, 使用一個貨幣系統 {1,2,5,10,...}產生 18單位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。寫一個程序來計算有多少種方法用給定的貨幣系統來構造一定數量的面值。保證總數將會適合long long (C/C++) 和 Int64 (Free Pascal)。
【輸入文件】
貨幣系統中貨幣的種類數目是 V (1<= V<=25)。要構造的數量錢是 N (1<= N<=10,000)。
第 1 行: 二整數， V 和 N
第 2 行： 可用的貨幣 V 個整數。
【輸出文件】
單獨的一行包含那個可能的構造的方案數。
【輸入樣例】
3 10
1 2 5
【輸出樣例】
10
【問題分析】
把錢面值，把要構造的前看做載重為N的背包，這個問題便是0/1背包的簡化版了，但這個問題和傳統模型有所差異，不是判斷N是否可構成，而是求構成N的方案，而且這裡的面值是可以重複利用的（你可以看做是物品有無限多）。
對與第一個問題，只要把原來BOOLEAN型的狀態改為INT64，在遞推過程中累加方案數即可。
對於第二個問題，基本模型中為了避免重複在內重循環枚舉背包載重時採用倒循環，現在只要正向循環就OK了。
複雜度與原模型相同。
【源代碼】
{
ID:hhzhaojia2
PROG:money
LANG:PASCAL
}
program money;
const
fin='money.in';
fout='money.out';
maxv=100;
maxn=10010;
var
a:array[0..maxv] of longint;
opt:array[0..maxn] of int64;
v,n:longint;
procedure init;
var
i:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(v,n);
for i:= 1 to v do
read(a[i]);
close(input);
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),0);
opt[0]:=1;
for i:=1 to v do
for j:=a[i] to n do
inc(opt[j],opt[j-a[i]]);
end;
procedure print;
begin
writeln(opt[n]);
close(output);
end;
begin
init;
main;
print;
end.
背包問題方案的求法：
和大多數DP問題的方案的求法一樣，增加一個數組path和狀態維數相同用來記錄當前狀態的決策就OK了。
輸出方案時候通過當前決策推出上一決策，這一連穿的決策序列就是要求的方案。
下面看這樣一個數據：
載重：6 物品個數：3
重量 價值
物品1： 3 10
物品2： 2 2
物品3： 1 9
一維狀態求解過程：
i=1 : (枚舉物品)
opt[0..6]= 1 0 0 11 0 0 0
path[0..6]=0 0 0 1 0 0 0 {記錄最後裝入包中的物品的編號}
i=2
opt[0..6]=1 0 3 11 0 13 0
path[0..6]=0 0 2 1 0 2 0
i=3
opt[0..6]=1 10 3 12 20 13 22
path[0..6]=0 3 2 3 3 2 3
二維狀態求解過程： （略）
可以看到一維狀態的最優解是正確的，但細心分析發現一個驚人的問題： 方案不對！！
什麼最優解正確而方案不正確呢？
因為在解i=3時opt[6]用到的方案數應該是9+2+10=21。顯然這個方案是真確的，所以最優解正確。但是求解完opt[6]後，接著求解opt[3]卻把原來的opt[3]=10改成了opt[3]=2+9=11這樣，在整個求解過程結束後最後的方案opt[6]=9+2+10就變成了opt[6]=9+2+2+9也就是說1，2兩個物品裝了兩次。
這也正是我要說的下面的問題；
背包問題一維狀態於二維狀態的優劣：
顯然，一維狀態的維數少空間複雜度低。甚至在一些問題上可以減輕思考負擔。既然這樣是不是我們就應該屏棄二維狀態解法呢？
由於一維狀態在求解方案是存在錯誤，所以二維狀態還是很有用啊。當然有些問題雖然也是在求解方案但要求方案唯一這樣就又可以用一維狀態了。
看到這裡覺得頭暈就上趟廁所，返回來看下面的例題：
例題12 新年趣事之打牌 來源： vijos P1071
【問題描述】
過年的時候，大人們最喜歡的活動，就是打牌了。xiaomengxian不會打牌，只好坐在一邊看著。
這天，正當一群人打牌打得起勁的時候，突然有人喊道：「這副牌少了幾張！」眾人一數，果然是少了。於是這副牌的主人得意地說：「這是一幅特製的牌，我知道整副牌每一張的重量。只要我們稱一下剩下的牌的總重量，就能知道少了哪些牌了。」大家都覺得這個辦法不錯，於是稱出剩下的牌的總重量，開始計算少了哪些牌。由於數據量比較大，過了不久，大家都算得頭暈了。
這時，xiaomengxian大聲說：「你們看我的吧！」於是他拿出筆記本電腦，編出了一個程序，很快就把缺少的牌找了出來。
如果是你遇到了這樣的情況呢？你能辦到同樣的事情嗎？
【輸入文件】
第一行一個整數TotalW，表示剩下的牌的總重量。
第二行一個整數N（1<N<=100），表示這副牌有多少張。
接下來N行，每行一個整數Wi（1<=Wi0 then
begin
if opt[j]=0 then
path[j]:=i; {只有當前狀態沒求過才記錄方案}
inc(opt[j],opt[j-w[i]]);
end;
if opt[total]=0 then
begin
writeln('0');
halt;
end;
if opt[total]>1 then
begin
writeln('-1');
halt;
end;
i:=total;
while i>0 do
begin
ans[path[i]]:=false;
i:=i-w[path[i]];
end;
end;
procedure print;
var
i:longint;
begin
for i:=1 to n do
if ans[i] then write(i,' ');
end;
begin
init;
main;
print;
end.
1.3其它問題
一維動態規劃最常見的就是前面總結的最長下降/非降子序列和0/1背包問題了，當然還有別的一寫題。由於不是很常見所以沒有固定的解題模式，到時候具體問題具體分析。下面在看一些例子：
例題13 挖地雷問題 (P3.pas/c/cpp) 來源：NOIP1996（提高組）第三題（有改動）
【問題描述】
在一個地圖上有N個地窖（N 3 -> 4 -> 5
max=27
【Hint】
題目中的路徑是有向的且無環路（這是我做的改動原題中沒有要求）。
【問題分析】
看到題目的第一影響是貪心——以一點出發找與他連接的地窖中地雷數最多的一個。
但很容易想到反例：
5
1 2 1 1 100
1 1 0 0
0 1 0
0 1
0
按照貪心答案是3，但實際上答案是101。
於是就不得不放棄貪心的想法。
但是貪心給了我們啟示：從一個頂點出發要選擇向一個與他相連且以該點出發可以挖到較多雷的點走。（有點拗口）
另一種解釋：如果一個頂點連同N個份量，顯然要則一個較大的就是問題的解答，這個定義是滿足最優化原理的。
那它滿足無後效性麼？
因為圖是有向的，所以以與該頂點相連的點在往下走的路線中不包括該點。也就是說圖是一個AOV網（有向無環圖）。
既然滿足最優化原理，且無後效性，我們就可以用動態規劃解了。
這個問題的階段就是拓撲序列，但由於輸入是倒三角形，所以我們沒必要求拓撲序列，只要從N到著求解就可以了。
設計狀態opt[i]表示以i點出發可以挖到最多的雷的個數。
狀態轉移方程：opt[i]=max{opt[j]}+w[i] (g[i,j]=1)
(g存圖，w[i]存第i個地窖中的雷的個數)。
時間複雜度：
狀態數O(n)*轉移代價O(n)=O(n2)
這個題目還要求出路徑，可以用一個輔助數組path來記錄，path[i]表示從第i個出發走到的下一個點的編號。求解完只要按path記錄的路徑輸出即可。
【源代碼】
program P3;
const
fin='P3.in';
fout='P3.out';
maxn=200;
var
g:array[0..maxn,0..maxn] of longint;
n,ans:longint;
w,opt,path:array[0..maxn] of longint;
procedure init;
var
i,j:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(n);
fillchar(g,sizeof(g),0);
for i:=1 to n do
read(w[i]);
for i:=1 to n do
for j:=i+1 to n do
read(g[i,j]);
close(input);
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),0);
fillchar(path,sizeof(path),0);
for i:=n downto 1 do
begin
for j:=i+1 to n do
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;
for i:=2 to n do
if opt[i]>opt[ans] then ans:=i;
end;
procedure print;
var
i:longint;
begin
write(ans);
i:=path[ans];
while i>0 do
begin
write('-->',i);
i:=path[i];
end;
writeln;
writeln('max=',opt[ans]);
close(output);
end;
begin
init;
main;
print;
end.
2.狀態是二維的
通過前面的學習，我想因該對動態規劃不陌生了，我學習動態規劃是沒這麼系統，二維，一維一起上。二維狀態的動態規劃是重中之重。
所謂二維狀態就是說一般設計的狀態是opt[i,j]形式的。那i,j可以代表什麼呢？
有很多朋友問過我這個問題，我的回答是：
(1)i,j組合起來代表一個點的坐標（顯然是平面坐標系）（如：街道問題）。
(2)i,j組合表示一個矩陣的單元的位置（第i行，第j列）（如：數塔問題）
(3)起點為i長度為j的區間。（如：回文詞）
(4)起點為i終點為j的區間。（如：石子合併問題）
(5)兩個沒關聯的事物，事物1的第i個位置，對應事物2的第j個位置（花店櫥窗設計）
(6)兩個序列，第一個序列的前i個位置或第i個位置對應第2個序列的第j個位置或前j個位置。（最長公共子序列）。
(7)其它
下面通過例題和基本模型進一步說明：
2.1數塔問題
數塔問題來源於一道經典的IOI的題目，直接說題通過題目總結公性。以後遇到類似的題目可以參照這個模型。
例題14 數塔問題 (numtri.pas/c/cpp) 來源：IOI94
【問題描述】
考慮在下面被顯示的數字金字塔。
寫一個程序來計算從最高點開始在底部任意處結束的路徑經過數字的和的最大。每一步可以走到左下方的點也可以到達右下方的點。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的樣例中,從7 到 3 到 8 到 7 到 5 的路徑產生了最大和:30
【輸入文件】
第一個行包含 R(1<= R<=1000) ,表示行的數目。
後面每行為這個數字金字塔特定行包含的整數。
所有的被供應的整數是非負的且不大於100。
【輸出文件】
單獨的一行包含那個可能得到的最大的和。
【輸入樣例】
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
【輸出樣例】
30
【問題分析】
這個問題是學習動態規劃最簡單最經典的問題，說它經典是因為它的階段，狀態決策都十分明顯。
剛看到題目覺得沒有如手點，連怎麼儲存，描述這個金字塔都是問題，看輸入樣例發現：數字金字塔可以變成像輸入樣例那樣的下三角，這樣可以用一個二維數組儲a存它，並且可以用（i,j）描述一個數字在金字塔中的位置。
對於中間的一個點來說，想經過它則必須經過它的上方或左上（針對變化後的三角形）。也就是說經過這個點的數字和最大等於經過上方或左上所得的「最大和」中一個更大的加上這個點中的數字。顯然這個定義滿足最優子結構。
這樣階段很明顯就是金字塔的層，設計一個二維狀態opt[i,j]表示走到第i行第j列時經過的數字的最大和。決策就是opt[i-1,j] 或opt[i-1,j-1]中一個更大的加上（i,j）點的數字。
對於一個點只考慮上面或左上即前一階段，滿足無後效性。
狀態轉移方程：
opt[i-1,j]+a[i,j] (j=1)
opt[i,j]= opt[i-1,j-1]+ a[i,j] (j=i)
max{opt[i-1,j],opt[i-1,j-1]}+ a[i,j] (1<j=0所以方程也可以這樣寫:
opt[i,j]=max{opt[i-1,j],opt[i-1,j-1]}+a[i,j]
同理 j=i時方程也可以寫成上面那樣，所以方程綜合為：
opt[i,j]=max{opt[i-1,j],opt[i-1,j-1]}+a[i,j]（0<j<=i）
顯然答案是走到底後的一個最大值，即：
ans=max{opt[n,i]} (1<=i<=n)
其實從上往下走和從下往上走結果是一樣的，但是如果從下往上走結果就是opt[1,1]省下求最大值了，所以方程進一不改動：
opt[i,j]=max{opt[i+1,j],opt[i+1,j+1]}+a[i,j]（0<jopt[i+1,j+1] then
opt[i,j]:=opt[i+1,j]+a[i,j]
else opt[i,j]:=opt[i+1,j+1]+a[i,j];
end;
procedure print;
begin
writeln(opt[1,1]);
close(output);
end;
begin
init;
main;
print;
end.
例題15 Henry撿錢 (money.pas/c/cpp) 來源：Dream Team邀請賽
【問題描述】
最近,Henry由於失戀(被某大牛甩掉！)心情很是鬱悶.所以,他去了大牛家,尋求Michael大牛的幫助,讓他盡快從失戀的痛苦中解脫出來.Michael大牛知道Henry是很愛錢的,所以他是費盡腦水,絞盡腦汁想出了一個有趣的遊戲,幫助Henry.....
Michael感覺自己簡直是個天才(我們從不這麼認為),就把這個遊戲取名為:Henry揀錢.為了幫助更多的人採用這種方法早日脫離失戀之苦,Michael特地選在這次DT比賽中把遊戲介紹給大家...(大家鼓掌!!!)
其實,這個遊戲相當垃圾,目的就是為了滿足Henry這種具有強烈好錢的心理的人.遊戲是這樣的:Michael首先找到了一塊方形的土地,面積為m*n(米^2).然後他將土地劃分為一平方米大小的方形小格.Michael在每個格子下都埋有錢(用非負數s表示,表示人民幣的價值為s)和炸彈(用負數s表示,表示Henry挖出該方格下的東西會花掉s的錢去看病，醫炸彈炸傷的傷口)...遊戲的要求就是讓Henry從一側的中間列出發,按照下圖的5種方式前進（前進最大寬度為5）,不能越出方格.他每到一個格子,必定要取走其下相應的東西.直到到達土地的另一側,遊戲結束.不用說也知道,Henry肯定想得到最多的人民幣.所以他偷窺了,Michael埋錢的全過程,繪成了一張距陣圖.由於他自己手動找會很麻煩,於是他就找到了學習編程的你.請給幫他找出,最大人民幣價值.
揀錢路線規則(只有5個方向，如下圖)：
H為Henry的出發點，每組數據的出發點都是最後一行的中間位置！
(前方5個格子為當前可以到達的)
【輸入文件】
第一行為m n.(n為奇數)，入口點在最後一行的中間
接下來為m*n的數字距陣.
共有m行,每行n個數字.數字間用空格隔開.代表該格子下是錢或炸彈.
為了方便Henry清算,數字全是整數.
【輸出文件】
一個數,為你所找出的最大人民幣價值.
【輸入樣例】
6 7
16 4 3 12 6 0 3
4 -5 6 7 0 0 2
6 0 -1 -2 3 6 8
5 3 4 0 0 -2 7
-1 7 4 0 7 -5 6
0 -1 3 4 12 4 2
【輸出樣例】
51
【數據範圍】
N and M<=200.
結果都在longint範圍內
【問題分析】
去掉題目華麗的偽裝，我們可以這樣描述這個題目：
給定一個數字矩陣，從最後一層的中間出發可以向圖上所示的5個方向走，直到走到第一層，使經過的數字和最大。
如果我們不考慮負數對問題的影響，這個問題的描述就是經典的數塔問題了，只不過將塔變成了矩陣。
這樣就可以用剛剛講過的數塔問題的模型解這個題目了，我就不多說了。
狀態轉移方程：
opt[i,j]=max(opt[i-1,k])+a[i,j] (j-2<=k0) and (kmax) then
max:=opt[i-1,k];
opt[i,j]:=max+a[i,j];
end;
ans:=-maxlongint;
i:=(1+m) div 2;
for j:=i-2 to i+2 do
if (j>0) and (jans) then
ans:=opt[n,j];
end;
procedure print;
begin
writeln(ans);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
2.2街道問題
和數塔問題一樣街道問題也來源於一道典型的例題，下面我們看一下這道題。
例題16 街道問題 (way.pas/c/cpp) 來源：《奧賽經典》（提高篇）
【問題描述】
如圖所示的矩形圖中找到一條從左下角到右上角的最短路徑，圖中數字表示邊的長度。只能向右或向上走。
【輸入文件】第一行兩個數，N，M 矩形的點有N行M列。（0<N，M<1000）接下來N行每行M-1個數描述橫向邊的長度。接下來N-1行每行M個數描述縱向邊的長度。邊的長度小於10。
【輸出文件】一個數——最短路徑長度。
【輸入樣例】
4 5
3 7 4 8
4 6 3 5
3 6 3 5
5 4 6 2
7 6 3 5 3
2 8 5 9 4
8 7 4 3 7
【輸出樣例】
28
【問題分析】
因為只能向右或向上走，所以階段應該是這樣的：
如果把圖再做個改動看看：
這樣就想是上面說的數塔問題了，只不過數塔問題的數在點上而街道問題的數在邊上。但是並不影響問題的求解我們可以用數塔問題的思路來解這個問題。
設計一個二維狀態opt[i,j]表示走到（i,j）的最短路徑，顯然這個路徑只可能是左邊或上邊走來的，所以決策就是這兩個方向上加上經過的邊的和中一個較短的路。於是有下面的狀態轉移方程：
opt[i+1,j]+z[i,j] (j=1)
opt[i,j]＝ opt[i,j-1]+h[i,j] (i=n)
min{opt[i+1,j]+z[i,j],opt[i,j-1]+h[i,j]} (0<i<=n,0<j<=m)
和數塔問題一樣，這個問題也可以做類似的預處理：初始化opt的值是一個很大的數，保證解不會超過他，但要注意不要太的了，太大了可能有２２５問題。opt[0,0]=0。這樣就可以把方程整理為：
opt[i,j]= min{opt[i+1,j]+z[i,j],opt[i,j-1]+h[i,j]}
複雜度：狀態數O（N2）*轉移代價O（1）=O（N2）
這一類問題是很經典的問題。
思考這樣一個問題：如果讓找出一條最短路徑，一條較短路徑，且兩條路徑不重合該怎麼辦呢？
這個問題先留給大家思考，在後面的多維狀態中會詳細的講。
【源代碼】
program way;
const
fin='way.in';
fout='way.out';
maxn=1010;
var
h,z,opt:array[0..maxn,0..maxn] of longint;
n,m:longint;
procedure init;
var
i,j:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(n,m);
for i:=1 to n do
for j:=2 to m do
read(h[i,j]);
for i:=1 to n-1 do
for j:=1 to m do
read(z[i,j]);
close(input);
end;
function min(x,y:longint):longint;
begin
min:=y;
if x<y then min:=x;
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),$7F);
opt[n,0]:=0;
for i:=n downto 1 do
for j:=1 to m do
opt[i,j]:=min(opt[i+1,j]+z[i,j],opt[i,j-1]+h[i,j]);
end;
procedure print;
begin
writeln(opt[1,m]);
close(output);
end;
begin
init;
main;
print;
end.
還有一道例題是街道問題的變形在記憶化搜索處會說。
2.3最長公共子序列問題
和前面講的有所區別，這個問題的不涉及走向。很經典的動態規劃問題。
例題17 最長公共子序列 (lcs.pas/c/cpp) 來源：《全國青少年信息學奧林匹克聯賽培訓教材》
【問題描述】
一個給定序列的子序列是在該序列中刪去若干元素後得到的序列。確切地說，若給定序列X= ，則另一序列Z= 是X的子序列是指存在一個嚴格遞增的下標序列 ，使得對於所有j=1,2,…,k有 Xij=Zj
例如，序列Z=是序列X=的子序列，相應的遞增下標序列為。給定兩個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。例如，若X= 和Y= ，則序列是X和Y的一個公共子序列，序列也是X和Y的一個公共子序列。而且，後者是X和Y的一個最長公共子序列，因為X和Y沒有長度大於4的公共子序列。
給定兩個序列X= 和Y= ，要求找出X和Y的一個最長公共子序列。
【輸入文件】
輸入文件共有兩行，每行為一個由大寫字母構成的長度不超過200的字符串，表示序列X和Y。
【輸出文件】
輸出文件第一行為一個非負整數，表示所求得的最長公共子序列的長度，若不存在公共子序列，則輸出文件僅有一行輸出一個整數0，否則在輸出文件的第二行輸出所求得的最長公共子序列(也用一個 大寫字母組成的字符串表示。
【輸入樣例】
ABCBDAB
BDCBA
【輸出樣例】
4
BCBA
【問題分析】
這個問題也是相當經典的。。
這個題目的階段很不明顯，所以初看這個題目沒什麼頭緒，不像前面講的有很明顯的上一步，上一層之類的東西，只是兩個字符串而且互相沒什麼關聯。
但仔細分析發現還是有入手點的：
既然說是動態規劃，那我們首先要考慮的就是怎麼劃分子問題，一般對於前面講到的街道問題和數塔問題涉及走向的，考慮子問題時當然是想上一步是什麼？但這個問題沒有涉及走向，也沒有所謂的上一步，該怎麼辦呢？
既然是求公共子序列，也就有第一個序列的第i個字符和第二個序列的第j個字符相等的情況。
那麼我們枚第一個序列（X）的字符，和第二個序列（Y）的字符。
顯然如果X[i]=Y[j]那麼起點是1（下面說的子序列都是起點為1的），長度為i的子序列和長度為j的子序列的最長公共子序列就是長度為i-1和長度為j-1 的子序列中最長的公共子序列加上X[i]或Y[j]。
那要是不相等呢？
如果不相等，也就是說第一個序列長度為I的子序列和第二個序列中長度為j的子序列的公共子序列中X[i]和Y[j]不同時出現。也就是說第一個序列長度為i的子序列和第二個序列中長度為j的子序列的公共子序列是第一個序列長度為i的子序列和第二個序列中長度為j-1的子序列或第一個序列長度為i-1的子序列和第二個序列中長度為j的子序列的公共子序列中一個更長的。
設計一個狀態opt[i,j] 表示起點為1，第一序列長度為i，第二序列長度為j的子序列的最長公共子序列。按照上面的分類就可以得到狀態轉移方程：
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]))
(0<i<=length(X),0<j=length(opt[i,j-1]) then
opt[i,j]:=opt[i-1,j]
else opt[i,j]:=opt[i,j-1];
end;
procedure print;
begin
writeln(length(opt[L1,L2]));
write(opt[L1,L2]);
close(output);
end;
begin
init;
main;
print;
end.
例題18 回文詞 (palin.pas/c/cpp) 來源：IOI 2000
【問題描述】
回文詞是一種對稱的字符串——也就是說，一個回文詞，從左到右讀和從右到左讀得到的結果是一樣的。任意給定一個字符串，通過插入若干字符，都可以變成一個回文詞。你的任務是寫一個程序，求出將給定字符串變成回文詞所需插入的最少字符數。
比如字符串「Ab3bd」，在插入兩個字符後可以變成一個回文詞（「dAb3bAd」或「Adb3bdA」）。然而，插入兩個以下的字符無法使它變成一個回文詞。
【輸入文件】
第一行包含一個整數N，表示給定字符串的長度，3<=Ny then exit(x);
max:=y;
end;
procedure main;
var
i,x,j,k0,k1:longint;
begin
fillchar(opt,sizeof(opt),0);
readln(n);
readln(a);
b:='';
for i:=n downto 1 do
b:=b+a[i];
k0:=0;
k1:=1;
for i:=1 to n do
begin
fillchar(opt[k1],sizeof(opt[k1]),0);
for j:=1 to n do
begin
opt[k1,j]:=max(opt[k0,j],opt[k1,j-1]);
if a[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.
用這個方法AC了就該很高興了，但不要停止思考的步伐，還有別的方法麼？
從原問題出發，找這個問題的子問題。和上面說的最長公共子序列問題一樣，設計序列的問題我們一般要考慮它的子序列，也就是更短的序列。
這樣就回到了我第一節說的邊界條件法了。
顯然單獨的字符就是邊界了，而且單獨的字符就是回文詞，添加0個字符就可以了。
如果是兩個字符組成的序列怎麼辦呢？
只要看他們是否相同就可以了，如果相同那就是回文詞了，添加0個字符，如果不相同就在它的左邊或右邊添一個字符，讓另外一個當對稱軸。
如果是3個字符呢？
我們用S存這個序列，如果S[1]=S[3]那麼它就是回文詞了,
如果S[1]S[3]那麼就在前面添S[3]或後面添S[1]
剩下的就要考慮S[1]S[2]和S[2]S[3]這兩個序列了。
通過前面的分析我們很容易想到這樣的算法：
對於一個序列S只要看它的左右端的字符是否相同，如果相同那麼就看除掉兩端字符的新串要添的字符個數了；如果不同，就在它左面添上右斷的字符然後考慮去掉新序列兩端的字符後的串要添的字符。或者在右面添上左端的字符，在考慮去掉添了字符後新串左右兩端字符得到的新串要添的字符。
設計一個二維狀態opt[L,i]表示長度是L+1，起點是i的序列變成回文詞要添的字符的個數。階段就是字符的長度，決策要分類，即S[i] 和S[i+L]是否相等。
狀態轉移方程:
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])
複雜度：
空間複雜度=狀態數O（N2）
時間複雜度=狀態數O（N2）* 轉移代價O（1）=O（N2）
由於空間複雜度較高，仍然要用滾動數組。
【源代碼2】
program P1327;
const
maxn=5002;
var
a:array[0..maxn] of char;
opt:array[0..2,0..maxn] of longint;
n,ans:longint;
function min(x,y:longint):longint;
begin
min:=y;
if x<y then min:=x;
end;
procedure main;
var
i,L,j,k0,k1,k2:longint;
begin
fillchar(opt,sizeof(opt),0);
readln(n);
for i:=1 to n do
read(a[i]);
k0:=0;
k1:=1;
k2:=2;
for L:=1 to n-1 do
begin
for i:=1 to n-L do
begin
opt[k2,i]:=min(opt[k1,i],opt[k1,i+1])+1;
if a[i]=a[i+L] then
opt[k2,i]:=min(opt[k2,i],opt[k0,i+1]);
end;
j:=k0;
k0:=k1;
k1:=k2;
k2:=j;
end;
writeln(opt[k1,1]);
end;
begin
main;
end.
例題19 調整隊形 (queue.pas/c/cpp) 來源：TJU P1006
【問題描述】
學校藝術節上，規定合唱隊要參加比賽，各個隊員的衣服顏色不能很混亂：合唱隊員應排成一橫排，且衣服顏色必須是左右對稱的。
例如：「紅藍綠藍紅」或「紅藍綠綠藍紅」都是符合的，而「紅藍綠紅」或「藍綠藍紅」就不符合要求。
合唱隊人數自然很多，僅現有的同學就可能會有3000個。老師希望將合唱隊調整得符合要求，但想要調整儘量少，減少麻煩。以下任一動作認為是一次調整：
1、在隊伍左或右邊加一個人（衣服顏色依要求而定）；
2、在隊伍中任兩個人中間插入一個人（衣服顏色依要求而定）；
3、剔掉一個人；
4、讓一個人換衣服顏色；
老師想知道就目前的隊形最少的調整次數是多少，請你編一個程序來回答他。
因為加入合唱隊很熱門，你可以認為人數是無限的，即隨時想加一個人都能找到人。同時衣服顏色也是任意的。
【輸入文件】
第一行是一個整數n(1≦n≦3000)。
第二行是n個整數，從左到右分別表示現有的每個隊員衣服的顏色號，都是1到3000的整數。
【輸出文件】
一個數，即對於輸入隊列，要調整得符合要求，最少的調整次數。
【輸入樣例】
5
1 2 2 4 3
【輸出樣例】
2
【問題分析】
讀完題目發現很熟悉，仔細想想這個題就是回文詞的加強版。不同與回文詞的是這個問題的決策多了，不僅可以插入一個人（詞），還可以剔人，還可以換服裝，其實剔人和插入是等價的。也就是說比原問題只多了一個條件就是可以換服裝。
這樣就不能用回文詞的第一個方法解了。（因為序列中的元素不固定，可以換）。只能用第二個方法解。
和回文詞一樣，階段是序列的長度，狀態是opt[i,j]表示[i,j]這段區間內要變成回文所需要的最少的調整次數。
決策比回文詞多了一個，即：如果左右兩端不一樣還可以通過換服裝這種方式只花費一次的代價調整好。
狀態轉移方程：
min{opt[i,j-1]+1,opt[i+1,j]+1,opt[i+1,j-1]+1}
opt[i,j]= (a[i]a[j],1<=i<j<=n)
min{opt[i,j-1]+1,opt[i+1,j]+1,opt[i+1,j-1]}
(a[i]=a[j],1<=i<j<=n)
邊界條件:opt[i,i]=0 (1<=i<=n)
時間複雜度：
狀態數O（N2）*轉移代價O（1）=總複雜度O（N2）
【源代碼】
program queue;
const
fin='queue.in';
fout='queue.out';
maxn=3000;
var
a:array[0..maxn] of longint;
opt:array[0..maxn,0..maxn] of longint;
n:longint;
procedure init;
var
i:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
readln(n);
for i:=1 to n do
read(a[i]);
end;
procedure main;
var
i,j,L:longint;
begin
fillchar(opt,sizeof(opt),0);
for L:=1 to n-1 do
for i:=1 to n-L do
begin
j:=i+L;
if opt[i+1,j]+1<opt[i,j-1]+1 then
opt[i,j]:=opt[i+1,j]+1
else opt[i,j]:=opt[i,j-1]+1;
if a[i]=a[j] then
begin
if opt[i+1,j-1]<opt[i,j] then
opt[i,j]:=opt[i+1,j-1]
end
else begin
if opt[i+1,j-1]+1<opt[i,j] then
opt[i,j]:=opt[i+1,j-1]+1;
end;
end;
end;
procedure print;
begin
writeln(opt[1,n]);
close(input);
close(output);
end;
begin
init;
main;
print;
end.
2.4 背包問題的拓展
前面說的背包問題還有個有趣的變形，可以說是背包問題的拓展吧，下面看一下這個例題：
例題20 找啊找啊找GF (gf.pas/c/cpp) 來源：MM群2007七夕模擬賽（RQNOJ 57）
【問題描述】
"找啊找啊找GF,找到一個好GF,吃頓飯啊拉拉手,你是我的好GF.再見."
"誒,別再見啊..."
七夕...七夕...七夕這個日子,對於sqybi這種單身的菜鳥來說是多麼的痛苦...雖然他聽著這首叫做"找啊找啊找GF"的歌,他還是很痛苦.為了避免這種痛苦,sqybi決定要給自己找點事情幹.他去找到了七夕模擬賽的負責人zmc MM,讓她給自己一個出題的任務.經過幾天的死纏爛打,zmc MM終於同意了.
但是,拿到這個任務的sqybi發現,原來出題比單身更讓人感到無聊-_-....所以,他決定了,要在出題的同時去辦另一件能夠使自己不無聊的事情--給自己找GF.
sqybi現在看中了n個MM,我們不妨把她們編號1到n.請MM吃飯是要花錢的,我們假設請i號MM吃飯要花rmb[i]塊大洋.而希望騙MM當自己GF是要費人品的,我們假設請第i號MM吃飯試圖讓她當自己GF的行為(不妨稱作泡該MM)要耗費rp[i]的人品.而對於每一個MM來說,sqybi都有一個對應的搞定她的時間,對於第i個MM來說叫做time[i]. sqybi保證自己有足夠的魅力用time[i]的時間搞定第i個MM^_^.
sqybi希望搞到儘量多的MM當自己的GF,這點是毋庸置疑的.但他不希望為此花費太多的時間(畢竟七夕賽的題目還沒出),所以他希望在保證搞到MM數量最多的情況下花費的總時間最少.
sqybi現在有m塊大洋,他也通過一段時間的努力攢到了r的人品(這次為模擬賽出題也攢rp哦~~).他憑藉這些大洋和人品可以泡到一些MM.他想知道,自己泡到最多的MM花費的最少時間是多少.
注意sqybi在一個時刻只能去泡一個MM--如果同時泡兩個或以上的MM的話,她們會打起來的...
【輸入文件】
輸入的第一行是n,表示sqybi看中的MM數量.
接下來有n行,依次表示編號為1, 2, 3, ..., n的一個MM的信息.每行表示一個MM的信息,有三個整數:rmb, rp和time.
最後一行有兩個整數,分別為m和r.
【輸出文件】
你只需要輸出一行,其中有一個整數,表示sqybi在保證MM數量的情況下花費的最少總時間是多少.
【輸入樣例】
4
1 2 5
2 1 6
2 2 2
2 2 3
5 5
【輸出樣例】
13
【數據規模】
對於20%數據,1<=n<=10;
對於100%數據,1<=rmb<=100,1<=rp<=100,1<=time<=1000;
對於100%數據,1<=m<=100,1<=r<=100,1<=n0說明花費正好)
狀態轉移方程：
opt[j,k]=max{opt[j-rmb[i],k-rp[i]]+1}
(rmb[i]<=j<=m,rp[i]<=k<=r,0<i0)
ct[j,k]:=min{ct[j-rmb[i],k-rp[i]]}+time[i] (opt[j,k]=opt[j-rmb[i],k-rp[i]]+1)
時間複雜度：
階段數 O（N）*狀態數O（MR）*轉移代價O（1）= O（NMR）
註：數據挺小的。
問題拓展：
如果要加入別的條件，比如泡MM還要一定的SP，等也就是說一個價值要不同的條件確定，那麼這個問題的狀態就需要在加一維，多一個條件就多一維。
【源代碼】
program gf;
const
fin='gf.in';
fout='gf.out';
maxn=110;
var
rmb,rp,time:array[0..maxn] of longint;
opt,ct:array[0..maxn,0..maxn] of longint;
n,m,r,ans,max:longint;
procedure init;
var
i:longint;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
read(n);
for i:=1 to n do
read(rmb[i],rp[i],time[i]);
read(m,r);
close(input);
end;
procedure main;
var
i,j,k:longint;
begin
fillchar(opt,sizeof(opt),0);
fillchar(ct,sizeof(ct),0);
opt[0,0]:=1;
for i:=1 to n do
for j:=m downto rmb[i] do
for k:=r downto rp[i] do
if opt[j-rmb[i],k-rp[i]]>0 then
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]]+time[i];
end
else if (opt[j-rmb[i],k-rp[i]]+1=opt[j,k])
and (ct[j-rmb[i],k-rp[i]]+time[i]max then
begin
max:=opt[j,k];
ans:=ct[j,k];
end
else if (opt[j,k]=max) and (ct[j,k]0），打分越高的碟說明多多越愛看。每張碟有播放的時間Ti。多多想在今晚爺爺規定的時間裡看的碟總分最高。（必須把要看的碟看完，也就是說一張碟不能只看一半）。顯然叔叔在買碟是沒必要把N張全買了，只要買要看的就OK了，這樣節省資金啊。而且多多讓叔叔慣的特別任性只要他看到有幾張就一定會看完。
可是出現了一個奇怪的問題，買碟的地方只買給顧客M（M<N）張碟，不會多也不會少。這可讓多多叔叔為難了。怎麼可以在N張碟中只買M張而且在規定時間看完，而且使總價值最高呢？
聰明的你幫幫多多的叔叔吧。
【輸入說明】(watchdvd.in)
輸入文件有三行
第一行：兩個數空格隔開的正整數，N，M，L（分別表示叔叔給多多買的碟的數量，商店要買給叔叔的碟的數量，爺爺規定的看碟的時間段）。
第二行到第N行，每行兩個數：T，M，給出多多列表中DVD碟的信息。
【輸出說明】(watchdvd.out)
單獨輸出一行
表示多多今晚看的碟的總分。
如果商店賣給叔叔的M張碟無法在爺爺規定的時間看完輸出0；
【輸入樣例】
3 2 10
11 100
1 2
9 1
【輸出樣例】
3
【數據範圍】
20%的數據 N <=20; L<=2000;
100%的數據 N<=100 L<=2000; M y then max:=x;
end;
procedure main;
var
i,j,k:longint;
begin
fillchar(opt,sizeof(opt),0);
for i:=1 to n do
for j:=m downto 1 do
if j0) 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;
for i:=0 to v do
if opt[m,i]>ans then ans:=opt[m,i];
end;
procedure print;
begin
write(ans);
close(output);
end;
begin
init;
main;
print;
end.
2.5石子合併問題
也有人把這類問題叫做是區間上的動態規劃。
例題22 石子合併 (stone.pas/c/cpp) 來源：某年NOI（去巴蜀交）
【問題描述】
在一個操場上擺放著一行共n堆的石子。現要將石子有序地合併成一堆。規定每次只能選相鄰的兩堆合併成新的一堆，並將新的一堆石子數記為該次合併的得分。請編輯計算出將n堆石子合併成一堆的最小得分和將n堆石子合併成一堆的最大得分。
【輸入文件】
輸入第一行為n(n<1000)，表示有n堆石子，第二行為n個用空格隔開的整數，依次表示這n堆石子的石子數量（y then max:=x;
end;
function min(x,y:longint):longint;
begin
min:=y;
if (x0) then min:=x;
end;
procedure main;
var
i,j,L,k:longint;
begin
fillchar(minopt,sizeof(minopt),200);
fillchar(maxopt,sizeof(maxopt),0);
for i:=1 to 2*n do
minopt[i,i]:=0;
for L:=1 to n-1 do
for i:=1 to 2*n-L do
begin
j:=i+L;
for k:=i to j-1 do
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;
for i:=1 to n do
maxans:=max(maxans,maxopt[i,i+n-1]);
for i:=1 to n do
minans:=min(minans,minopt[i,i+n-1]);
{for i:=1 to n*2 do
begin
for j:=1 to n*2 do
write(maxopt[i,j],' ');
writeln;
end;}
end;
begin
init;
main;
writeln(minans,' ',maxans);
end.
例題23 能量項鏈 (energy.pas/c/cpp) 來源NOIP2006（提高組）
【問題描述】
在Mars星球上，每個Mars人都隨身佩帶著一串能量項鏈。在項鏈上有N顆能量珠。能量珠是一顆有頭標記與尾標記的珠子，這些標記對應著某個正整數。並且，對於相鄰的兩顆珠子，前一顆珠子的尾標記一定等於後一顆珠子的頭標記。因為只有這樣，通過吸盤（吸盤是Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標記為m，尾標記為r，後一顆能量珠的頭標記為r，尾標記為n，則聚合後釋放的能量為（Mars單位），新產生的珠子的頭標記為m，尾標記為n。
需要時，Mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請你設計一個聚合順序，使一串項鏈釋放出的總能量最大。
例如：設N=4，4顆珠子的頭標記與尾標記依次為(2，3) (3，5) (5，10) (10，2)。我們用記號⊕表示兩顆珠子的聚合操作，(j⊕k)表示第j，k兩顆珠子聚合後所釋放的能量。則第4、1兩顆珠子聚合後釋放的能量為：
(4⊕1)=10*2*3=60。
這一串項鏈可以得到最優值的一個聚合順序所釋放的總能量為
((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。
【輸入文件】
輸入文件energy.in的第一行是一個正整數N（4≦N≦100），表示項鏈上珠子的個數。第二行是N個用空格隔開的正整數，所有的數均不超過1000。第i個數為第i顆珠子的頭標記（1≦i≦N），當i2 3 5 10 2 3 5 10
這樣處理後其中任意長度為N+1的鏈就可代表一個環，那麼問題就轉化成合併任意長度為N+1的鏈所能釋放的總能量最大。
也就是說從任意一點(i<k<j)把鏈拆成兩段問題的解就是合併這兩段釋放出最大能量在加上合併後這兩顆珠子再一次合併釋放的能量。將這個子問題進一步分解就是分解到鏈長度為1也就是就有兩課珠子時，生成這兩顆柱子沒有釋放能量，而合併他們釋放的能量是m*r*n。（這就是邊界條件）。
我們設計一個狀態opt [i,j] 表示合併頭為i，尾為j的鏈狀項鏈所能釋放的最多的能量值。邊界條件是opt[i,i]=0 (1<=i<=n*2).
根據定義不難得到動規的狀態轉移方程:
opt[i,j]=max{opt[i,j],opt[i,k]+opt[k,j]+a[i]*a[k]*a[j]}(i<ky then exit(x);
exit(y);
end;
procedure main;
var
i,j,k,L:longint;
begin
fillchar(opt,sizeof(opt),0);
for L:=2 to n do
for i:=1 to n*2-L+1 do
begin
j:=i+L;
for k:=i+1 to j-1 do
opt[i,j]:=max(opt[i,j],opt[i,k]+opt[k,j]+a[i]*a[j]*a[k]);
end;
for i:=1 to n do
ans:=max(ans,opt[i,i+n]);
end;
procedure print;
begin
writeln(ans);
close(output);
end;
begin
init;
main;
print;
end.
例題24 統計單詞個數 (.pas/c/cpp) 來源：NOIP2001（提高組）
【問題描述】
給出一個長度不超過200的由小寫英文字母組成的字母串(約定;該字串以每行20個字母的方式輸入，且保證每行一定為20個)。要求將此字母串分成k份(1<k<=40)，且每份中包含的單詞個數加起來總數最大(每份中包含的單詞可以部分重疊。當選用一個單詞之後，其第一個字母不能再用。例如字符串this中可包含this和is，選用this之後就不能包含th)。
單詞在給出的一個不超過6個單詞的字典中。
要求輸出最大的個數。
【輸入文件】
去部輸入數據放在文本文件input3.dat中，其格式如下：
每組的第一行有二個正整數(p，k)
p表示字串的行數;
k表示分為k個部分。
接下來的p行，每行均有20個字符。
再接下來有一個正整數s，表示字典中單詞個數。(1<=s<=6)
接下來的s行，每行均有一個單詞。
【輸出文件】
結果輸出至屏幕，每行一個整數，分別對應每組測試數據的相應結果。
【輸入樣例】
1 3
thisisabookyouareaoh
4
is
a
ok
sab
【輸出樣例】
7
【問題分析】
剛看到這個題目覺得很迷茫，沒入手點但是突然看到了閃亮的突破口：題目中說this包含this和is 但不包含th這也就是說在一個串內對於一個固定了起點的單詞只能用一次，即使他還可以構成別的單詞但他還是用一次。比如：串：thisa
字典：this is th
串中有this is th這三個單詞，但是對於this 和 th 只用一次，也就是說枚舉一下構成單詞的起點，只要以該起點的串中包含可以構成一個以該起點開頭的單詞，那麼就說明這個串中多包含一個單詞。
這樣可一得出下面的結果：
每舉的起點 結論：
t 至少包含1個
h 至少包含1個
i 至少包含2個
s 至少包含2個
a 至少包含2個
考慮到這裡，就有點眉目了。
題目中要將串分K個部分也就是說從一個點截斷後一個單詞就未必可以構成了。比如上例要分3個部分合理的其中的一個部分至多有3個字母，這樣this 這個單詞就構不成了。
要是分5個部分，那就連一個單詞都夠不成了。
這樣就需要對上面做個改動，上面的只控制了起點，而在題目中還需要限制終點，分完幾個部分後，每部分終點不同可以構成的單詞就不同了。
這樣就需要再枚舉終點了。
設計一個二維數組sum[i,j]統計從i到j的串中包含的單詞的個數
狀態轉移方程:
sum[i+1,j]+1 (s[i,j]中包含以S[i]開頭的單詞)
sum[i,j]=
sum[i+1,j] (與上面相反)
註：(1)這裡枚舉字符的起點的順序是從尾到頭的。
(2)有人把上面這次也看做是一次動態規劃，但我覺得更準確的說是遞推。
求出所有的SUM還差一步，就是不同的劃分方法顯然結果是不一樣的，但是對於求解的問題我們可以這樣把原問題分解成子問題：求把一個串分成K部分的最多單詞個數可以看做是先把串的最後一部分分出來，在把前面一部分分解成K-1個部分，顯然決策就是找到一種劃分的方法是前面的K-1部分的單詞+最後一部分的單詞最多。
顯然這個問題滿足最優化原理，那滿足不滿足無後效性呢？
對於一個串分解出最後一部分在分解前面的那部分是更本就不會涉及分好的這部分，換句話說沒次分解都回把串分解的更小，對於分解這個更小的傳不會用到不屬於這個小串的元素。這就滿足無後效性。
具體求解過程：
設計一個狀態opt[i,j]表示把從１到j的串分成i份可以得到最多的單詞的個數。決策就是枚舉分割點使當前這種分割方法可以獲得最多的單詞。
狀態轉移方程：opt[I,j]=max(opt[i-1,t]+sum[t+1,j]) (i<t<j)
邊界條件：opt[1,i]=sum[1,i] (0<iy then max:=x;
end;
procedure main;
var
i,j,t:longint;
begin
L:=length(s);
for i:=L downto 1 do
for j:=i to L do
if find(i,j) then sum[i,j]:=sum[i+1,j]+1
else sum[i,j]:=sum[i+1,j];
fillchar(opt,sizeof(opt),0);
opt[1]:=sum[1];
for i:=2 to k do
for j:=i+1 to L do
for t:=i+1 to j-1 do
opt[i,j]:=max(opt[i,j],opt[i-1,t]+sum[t+1,j]);
writeln(opt[k,L]);
end;
begin
assign(input,fin);
reset(input);
assign(output,fout);
rewrite(output);
init;
main;
close(input);
close(output);
end.
2.6其他問題
還有一些題目雖和一寫基本模型相似但又有區別，我也就不總結共性了，列出它們，看看他們的狀態又是怎麼設計的：
例題25 花店櫥窗設計 (flower.pas/c/cpp) 來源：IOI或巴蜀評測系統
【問題描述】假設以最美觀的方式佈置花店的櫥窗，有F束花，每束花的品種都不一樣，同時，至少有同樣數量的花瓶，被按順序擺成一行，花瓶的位置是固定的，並從左到右，從1到V順序編號，V 是花瓶的數目，編號為1的花瓶在最左邊，編號為V的花瓶在最右邊，花束可以移動，並且每束花用1到F 的整數惟一標識，標識花束的整數決定了花束在花瓶中列的順序即如果I < J，則花束I 必須放在花束J左邊的花瓶中。
例如，假設杜鵑花的標識數為1，秋海棠的標識數為2，康乃馨的標識數為3，所有的花束在放人花瓶時必須保持其標識數的順序，即：杜鵑花必須放在秋海棠左邊的花瓶中，秋海棠必須放在康乃馨左邊的花瓶中。如果花瓶的數目大於花束的數目，則多餘的花瓶必須空，即每個花瓶中只能放一束花。
每一個花瓶的形狀和顏色也不相同，因此，當各個花瓶中放人不同的花束時會產生不同的美學效果，並以美學值(一個整數)來表示，空置花瓶的美學值為0。在上述例子中，花瓶與花束的不同搭配所具有的美學值，可以用如下表格表示。
根據表格，杜鵑花放在花瓶2中，會顯得非常好看，但若放在花瓶4中則顯得很難看。
為取得最佳美學效果，必須在保持花束順序的前提下，使花的擺放取得最大的美學值，如果具有最大美學值的擺放方式不止一種，則輸出任何一種方案即可。題中數據滿足下面條件：1≦F≦100，F≦V≦100，－50≦AIJ≦50，其中AII是花束I擺放在花瓶J中的美學值。輸入整數F，V 和矩陣(AIJ)，輸出最大美學值和每束花擺放在各個花瓶中的花瓶編號。
┌───┬───┬───┬───┬───┬───┐
│ │花瓶1│花瓶2 │花瓶3│花瓶4 │花瓶5│
├───┼───┼───┼───┼───┼───┤
│杜鵑花│ 7 │ 23 │ -5 │ -24 │ 16 │
├───┼───┼───┼───┼───┼───┤
│秋海棠│ 5 │ 21 │ -4 │ 10 │ 23 │
├───┼───┼──┼─── ┼── ─┼───┤
│康乃馨│ -21 │ 5 │ -4 │ -20 │ 20 │
\───┴───┴───┴───┴───┴───┘
【輸入文件】
第一行包含兩個數：F，V。 隨後的F 行中，每行包含V 個整數，Aij 即為輸入文件中第（i+1 ）行中的第j 個數
【輸出文件】
包含兩行:第一行是程序所產生擺放方式的美學值。第二行必須用F 個數表示擺放方式，即該行的第K個數表示花束K所在的花瓶的編號。
【輸入樣例】
3 5
7 23 –5 –24 16
5 21 -4 10 23
-21 5 -4 -20 20
【輸出樣例】
53
2 4 5
【題目鏈接】
http://mail.bashu.cn:8080/JudgeOnline/showproblem?problem_id=1597
【問題分析】
這個問題很奇怪題目中給定的條件是花瓶和花束，似乎是兩個沒有關聯的事物啊，但著兩個看似沒關聯的東西，卻有一點聯繫：不同的花放在不同的花瓶中產生不同的美學價值。
一般人的思維都是拿來花一個一個的放，假設要放第i束花時，把它放到哪裡好呢？
很容易想到一個貪心的策略：找到一個符合條件（第i束花要放在前i-1束花的後面）下的它放如後能產生最大的美學價值的花瓶放。但和容易舉出反例：
│ │花瓶1│花瓶2 │花瓶3│
├───┼───┼───┼───|
│杜鵑花│ 1 │ 2 │ -5 |
├───┼───┼───┼─——|
│秋海棠│ 5 │ 10 │ 1 │
按照貪心策略是：杜鵑花放在2號瓶裡，秋海棠放在3號瓶裡，美學值：3
答案是： 杜鵑花放在1號瓶裡，秋海棠放在2號瓶裡，美學值：11
數據量很大搜索顯然不行。
那要是動態規劃，階段，狀態，決策有是什麼呢？
既然要拿來花束一個一個的放，我們就以花束劃分階段。設計一個狀態opt[i,j]表示將第i束花放在第j個花瓶中可使前i束花或得的最大美學價值，那麼決策就很容易想到了：將第i束花放在第j個瓶中，那麼第i-1束花只能放在前j-1個瓶裡，顯然我們要找到一個放在前j-1個瓶中的一個最大的美學價值在加上當前第i束放在第j個瓶中的美學價值就是OPT[I，J]的值。
顯然符合最優化原理和無後效性。
狀態轉移方程：
opt[i,j]=max{opt[i-1,k]}+a[i,j] (i<=k<=j-1) 為什麼是iopt[i,j] then
begin
opt[i,j]:=opt[i-1,k];
path[i,j]:=k;
end;
inc(opt[i,j],a[i,j]);
end;
ans:=n;
for i:=n+1 to m do
if opt[n,i]>opt[n,ans]then ans:=i;
end;
procedure outputway(i,j:longint);
begin
if i>0 then
begin
outputway(i-1,path[i,j]);
write(j,' ');
end;
end;
procedure print;
var
i:longint;
begin
writeln(opt[n,ans]);
outputway(n,ans);
writeln;
end;
begin
init;
main;
print;
end.
例題26 Divisibility 來源：ZJU2042
【問題描述】
Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions:
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
We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.
You are to write a program that will determine divisibility of sequence of integers.
譯題：
給出N個數，你可以在這N個數中任意地添加+號或-號，求出能不能使算出的結果被K整除。可以則打印「Divisible」，否則打印「Not divisible」
(1 <= N <= 10000, 2 <= K <= 100)
下面是一個例子：
有4個數，分別是17 5 -21 15
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
有8種添法，其中第二種求出的-14能被7整除。
【輸入文件】
The first line of the input contains two integers, N and K (1 <= N <= 10000, 2 <= K <= 100) separated by a space.
The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value.
注意第一個數是測試數據的組數，多組測試數據一起測。。
【輸出文件】
Write to the output file the word "Divisible" if given sequence of integers is divisible by K or "Not divisible" if it's not.
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.
注意：輸出每組結果之間有空格，最後一行無空格，格式不對不能AC，我就是因為格式不對調了一上午。。。。
【輸入樣例】
2
4 7
17 5 -21 15
4 5
17 5 -21 15
【輸出樣例】
Divisible
Not divisible
【問題分析】
看到題目第一個反映就是枚舉中間添的運算符，算出值在MOD K如果有一個值MOD K=0則輸出「Divisible」。
時間複雜度是O（2N-1）。
但是題目給出的數據量很大，這樣做效率太低了。
因為題目涉及MOD運算，要想簡化問題就需要知道一些基本的MOD運算性質：
A*B mod C=(A mod C*B mod C) mod C
(A+B) mod C=(A mod C+B mod C) mod C
有了這個性質，我們就可以把累加後求余轉化成求余後累加（我們把減法看作加負數以後分析只說加法）再求余。這樣我們的讀入數據就控制在了1-K到K-1的範圍內了。
我們要判斷的就是
所有結果的累加和 MOD K 是否為0。簡記為:
（A+B）mod K=0 or (A+B) mod K0
如果我們按數的個數劃分階段，前N-1個數的運算結果 MOD K看做A，第N個數看作B就OK了。
於是我們想到了這樣的狀態：opt[i,j]表示前i個數是否可以得到餘數為J的結果。
那麼狀態轉移方程就是
opt[i,(j-a[i] mod k )mod k]=opt[i-1,j] (opt[i-1,j]=true);
opt[i,(j+a[i] mod k) mod k]=opt[i-1,j] (opt[i-1,j]=true);
如果opt[n,0]=true就輸出『Divisible'
注意上面
【源代碼】
program P2042;
const
maxk=110;
maxn=10010;
var
a:array[0..maxn] of longint;
opt:array[1..2,-maxk..maxk] of boolean;
n,k,tim,ii:longint;
vis:array[0..maxn] of boolean;
procedure init;
var
i:longint;
begin
read(n,k);
for i:=1 to n do
read(a[i]);
end;
procedure main;
var
i,j,p1,p2,p3:longint;
begin
fillchar(opt,sizeof(opt),false);
fillchar(vis,sizeof(vis),false);
for i:=1 to n do
if a[i] mod k=0 then vis[i]:=true;
for i:=1 to n do
a[i]:=a[i] mod k;
opt[1,a[1]]:=true;
p1:=1;
p2:=2;
for i:=2 to n do
if not vis[i] then
begin
fillchar(opt[p2],sizeof(opt[p2]),false);
for j:=1-k to k-1 do
if opt[p1,j] then
begin
opt[p2,(j-a[i]) mod k]:=true;
opt[p2,(j+a[i]) mod k]:=true;
end;
p3:=p1;
p1:=p2;
p2:=p3;
end;
if opt[p1,0] then writeln('Divisible')
else writeln('Not divisible');
end;
begin
read(tim);
for ii:=1 to tim do
begin
if ii>1 then
writeln;
init;
main;
end;
end.
3.多維狀態和動態規劃的優化
一般多維動態規劃的時，空間複雜度較高，所以我們要想辦法將其優化，我就把多維動態規劃和動態規劃的優化放到一起了……
多維動態規劃以三，四維最為常見，在多的也沒有太大的研究價值，其實多維動態規劃大多也就是上面的一維，和二維的加一些條件，或是在多進程動態規劃中要用到。當然除了這些特點外，狀態的表示也有一些共性。
三維：狀態opt[i,j,k]一般可表示下面的含義：
（1）二維狀態的基礎上加了某個條件，或其中一維變成兩個。
比如opt[L,i]表示起點為I，長度為L的序列的最優值。opt[L,i,j]就可表示起點是i和起點是j，長度是L的兩個序列的最優值。
（2）I，J，K組合表示一個正方形（（i,j）點為一角，邊長為K）。
（3）I，J，K組合表示一個等邊三角形（（i,j）點為一角，邊長為K）。
四維：除了二維和三維加條件外，還可以用i,j,k,t組合來描述一個矩形，
（i,j）點和（k,t）點是兩個對頂點。
四維以上的一般都是前幾維加了條件了，這裡就不多說了。
動態規劃的優化：
動態規劃的優化往往需要較強的數學功底。
常見空間優化：
滾動數組，滾動數組在前面也提到過，其實很簡單，如果一個狀態的決策的步長為N就只保留以求出的最後N（一般N=1）個階段的狀態，因為當前狀態只和後N個階段中的狀態有關，再以前的已經利用過了，沒用了就可以替換掉了。具體實現是最好只讓下標滾動（這樣更省時間）。
X：=K1，K1：=K2，K2；=K3，K3：=X這樣就實現了一個N=3的下標的滾動，在滾動完如果狀態是涉及累加，累乘類的操作要注意將當前要求的狀態初始化。
常見時間優化：利用一些數據結構（堆，並查集，HASH）降低查找複雜度。
時間空間雙重優化：改變狀態的表示法，降低狀態維數。
具體的多維動態規劃和動態規劃的優化，我們從題目裡體會吧！
3.1矩陣問題
先看一道題
例題27 蓋房子 來源：VIJOS P1057
【問題描述】
永恆の靈魂最近得到了面積為n*m的一大塊土地（高興ING^_^），他想在這塊土地上建造一所房子，這個房子必須是正方形的。
但是，這塊土地並非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。這些瑕疵十分噁心，以至於根本不能在上面蓋一磚一瓦。
他希望找到一塊最大的正方形無瑕疵土地來蓋房子。
不過，這並不是什麼難題，永恆の靈魂在10分鐘內就輕鬆解決了這個問題。現在，您也來試試吧。
【輸入文件】
輸入文件第一行為兩個整數n,m（1<=n,m<=1000），接下來n行，每行m個數字，用空格隔開。0表示該塊土地有瑕疵，1表示該塊土地完好。
【輸出文件】
一個整數，最大正方形的邊長。
【輸入樣例】
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
【輸出樣例】
2
【問題分析】
題目中說要求一個最大的符合條件的正方形，所以就想到判斷所有的正方形是否合法。
這個題目直觀的狀態表示法是opt[i,j,k]基類型是boolean，判斷以（i,j）點為左上角（其實任意一個角都可以，依據個人習慣）,長度為K的正方形是否合理，再找到一個K值最大的合法狀態就可以了（用true表示合理，false表示不合理）。其實這就是遞推，（決策唯一）。
遞推式：
opt[i,j,k]=opt[i+1,j+1,k-1] and opt[i+1,j,k-1] and opt[i,j+1,k-1] and (a[i,j]=1)
時間複雜度：
狀態數O（N3）*轉移代價O（1）=總複雜度O（N3）
空間複雜度：
O（N3）
由於空間複雜度和時間複雜度都太高，不能AC，我們就的再想想怎麼優化？
顯然何以用滾動數組優化空間，但是時間複雜度仍然是O（N3）。這就需要我們找另外一種簡單的狀態表示法來解了。
仔細分析這個題目，其實我們沒必要知道正方形的所有長度，只要知道以一個點為左上角的正方形的最大合理長度就可以了。
如果這個左上角是0那麼它的最大合理長度自然就是0（不可能合理）。
如果這個左上角是1呢？
回顧上面的遞推式，我們考慮的是以它的右面，下面，右下這個三個方向的正方形是否合理，所以我們還是要考慮這三個方向。具體怎麼考慮呢？
如果這三個方向合理的最大邊長中一個最小的是X，那麼它的最大合理邊長就是X+1。為什麼呢？
看個例子：
0 1 1 1 1 1
1 1 1 1 1 1
0 1 0 1 1 0
1 1 0 1 1 1
上例中紅色的正方形，以（1,3）點為左上角，以（1，4），（2，3），（2，4）這三個點的最大合理邊長分別是2，1，2。其中最小的是以（2，3）為左上角的正方形，最大合理邊長是1。因為三個方向的最大合理邊長大於等於1，所以三個方向上邊長為1的正方形是合理的，即上面低推式中:
opt[1,3,2]=opt[1,4,1] and opt[2,3,1] and opt[2,4,1] and (a[1,3]=1) = true 成立
這樣就把一個低推判定性問題轉化成最優化問題從而節省空間和時間。
具體實現：
設計一個狀態opt[i,j]表示以（i,j）為左上角的正方形的最大合理邊長。
狀態轉移方程：
min{opt[i+1,j],opt[i,j+1],opt[i+1,j+1]}+1 (a[i,j]=1)
opt[i,j]=0 (a[i,j]=0)
時間複雜度：狀態數O（N2）*轉移代價O（1）=總代價O（N2）
空間複雜度：O（N2）
【源代碼】
program P1057;
const
maxn=1010;
var
opt,a:array[0..maxn,0..maxn] of longint;
n,m,ans:longint;
procedure init;
var
i,j:longint;
begin
read(n,m);
for i:=1 to n do
for j:=1 to m do
read(a[i,j]);
end;
procedure main;
var
i,j:longint;
begin
fillchar(opt,sizeof(opt),0);
for i:=n downto 1 do
for j:=m downto 1 do
if a[i,j]0 then
begin
opt[i,j]:=opt[i+1,j];
if opt[i,j+1]<opt[i,j] then
opt[i,j]:=opt[i,j+1];
if opt[i+1,j+1]ans then ans:=opt[i,j];
writeln(ans);
end;
begin
init;
main;
end.
3.2多進程動態規劃
從字面上就可以看出，所謂多進程就是在原文題的基礎上要求將這個問題重複多次的總和最大。
具體怎麼做看個例題吧。
例題28 方格取數 (fgqs.pas/c/cpp) 來源：NOIP2000(提高組)
【問題描述】
設有N*N的方格圖(N<=10,我們將其中的某些方格中填入正整數,而其他的方格中則放入數字0。如下圖所示（見樣例）：
某人從圖的左上角的A 點出發，可以向下行走，也可以向右走，直到到達右下角的B點。在走過的路上，他可以取走方格中的數（取走後的方格中將變為數字0）。
此人從A點到B 點共走兩次，試找出2條這樣的路徑，使得取得的數之和為最大。
【輸入文件】
輸入的第一行為一個整數N（表示N*N的方格圖），接下來的每行有三個整數，前兩個表示位置，第三個數為該位置上所放的數。一行單獨的0表示輸入結束。
【輸出文件】
只需輸出一個整數，表示2條路徑上取得的最大的和。
【輸入樣例】
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
【輸出樣例】
67
【問題分析】
這是一道很經典的多進程動態規劃題，如果只取一次，它的模型就是我們前面講的街道問題了，很簡單就可以實現。現在要求取兩次，怎麼辦呢？
一個自然的想法是：將前面的取過的數全賦成0，然後在取一次，感覺挺對的，樣例也過了。
但這樣做是錯的，第一次取的顯然是最大值，但第二次取的未必次大，所以也許兩條非最大的路，也許比一條最大一條小一點的路更優。
看個例子：
0 0 2 0 3 0 0 0 2 0 3 0
0 0 2 0 0 0 0 0 2 0 0 0
0 0 2 0 2 0 0 0 2 0 2 0
0 0 0 0 2 0 0 0 0 0 2 0
0 0 0 0 2 0 0 0 0 0 2 0
0 0 2 0 2 0 0 0 2 0 2 0
圖1 圖2
如上圖，圖1是按找上訴思路求得的解。圖中紅色路線是第一求得的最大值，顯然圖1紅色和紫色兩條路徑不如圖2藍色和綠色兩條路徑大。
既然這樣做不行，我們還得回到動態規劃的本質來看代問題，我們在想想這個問題的狀態，對於走一次，走到矩陣的任意一個位置就是一個狀態，而要是走兩次，顯然走到矩陣的某個位置只是一個狀態的一部分，不能完整的描述整個狀態。那另一部分顯然就是第二次走到的位置了。如果我們把這兩部分合起來就是一個完整的狀態了。
於是，設計一個狀態opt[i1,j1,i2,j2]表示兩條路分別走到（i1,j1）點和（i2,j2）點時取到的最大值。顯然決策有4中（乘法原理一個點兩種*另一個點的兩中）
即（上，上）（上，左）（左，上）（左，左）上和左表示從哪個方向走到該點，當然要注意走到同行，同列，同點時的情況（因為要求路徑不重複）。
狀態轉移方程：
max(opt[i1-1,j1,i2-1,j2],opt[i1,j1-1,i2-1,j2])+a[i1,j1]+a[i2,j2] (1<=i1=i2<=n,1<=j1<=j2<=n)
max(opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2,j2-1])
(1<=j1=j2<=n,1<=i1<=i2<=n)
opt[i,j]= max(opt[i1-1,j1,i2-1,j2],opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2-1,j2],
opt[i1,j1-1,i2,j2-2])+a[i1,j1]+a[i2,j2] (1<=i1,j1<=i2,j2<=n)
max(opt[i1-1,j1,i2-1,j2],opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2-1,j2],
opt[i1,j1-1,i2,j2-2])+a[i1,j1] (1<=i1=i2<=n,1<=j1=j2y then max:=x;
end;
procedure main;
var
i1,i2,j1,j2:longint;
begin
for i1:=1 to n do
for j1:=1 to n do
for i2:=i1 to n do
for j2:=1 to j1 do
if (i1=i2) and (j1=j2) then
opt[i1,j1,i2,j2]:=opt[i1-1,j1,i2,j2-1]+a[i1,j1]
else if (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]
else if (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]
else begin
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,j1,i2,j2],opt[i1,j1-1,i2,j2-1]);
opt[i1,j1,i2,j2]:=max(opt[i1,j1,i2,j2],opt[i1,j1-1,i2-1,j2]);
inc(opt[i1,j1,i2,j2],a[i1,j1]+a[i2,j2]);
end;
end;
procedure print;
begin
writeln(opt[n,n,n,n]);
close(output);
end;
begin
init;
main;
print;
end.
如果這個題的數據範圍在大點就得優化了，怎麼優化這個程序呢？
上面說過對於時間空間都大的時候，首先想到的就是尋找特點，改變狀態的表示法，減少狀態的維數。
仔細分析我們發現，處於同行，同列的狀態，等價於另外一個點在對角線上的狀態。而這條對角線正是此題的階段。因為在狀態轉移的時候後面的哪個點總是從固定的一個方向轉移來的。也就是說我們只要對角先上的狀態就可以省掉那些同行同列的狀態了。
做過N皇的同學一定知道怎麼表示右上到左下的這幾條對角線，不知道的同學也沒關係,對於一個點（i,j）他對角右上角的點就是（i-1，j+1）所以可以看出這些點的和是定值，且值從2到N*2。
這樣用三個變量就可以表示這兩個點了，於是設計狀態opt[k,i1,i2]表示處於階段K時走到i1,i2的兩條路徑所取得的數的最大和。
用上面的思維不難想出動態轉移方程：
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](1<=i1,i2<=n,2<=k<=n*2,i1i2)
otp[k,i1,i2]=opt[k-1,i1-1,i2]+a[i1,k-i1](1<=i1,i2<=n,2<=ky then max:=x;
end;
procedure main;
var
k,i1,i2,j1,j2,mid:longint;
begin
for k:=2 to n*2 do
begin
for i1:=1 to n do
if (k-i1>0) and (k-i10) and (k-i2=1）子樹的最優解，決策會很多。以至於我們沒發寫出準確的狀態轉移方程。這就是我們為什麼要把多叉數轉化成二叉數的原因。（當然，如果問題是求所有子樹的和，就沒必要轉化了，如URAL P1039 沒有上司的舞會）。
如果把多叉樹或森林轉化成二叉樹要注意，左兒子和根結點是父子關係，而右兒子在原問題中和跟結點是兄弟關係。（這個數據結構掌握紮實的應該能明白，不理解的就去看數據結構方面的知識）。
用鄰接矩陣存多叉樹，轉化成二叉樹的部分代碼（可能有語法錯誤）
G: 存圖，F[i] 表示第i個結點的兒子應該插入的位置
W：結點的值 BT：二叉樹
Procedure creat_tree(T:tree);
Var
i:longint;
Begin
for i:=1 to n do
Begin
for j:=1 to n do
If g[i,j] then
Begin
If F[i]=0 then
BT[i].L:=j
Else BT[F[i]].r:=j;
F[i]:=j;
End;
End;
End;
下面同過例題看一下樹型動態規劃的具體實現：
例題29 加分二叉樹 (binary.pas/c/cpp) 來源：NOIP2003（提高組）
【問題描述】
設一個n個節點的二叉樹tree的中序遍歷為（l,2,3,…,n），其中數字1,2,3,…,n為節點編號。每個節點都有一個分數（均為正整數），記第i個節點的分數為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下：
subtree的左子樹的加分× subtree的右子樹的加分＋subtree的根的分數
若某個子樹為空，規定其加分為1，葉子的加分就是葉節點本身的分數。不考慮它的空
子樹。
試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。要求輸出；
（1）tree的最高加分
（2）tree的前序遍歷
【輸入格式】
第1行：一個整數n（n＜30），為節點個數。
第2行：n個用空格隔開的整數，為每個節點的分數（分數＜100）。
【輸出格式】
第1行：一個整數，為最高加分（結果不會超過4,000,000,000）。
第2行：n個用空格隔開的整數，為該樹的前序遍歷。
【輸入樣例】
5
5 7 1 2 10
【輸出樣例】
145
3 1 2 4 5
【問題分析】
根據題目描述就可以看出是典型的樹型動態規劃，而且題目中已經給出了加分的求法：
subtree的左子樹的加分× subtree的右子樹的加分＋subtree的根的分數
這估計是最簡單的題目了。
但是有一點需要注意：我們應該怎麼建樹？
其實這個題不用建樹，這就需要我們對數據結構掌握的很紮實。
題目中說這個樹的中序遍歷是1，2，3……N，我們要求的是樹的先序，這樣馬上就想到怎樣用中序和先序確定一棵樹。
枚舉樹根i那麼1，2……i-1就是它的左子樹中的結點，i+1……N就是它右子樹中的結點。這樣一顆樹按這樣的低歸定義就構造出來了，（當然我們只要這個過程並不需要存儲這棵樹）。在構造過程中順便求出加分來，在一個序列裡不同的元素做根顯然加分不同，我們只要記錄一個最大的就可以了。
具體實現方法：
設計狀態opt[L,r]表示以L為起點，以r為終點的結點所組成的樹的最高加分，階段就是樹的層數。決策就是在這些結點中找一個結點做根使樹的加分最大，狀態轉移方程：
1 (L>r)
opt[L,r] = a[L] (L=r)
max{opt[L,i-1]*opt[i+1,r]+a[i]} (L<r,L<=ir then
begin
opt[L,r]:=1;
path[L,r]:=0;
end
else if L=r then
begin
opt[L,r]:=a[L];
path[L,r]:=L;
end
else begin
for i:=L to r do
begin
x:=TreeDp(L,i-1)*TreeDp(i+1,r)+a[i];
if x>opt[L,r] then
begin
opt[L,r]:=x;
path[L,r]:=i;
end;
end;
end;
end;
TreeDp:=opt[L,r];
end;
procedure print(L,r:longint);
begin
if path[L,r]>0 then
begin
write(path[L,r],' ');
print(L,path[L,r]-1);
print(path[L,r]+1,r);
end;
end;
begin
init;
writeln(TreeDp(1,n));
print(1,n);
close(output);
end.
例題30 A Binary Apple Tree 蘋果二叉樹 來源：URAL P1018
【問題描述】
設想蘋果樹很像二叉樹，每一枝都是生出兩個分支。我們用自然數來數這些枝和根那麼必須區分不同的枝（結點），假定樹根編號都是定為1，並且所用的自然數為1到N。N為所有根和枝的總數。例如下圖的N為5，它是有4條枝的樹。
2 5
\ /
3 4
\ /
1
當一棵樹太多枝條時，採摘蘋果是不方便的，這就是為什麼有些枝要剪掉的原因。現在我們關心的是，剪枝時，如何令到損失的蘋果最少。給定蘋果樹上每條枝的蘋果數目，及必須保留的樹枝的數目。你的任務是計算剪枝後，能保留多少蘋果。
【輸入文件】
首行為N，Q (1 <= Q <= N, 1 < N <= 100), N為一棵樹上的根和枝的編號總數，Q為要保留的樹枝的數目。以下N-1行為每條樹枝的描述，用3個空格隔開的整數表示，前2個數為樹枝兩端的編號,第三個數為該枝上的蘋果數。假設每條枝上的蘋果數不超過3000個。
【輸出文件】
輸出能保留的蘋果數。（剪枝時，千萬不要連根拔起哦）
【輸入樣例】
5 2
1 3 1
1 4 10
2 3 20
3 5 20
【輸出樣例】
21
【問題分析】
和上一道題一樣，題目描述就很明確的說是關於樹的題目，在加上是求最優值，和上一道題不同的是，這個題目邊有值，並非點有值，還有一個不同點就是這個題需要建樹。
建樹是要注意，給每個結點增加一個域：SUM用來存以它為根的樹中的邊的數目。
其實樹型動態規劃是最好分析的，因為樹這種數據結構本來就符合遞歸定義，這樣的話子問題很好找，顯然這個問題的子問題就是一棵樹要保留M個枝分三種情況：
剪掉左子樹：讓右子樹保留M-1個枝可保留最多的蘋果數+連接右子樹的枝上的蘋果數
剪掉右子樹：讓左子樹保留M-1個枝可保留最多的蘋果數+連接左子樹的枝上的蘋果數
都不剪掉： 讓左子樹保留i個枝，讓右子樹保留M-2-i個枝可保留最多的蘋果數+連接右子樹的枝上的蘋果數+連接左子樹的枝上的蘋果數
顯然邊界條件就是如果要保留的枝子數比當前的子樹的枝多，或著一個樹要保留0個枝子，則結果就是0。
應為一顆樹中根接點是對子樹的完美總結，所以滿足最優化原理。
沒次求解只和子樹有關所以也滿足無後效性，可見用動態規劃做是正確的。
設計一個狀態opt[num,i]表示要讓結點編號為i的樹保留num個枝可得到的最優解。
狀態轉移方程：
opt[num,i]=max{opt[num-1,BT[i].L]+T[i,BT[i].L],opt[num-1,BT[i].r]+T[i,BT[i].r],opt[k,BT[i].L]+opt[num-2-k,BT[i].r]+T[i,BT[i].L]+T[i,BT[i].r]}
(0<=k0) and (not vis[j]) then
begin
creat_tree(j);
BT[i].L:=Bt[i].r;
Bt[i].r:=j;
inc(Bt[i].sum,BT[j].sum+1);
end;
end;
Function max(x,y:longint):longint;
begin
max:=y;
if x>y then max:=x;
end;
Function F(num,i:longint):longint;
var
k:longint;
begin
if opt[num,i]BT[i].sum) or (num=0) then opt[num,i]:=0
else begin
opt[num,i]:=F(num-1,BT[i].L)+T[i,BT[i].L];
opt[num,i]:=max(opt[num,i],F(num-1,BT[i].r)+T[i,BT[i].r]);
for k:=0 to num-2 do
opt[num,i]:=max(opt[num,i],F(k,BT[i].L)+F(num-2-k,BT[i].r)
+T[i,BT[i].L]+T[i,BT[i].r]);
end;
end;
F:=opt[num,i];
end;
begin
init;
creat_tree(1);
fillchar(opt,sizeof(opt),200);
writeln(F(m,1));
close(output);
end.
例題31 選課 來源：VIJOS P1180
【問題描述】
學校實行學分制。每門的必修課都有固定的學分，同時還必須獲得相應的選修課程學分。學校開設了N（N<300）門的選修課程，每個學生可選課程的數量M是給定的。學生選修了這M門課並考核通過就能獲得相應的學分。
在選修課程中，有些課程可以直接選修，有些課程需要一定的基礎知識，必須在選了其它的一些課程的基礎上才能選修。例如《Frontpage》必須在選修了《Windows操作基礎》之後才能選修。我們稱《Windows操作基礎》是《Frontpage》的先修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。每門課都有一個課號，依次為1，2，3，…。例如:
表中1是2的先修課，2是3、4的先修課。如果要選3，那麼1和2都一定已被選修過。 你的任務是為自己確定一個選課方案，使得你能得到的學分最多，並且必須滿足先修課優先的原則。假定課程之間不存在時間上的衝突。
【輸入文件】
輸入文件的第一行包括兩個整數N、M（中間用一個空格隔開）其中1≦N≦300,1≦M≦N。
以下N行每行代表一門課。課號依次為1，2，…，N。每行有兩個數（用一個空格隔開），第一個數為這門課先修課的課號（若不存在先修課則該項為0），第二個數為這門課的學分。學分是不超過10的正整數。
【輸出文件】
輸出文件只有一個數,實際所選課程的學分總數。
【輸入樣例】
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
【輸出樣例】
13
【問題分析】
事先說明題目描述有個漏洞，應該是二個以上的課程可能有同一個先修課。
換句話講，一個課程可能是多個課程的先修課，可是一個課最多只有一個先修課。這樣的描述好像和我們以前學過的一種數據結構的描述一樣。
你想對了，就是樹。
因為是建立在樹這種數據結構上的最優化問題，我們自然想到了樹型動態規劃。想到樹型動態規劃，那麼第一步就是想這課樹是否是二叉樹，如果不是，是否需要轉化呢？
顯然這個問題不是二叉樹，有應為問題是在多個課程中選M個，也就是說是樹中一棵或多棵子樹的最優解，這樣問題就需要轉化成二叉樹了。注意題目中說一個課程沒有先修課是0，也就是說這課樹的根是0。
把數據結構確定了以後就要想動態規劃的三要素了。
樹型動態規劃階段的具有共性：樹的層數，
狀態是結點，但是只描述結點顯然不夠，需要在加一個參數。於是我們想到設計一個狀態opt[i,j]表示以i為跟的樹，選j個課程可獲得的最優解。
因為樹是以0為根的而0又必須要選所以問題的解不是opt[0,m]而是opt[0,m+1]。
決策是什麼呢？
對於二叉樹我在設計決策時習慣分類討論這樣結構清晰。
這棵樹只有左子樹：
要選左子樹中的課程，那麼根結點一定要選，所以決策就是在左子樹中選j-1個課程，在加上選根結點可獲得的分數。
這棵樹只有右子樹：
因為右子樹和根在原問題中是兄弟關係，所以選右子樹中的課程未必要選根，這樣決策就有兩條：（1）在右子樹中選j個的最優值。（2）在右子樹中選j-1個的最優值加上選根結點可獲得的分數。
都有：
這種情況的決策很容易想到，從左子樹中選k-1個，從右子樹中選j-k個的最優值加上根結點可獲得的分數。
但要注意，當K=1也就是左子樹選0個時，根結點可以不選，右子樹可以選j個而不是j-1個；當然根結點也可以選，選了根結點右子樹就得選j-1個了。
針對不同情況寫出狀態轉移方程：
max(opt[t[i].L,j-1]+t[i].data) （只有左子樹）
opt[i,j] = max(opt[t[i].r,j-1]+t[i].data, opt[t[i].r,j]) （只有右子樹）
max(opt[t[i].L,k-1]+opt[t[i].r,j-k]+t[i].data,opt[t[i].r,j])（都有）
(1<=ky then max:=x;
end;
function TreeDp(i,j:longint):longint;
var
k:longint;
begin
if opt[i,j]<0 then
begin
if (T[i].L<0) and (T[i].r<0) then
begin
if j1 then opt[i,j]:=0
else opt[i,j]:=T[i].data;
end
else if (T[i].L>=0) and (T[i].r<0) then
opt[i,j]:=max(opt[i,j],TreeDp(T[i].L,j-1)+T[i].data)
else if (T[i].L=0) then
begin
opt[i,j]:=max(opt[i,j],TreeDp(T[i].r,j));
opt[i,j]:=max(opt[i,j],TreeDp(T[i].r,j-1)+T[i].data);
end
else begin
opt[i,j]:=max(opt[i,j],TreeDp(T[i].r,j));
for k:=1 to j do
opt[i,j]:=max(opt[i,j],TreeDp(T[i].L,k-1)+
TreeDp(T[i].r,j-k)+T[i].data);
end;
end;
TreeDp:=opt[i,j];
end;
begin
init;
writeln(TreeDp(0,m+1));
end.
留言
張貼留言