動態(tài)規(guī)劃總結(jié)
by Amber
1. 按狀態(tài)類型分
寫在前面：
從狀態(tài)類型分，并不表示一題只從屬于一類。其實(shí)一類只是一種狀態(tài)的表示方法。可以好幾種方法組合成一個(gè)狀態(tài)，來解決問題。
1.1. 編號（長度）動態(tài)規(guī)劃
共性總結(jié)
本類的狀態(tài)是基礎(chǔ)的基礎(chǔ)，大部分的動態(tài)規(guī)劃都要用到它，成為一個(gè)維。
一般來說，有兩種編號的狀態(tài)：
狀態(tài)(i)表示前i個(gè)元素決策組成的一個(gè)狀態(tài)。
狀態(tài)(i)表示用到了第i個(gè)元素，和其他在1到i-1間的元素，決策組成有的一個(gè)狀態(tài)。
題庫
a) 最長不下降子序列
以一元組(i)作為狀態(tài)，表示第i個(gè)作為序列的最后一個(gè)點(diǎn)的時(shí)候的最長序列。于是很容易想到O(n2)得算法。但本題可合理組織狀態(tài)，引入一個(gè)單調(diào)的輔助數(shù)組，利用單調(diào)性二分查找，優(yōu)化到O(nlogn)。關(guān)于優(yōu)化詳見優(yōu)化章。
一些問題可將數(shù)據(jù)有序化，轉(zhuǎn)化成本題。
應(yīng)用：
攔截導(dǎo)彈(NOIP99 Advance 1) 就是原題。
Beautiful People (sgu199)，要將數(shù)據(jù)有序化：其中一個(gè)權(quán)作為第一關(guān)鍵字不下降排列，另一個(gè)權(quán)作為第二關(guān)鍵字不上升。
Segment (ural 1078)，將線段的左端點(diǎn)有序化就可以了。
b) LCS
狀態(tài)(i,j)，表示第1個(gè)字符串的第i位，與第2個(gè)字符串的第j位匹配，得到的最長的串。若有多個(gè)串要LCS，則加維，即幾個(gè)串就幾個(gè)維。我也將此題歸入路徑問題。
c) 花店櫥窗布置(IOI99)
見路徑問題。
1.2. 區(qū)間動態(tài)規(guī)劃
共性總結(jié)
本類問題與下一章的劃分問題的決策的分割點(diǎn)無序交集比較大（占本類問題的30%）。
題庫
a) 石子合并
見劃分問題
b) 模版匹配(CEOI01,Patten)
這題特殊的地方是狀態(tài)的值是一個(gè)集合而不是一個(gè)數(shù)。
c) 不可分解的編碼(ACM World Final 2002)
d) Electric Path(ural1143)
e) 郵局(IOI2000 Day2 1)
若狀態(tài)表示的思路從第i個(gè)村莊可以從屬于哪個(gè)郵局，無最優(yōu)子結(jié)構(gòu)。轉(zhuǎn)變一個(gè)方向：第k個(gè)郵局可以“控制”一個(gè)區(qū)間的村莊[i,j]。于是方程就顯然了:
f(k,i,j)=min{f(k-1,p,i-1)+w(i,j)}(k-1<=p<=i-1)
S(i) 為村莊i到原點(diǎn)的距離。
w(i,j)=min{k| Sum{|S(k)-S(p)|}(i<=p<=j)}(i<=k<=j) 找到[i,j]間最好的一個(gè)郵局點(diǎn)。
不過可以發(fā)現(xiàn)Sum{|S(k)-S(p)|是單調(diào)的，所以取中位數(shù)就可以了。即上式中k的取值范圍只有floor((i+j)/2), ceil((i+j)/2)兩個(gè)。Floor是下取整。Ceil是上取整。這樣每次轉(zhuǎn)移時(shí)間降到O(1)。
注意到是區(qū)間連續(xù)的，即(p,i-1) 和(i, j) 中的 i-1, i是連續(xù)的，所以空間可以降維：f(i,j)表示放前i個(gè)郵局到前j個(gè)村莊的最優(yōu)值。
f(i,j)=min{f(i-1,p-1)+w(p,j)}(i-1<=p<=j-1}
e(i,j) 為當(dāng)f(i,j)到達(dá)最優(yōu)值時(shí)的p.
通過證明四邊形不等式，得到e(i,j)<=e(i,j+1)<=e(i+1,j+1)
決策數(shù)量又少了一個(gè)數(shù)量級。
1.3. 坐標(biāo)動態(tài)規(guī)劃
共性總結(jié)
之后的一些問題，狀態(tài)是由坐標(biāo)維與其他的維組成。本類與劃分問題(是2維或多維的坐標(biāo)系的劃分)與路徑問題的交集占本類問題中大多數(shù)。
題庫
a) 棋盤分割(NOI99 4)
主要是將公式變形，變形后的公式很容易看出方程。
狀態(tài)是由2個(gè)坐標(biāo)組成的4元組(x1,y1)(x2,y2)，表示一個(gè)子棋盤。這有點(diǎn)像之前的區(qū)間動態(tài)規(guī)劃，只不過是將1維轉(zhuǎn)2維。
后見路徑問題。
1.4. 數(shù)軸動態(tài)規(guī)劃
共性總結(jié)
題庫
a) 01背包
應(yīng)用：
裝箱問題（NOIP01 Trade 4）
就是原題。
值幣分割
可利用方程的性質(zhì)，空間降1維。
幣值可重復(fù)的值幣分割(pku1742, Problem F LouTianCheng’s Contest in POJ)
使用左右法在定位上加速。
另給狀態(tài)加一個(gè)屬性last,記錄上一次剩下的可用的同幣值硬幣數(shù)（利用了當(dāng)前轉(zhuǎn)移是唯一前驅(qū)的特點(diǎn)）。
b) 取火柴問題(sgu153 Playing with matches)
c) Stone Pile(ural1005 Stone Pile)
d) 公路巡邏(CTSC2000)
1.5. 5.樹型動態(tài)規(guī)劃
共性總結(jié)
1） 動態(tài)規(guī)劃的順序
一般按照后序遍歷的順序，即處理完兒子再處理當(dāng)前節(jié)點(diǎn)，才符合樹的子結(jié)構(gòu)的性質(zhì)。
2） 多叉樹轉(zhuǎn)換為二叉樹
由于要分配附加維到各個(gè)節(jié)點(diǎn)，而分配附加維是個(gè)劃分問題，若還是按當(dāng)前節(jié)點(diǎn)到各個(gè)兒子節(jié)點(diǎn)分配，則成了一個(gè)整數(shù)劃分問題,O(n2)。所以要把多叉樹轉(zhuǎn)換為二叉樹，這樣才能按動態(tài)規(guī)劃的方式只決策當(dāng)前點(diǎn)的分配問題, O(n)。
3） 加當(dāng)前點(diǎn)的選或不選的常數(shù)維
加此維解決的是后效性問題。
……………………
4） 在將邊信息轉(zhuǎn)成樹時(shí)的技巧
將讀入的邊分裂成2條邊，將這2條邊關(guān)聯(lián)起來（就是找到一條邊，另一條邊的編號就知道）。用前向星表示法表示邊（按起點(diǎn)有序），以后用邊的時(shí)候，用了一條邊打不可用標(biāo)志，也將關(guān)聯(lián)邊打不可用標(biāo)志。這樣可以保證O(n)的時(shí)間完成信息處理，而且在父節(jié)點(diǎn)找兒子的過程中帶來很大的方便。
5） 復(fù)雜度
樹型動態(tài)規(guī)劃復(fù)雜度基本上是O(n)；若有附加維m，則是O(nm)。
題庫
a) 選課(CTSC97-3)
由于要分配課程數(shù)，所以要多叉樹轉(zhuǎn)換為二叉樹。
b) 貪吃的九頭龍(NOI02-3)
若小頭數(shù)大于1的話，則讓不同的小頭吃一段樹枝的2個(gè)端點(diǎn)。
這樣就把問題轉(zhuǎn)化成：附加維是大頭吃的個(gè)數(shù)，當(dāng)前點(diǎn)由不由大頭吃的常數(shù)維的動態(tài)規(guī)劃。由于涉及劃分問題，所以要多叉樹轉(zhuǎn)換為二叉樹。
c) 求樹的質(zhì)心(sgu134 Centroid)
給出一棵邊不帶權(quán)的樹，求點(diǎn),使得去掉此點(diǎn)后,剩下的最大的連通子圖的頂點(diǎn)數(shù)最小.
d) 求樹中的點(diǎn)最遠(yuǎn)距離最近。
給出一棵邊帶權(quán)的樹，求樹中的點(diǎn)，使得此點(diǎn)到樹中的其他結(jié)點(diǎn)的最遠(yuǎn)距離最近。
Computer Network (sgu149)
Computer Net (ural1056)
1.6. 集合動態(tài)規(guī)劃（狀態(tài)壓縮）
共性總結(jié)
1) 數(shù)據(jù)特殊性
給出的數(shù)據(jù)在某一個(gè)或幾個(gè)維度上一般具有比較小的范圍（可以枚舉一類的狀態(tài)）。
一個(gè)枚舉的狀態(tài)是一個(gè)集合。
2) 編碼
由于集合中元素個(gè)數(shù)的不定性或范圍大，直接開數(shù)組存，不好索引數(shù)組（編程復(fù)雜度太高），所以要將集合編碼。
利用數(shù)據(jù)的可枚舉性，將枚舉的狀態(tài)(集合)編碼。一般來說碼值的范圍要很小（盡量排除無用的碼值，如炮兵：當(dāng)前格和上格存在炮兵的情況是非法的，可以排除）。
規(guī)定編碼的碼值代表的意思，要盡量規(guī)定好維護(hù)的碼值。（如炮兵：當(dāng)前格存在炮兵的用2，上格存在炮兵用1。這樣下一層的規(guī)劃時(shí)，只要碼值-1即可）。
有時(shí)候可以直接利用編碼的順序動態(tài)規(guī)劃，因?yàn)檫@時(shí)編碼已經(jīng)是拓補(bǔ)有序。如TSP問題當(dāng)前已選點(diǎn)集合的狀態(tài)的前驅(qū)的編碼的值一定比當(dāng)前的編碼的值小。
3) 狀態(tài)壓縮
對有限階段的放置情況，行走情況編碼（其實(shí)質(zhì)也是放置的集合或行走路線的集合），這樣的編碼，也有人謂之：“狀態(tài)壓縮”。此類題以“炮兵陣地”為典型，進(jìn)行擴(kuò)展。
題庫
a) 購物（IOI95-2）
可將每種物品按5進(jìn)制編碼。（5為每種物品數(shù)的上限）
由于物品數(shù)的上限為5，比較小，也可直接開數(shù)組存。
b) Roger游戲任務(wù)一（CTSC98 Day2 4）
一個(gè)正方體在一個(gè)方格內(nèi)的狀態(tài)只有24種，而且可以通過頂面和前面來表示，這樣用3維的狀態(tài)(x,y,p)就可以解決，p為1到24種狀態(tài)中的一種。
c) TSP問題
觀察一下TSP的搜索過程： for (x in 未選點(diǎn)) TSP(x)
即當(dāng)前路的最后一個(gè)節(jié)點(diǎn)為x,現(xiàn)在要選擇下一個(gè)節(jié)點(diǎn)y,而y要在未選點(diǎn)的集合中。若未選點(diǎn)或已選點(diǎn)的集合已確定，則后效性消除。可以DP。狀態(tài)為令X為當(dāng)前路的已選點(diǎn)的集合(含i)，當(dāng)前路的最后一個(gè)節(jié)點(diǎn)為i。2元組(X,i)為經(jīng)過已選點(diǎn)的集合X到節(jié)點(diǎn)i的最短長度。將X編碼即可。
注意：并沒有因?yàn)閯討B(tài)規(guī)劃將問題從NP類帶到P類。
應(yīng)用: DNA Laboratory(Problem B,TU-Darmstadt Programming Contest 2004)
將每個(gè)串的交迭部分求出，就可以將問題專成TSP
但要輸出字典序最小的，則需要注意DP順序。
有具體的報(bào)告。
d) 炮兵陣地
十分經(jīng)典，詳見報(bào)告。
應(yīng)用:
Another Chocolate Maniac(sgu132) 類似炮兵的做法的最值，只不過是求最小值，麻煩點(diǎn)。
Hardwood floor(sgu131) 類似炮兵的做法的統(tǒng)計(jì)
Little Knights(sgu225) 類似炮兵的做法的統(tǒng)計(jì),數(shù)據(jù)量太大要const
Little Kings(sgu223) 類似炮兵的做法的統(tǒng)計(jì)
Bugs公司(CEOI 2002) 類似炮兵的做法的最值
1.7. 利用動態(tài)規(guī)劃思想求最值，編號（循環(huán)變量）的迭代
共性總結(jié)
要利用上次的一些運(yùn)算“剩下”的循環(huán)變量作當(dāng)前循環(huán)的邊界，主要在于找出一種決策順序，使之成立。
題庫
a) 奶牛浴場
b) Communication System
將數(shù)據(jù)有序化, 從大到小枚舉帶寬, 每次可利用上次處理的結(jié)果Min, 來決策當(dāng)前狀態(tài)。稱作迭代, 或就是一種動態(tài)規(guī)劃。
(zju1409, Problem C Tehran 2002 Iran Nationwide Internet Programming Contest)
1.8. 記憶化搜索
題庫
a) Magic Trick (Problem G, TU-Darmstadt Programming Contest 2004)
2. 按轉(zhuǎn)移方式分
2.1. 存在性
遞推
1)01統(tǒng)計(jì)(CTSC99 1)
2)卡特蘭數(shù)
circle(sgu130)
3)鷹蛋
2.2. 求一系列的分割（合并）點(diǎn)（劃分問題）
2.2.1. 決策的分割點(diǎn)有序
共性總結(jié)
a) 有序性
每次決策的點(diǎn)的編號是有序的，即要按決策的順序輸出分割點(diǎn)的編號的話，編號是有序的，滿足分割點(diǎn)的編號按升序排列。
b) 方程一般形式
f(n,m)=optimize{f(k,m-1)+w(k+1,n)}
(n,m)表示從1到n個(gè)點(diǎn)中劃分為m個(gè)部分的最優(yōu)值；k為決策的分割點(diǎn)，即第m個(gè)部分為k+1到n；這里optimize可以為max,min。
題庫
a) 整數(shù)劃分
常應(yīng)用在將一個(gè)權(quán)分配給一定的小分割塊，如：將大堆的石子分成一定的小堆，小堆可為空，大堆要分完。有時(shí)應(yīng)用在樹型動態(tài)規(guī)劃（二叉轉(zhuǎn)多叉）中。
b) 乘積最大(NOIP00 Advance 2)
就是按上面的一般式的方程做。
2.2.2. 決策的分割點(diǎn)無序
共性總結(jié)
a) 無序性
每次決策的點(diǎn)的編號是無序的，即要按決策的遞歸順序輸出分割點(diǎn)的編號的話，編號是無序的。
b) 方程一般形式
f(i,j)=optimize{f(i,k-1)+f(k+1,j)}+w(i,j)
(i,j)表示從i到j的范圍內(nèi)選取一個(gè)分割點(diǎn)k的最優(yōu)值，子問題是分割點(diǎn)左邊(i,k-1)和右邊(k+1,j)的點(diǎn)的范圍的最優(yōu)值；這里optimize可以為max,min。
方程很類似2叉樹的性質(zhì)。
c) 四邊形不等式
此類的問題，有些可用四邊形不等式優(yōu)化。見優(yōu)化章。
題庫
a) 石子合并(NOI95 2)
經(jīng)典，詳見報(bào)告。
可用四邊形不等式優(yōu)化成O(n2)
其實(shí)還可以用類似堆的數(shù)據(jù)結(jié)構(gòu)在O(nlogn)的時(shí)間內(nèi)完成，但這就不是動態(tài)規(guī)劃了。
應(yīng)用：
構(gòu)造最優(yōu)二叉排序樹(CTSC96 2)
b) 多邊形(IOI98)
這題值的正負(fù)號處理要注意，乘法運(yùn)算，由于符號的加入，使原本的正的最優(yōu)解，一下變成負(fù)的。
c) 加分二叉樹(NOIP03 Advance 3)
方程就是一般式，轉(zhuǎn)移的函數(shù)：w(i,j)=sum(i,k-1)*sum(k+1,j)+d(k)。由于w(i,j)不滿足凸單調(diào)性，所以不能用四邊形不等式優(yōu)化。
d) 括號序列(Problem B, NEERC 2001)
這題的分割點(diǎn)不是一個(gè)元素，而是元素間的一條線。
主要的思維方式是從遞歸定義。
2.3. 路徑問題
共性總結(jié)
a) 行走方向決定階段性
有規(guī)定源點(diǎn)與終點(diǎn)。每次行走方向都有一定的規(guī)定，使原點(diǎn)到終點(diǎn)的所有路徑形成無環(huán)有向圖。
b) 多源或多匯
當(dāng)多源或多匯時(shí)，應(yīng)該加維，使得每個(gè)源，都有一個(gè)路徑的狀態(tài)與之對應(yīng)。如有n個(gè)源的網(wǎng)格類問題，常常轉(zhuǎn)態(tài)是(x1,y1)(x2,y2)…(xn,yn)。但是源太多的話，空間上不允許，可以降問題轉(zhuǎn)成網(wǎng)絡(luò)流問題。
c) 雙向動態(tài)規(guī)劃
由于有規(guī)定源點(diǎn)與終點(diǎn)，可以雙向動態(tài)規(guī)劃，但要考慮效果好不好，理論上是比原來少1/2，但有時(shí)由于可用于決策的狀態(tài)較少，效果就不錯(cuò)了。
d) 決策稀疏性
就是所謂走法，若對于一個(gè)狀態(tài)，它的前驅(qū)或者后繼數(shù)很少(從無環(huán)有向圖角度，就是入度或出度少)，稱決策稀疏。
e) 狀態(tài)稀疏性
就是很多狀態(tài)是沒有用的，如排列的LCS,狀態(tài)為2維的(x,y)，但對于一個(gè)x只有一個(gè)y是有效個(gè)。所以實(shí)質(zhì)上狀態(tài)數(shù)還是線形的。
本類一些技巧性的東西較多，在題庫中具體說明。
題庫
a) 方格取數(shù)(NOIP00 advance 4)
(x1,y1)(x2,y2)
對角線空間優(yōu)化
b) 花店櫥窗布置(IOI99)
我對本題有個(gè)小改造：若花瓶無序，如何做，有序指：對于花束i<花束j, 花束i對應(yīng)的花瓶編號<花束j對應(yīng)的花瓶編號。那么這樣就是一個(gè)NP問題了，可用后面的基于狀態(tài)壓縮的動態(tài)規(guī)劃解決。
3. 動態(tài)規(guī)劃的優(yōu)化
3.1. 迭代
3.2. 四邊形
3.3. 凸性的優(yōu)化