動態(tài)規(guī)劃總結(jié)

by Amber

1.   按狀態(tài)類型分

寫在前面：

從狀態(tài)類型分，并不表示一題只從屬于一類。其實一類只是一種狀態(tài)的表示方法。可以好幾種方法組合成一個狀態(tài)，來解決問題。

1.1. 編號（長度）動態(tài)規(guī)劃

共性總結(jié)

本類的狀態(tài)是基礎(chǔ)的基礎(chǔ)，大部分的動態(tài)規(guī)劃都要用到它，成為一個維。

一般來說，有兩種編號的狀態(tài)：

狀態(tài)(i)表示前i個元素決策組成的一個狀態(tài)。

狀態(tài)(i)表示用到了第i個元素，和其他在1到i-1間的元素，決策組成有的一個狀態(tài)。

題庫

a)       最長不下降子序列

以一元組(i)作為狀態(tài)，表示第i個作為序列的最后一個點的時候的最長序列。于是很容易想到O(n²)得算法。但本題可合理組織狀態(tài)，引入一個單調(diào)的輔助數(shù)組，利用單調(diào)性二分查找，優(yōu)化到O(nlogn)。關(guān)于優(yōu)化詳見優(yōu)化章。

一些問題可將數(shù)據(jù)有序化，轉(zhuǎn)化成本題。

              應(yīng)用：

攔截導彈(NOIP99 Advance 1) 就是原題。

Beautiful People (sgu199)，要將數(shù)據(jù)有序化：其中一個權(quán)作為第一關(guān)鍵字不下降排列，另一個權(quán)作為第二關(guān)鍵字不上升。

              Segment (ural 1078)，將線段的左端點有序化就可以了。

b)      LCS

狀態(tài)(i,j)，表示第1個字符串的第i位，與第2個字符串的第j位匹配，得到的最長的串。若有多個串要LCS，則加維，即幾個串就幾個維。我也將此題歸入路徑問題。

c)      花店櫥窗布置(IOI99)

              見路徑問題。

1.2. 區(qū)間動態(tài)規(guī)劃

共性總結(jié)

       本類問題與下一章的劃分問題的決策的分割點無序交集比較大（占本類問題的30%）。

題庫

a)       石子合并

              見劃分問題

b)      模版匹配(CEOI01,Patten)

              這題特殊的地方是狀態(tài)的值是一個集合而不是一個數(shù)。

c)      不可分解的編碼(ACM World Final 2002)

d)      Electric Path(ural1143)

e)       郵局(IOI2000 Day2 1)

若狀態(tài)表示的思路從第i個村莊可以從屬于哪個郵局，無最優(yōu)子結(jié)構(gòu)。轉(zhuǎn)變一個方向：第k個郵局可以“控制”一個區(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到原點的距離。

              w(i,j)=min{k| Sum{|S(k)-S(p)|}(i<=p<=j)}(i<=k<=j) 找到[i,j]間最好的一個郵局點。

       不過可以發(fā)現(xiàn)Sum{|S(k)-S(p)|是單調(diào)的，所以取中位數(shù)就可以了。即上式中k的取值范圍只有floor((i+j)/2), ceil((i+j)/2)兩個。Floor是下取整。Ceil是上取整。這樣每次轉(zhuǎn)移時間降到O(1)。

注意到是區(qū)間連續(xù)的，即(p,i-1) 和(i, j) 中的 i-1, i是連續(xù)的，所以空間可以降維：f(i,j)表示放前i個郵局到前j個村莊的最優(yōu)值。

              f(i,j)=min{f(i-1,p-1)+w(p,j)}(i-1<=p<=j-1}

              e(i,j) 為當f(i,j)到達最優(yōu)值時的p.

              通過證明四邊形不等式，得到e(i,j)<=e(i,j+1)<=e(i+1,j+1)

              決策數(shù)量又少了一個數(shù)量級。

1.3. 坐標動態(tài)規(guī)劃

共性總結(jié)

之后的一些問題，狀態(tài)是由坐標維與其他的維組成。本類與劃分問題(是2維或多維的坐標系的劃分)與路徑問題的交集占本類問題中大多數(shù)。

題庫

a)       棋盤分割(NOI99 4)

主要是將公式變形，變形后的公式很容易看出方程。

狀態(tài)是由2個坐標組成的4元組(x1,y1)(x2,y2)，表示一個子棋盤。這有點像之前的區(qū)間動態(tài)規(guī)劃，只不過是將1維轉(zhuǎn)2維。

后見路徑問題。

1.4. 數(shù)軸動態(tài)規(guī)劃

共性總結(jié)

 

       題庫

a)       01背包

              應(yīng)用：

       裝箱問題（NOIP01 Trade 4）

就是原題。

值幣分割

              可利用方程的性質(zhì)，空間降1維。

幣值可重復的值幣分割(pku1742, Problem F LouTianCheng’s Contest in POJ)

使用左右法在定位上加速。

另給狀態(tài)加一個屬性last,記錄上一次剩下的可用的同幣值硬幣數(shù)（利用了當前轉(zhuǎn)移是唯一前驅(qū)的特點）。

b)      取火柴問題(sgu153 Playing with matches)

             

c)      Stone Pile(ural1005 Stone Pile)

d)      公路巡邏(CTSC2000)

1.5. 5.樹型動態(tài)規(guī)劃

共性總結(jié)

1）  動態(tài)規(guī)劃的順序

一般按照后序遍歷的順序，即處理完兒子再處理當前節(jié)點，才符合樹的子結(jié)構(gòu)的性質(zhì)。

2）  多叉樹轉(zhuǎn)換為二叉樹

由于要分配附加維到各個節(jié)點，而分配附加維是個劃分問題，若還是按當前節(jié)點到各個兒子節(jié)點分配，則成了一個整數(shù)劃分問題,O(n_­²)。所以要把多叉樹轉(zhuǎn)換為二叉樹，這樣才能按動態(tài)規(guī)劃的方式只決策當前點的分配問題, O(n_­)。

3）  加當前點的選或不選的常數(shù)維

              加此維解決的是后效性問題。

……………………

4）  在將邊信息轉(zhuǎn)成樹時的技巧

將讀入的邊分裂成2條邊，將這2條邊關(guān)聯(lián)起來（就是找到一條邊，另一條邊的編號就知道）。用前向星表示法表示邊（按起點有序），以后用邊的時候，用了一條邊打不可用標志，也將關(guān)聯(lián)邊打不可用標志。這樣可以保證O(n)的時間完成信息處理，而且在父節(jié)點找兒子的過程中帶來很大的方便。

5）  復雜度

樹型動態(tài)規(guī)劃復雜度基本上是O(n)；若有附加維m，則是O(nm)。

題庫

a)       選課(CTSC97-3)

              由于要分配課程數(shù)，所以要多叉樹轉(zhuǎn)換為二叉樹。

b)      貪吃的九頭龍(NOI02-3)

              若小頭數(shù)大于1的話，則讓不同的小頭吃一段樹枝的2個端點。

              這樣就把問題轉(zhuǎn)化成：附加維是大頭吃的個數(shù)，當前點由不由大頭吃的常數(shù)維的動態(tài)規(guī)劃。由于涉及劃分問題，所以要多叉樹轉(zhuǎn)換為二叉樹。

c)      求樹的質(zhì)心(sgu134 Centroid)

給出一棵邊不帶權(quán)的樹，求點,使得去掉此點后,剩下的最大的連通子圖的頂點數(shù)最小.

d)      求樹中的點最遠距離最近。

給出一棵邊帶權(quán)的樹，求樹中的點，使得此點到樹中的其他結(jié)點的最遠距離最近。

Computer Network (sgu149)

Computer Net (ural1056)

1.6. 集合動態(tài)規(guī)劃（狀態(tài)壓縮）

共性總結(jié)

1)      數(shù)據(jù)特殊性

              給出的數(shù)據(jù)在某一個或幾個維度上一般具有比較小的范圍（可以枚舉一類的狀態(tài)）。

              一個枚舉的狀態(tài)是一個集合。

2)      編碼

由于集合中元素個數(shù)的不定性或范圍大，直接開數(shù)組存，不好索引數(shù)組（編程復雜度太高），所以要將集合編碼。

利用數(shù)據(jù)的可枚舉性，將枚舉的狀態(tài)(集合)編碼。一般來說碼值的范圍要很小（盡量排除無用的碼值，如炮兵：當前格和上格存在炮兵的情況是非法的，可以排除）。

規(guī)定編碼的碼值代表的意思，要盡量規(guī)定好維護的碼值。（如炮兵：當前格存在炮兵的用2，上格存在炮兵用1。這樣下一層的規(guī)劃時，只要碼值-1即可）。

有時候可以直接利用編碼的順序動態(tài)規(guī)劃，因為這時編碼已經(jīng)是拓補有序。如TSP問題當前已選點集合的狀態(tài)的前驅(qū)的編碼的值一定比當前的編碼的值小。

3)      狀態(tài)壓縮

對有限階段的放置情況，行走情況編碼（其實質(zhì)也是放置的集合或行走路線的集合），這樣的編碼，也有人謂之：“狀態(tài)壓縮”。此類題以“炮兵陣地”為典型，進行擴展。

題庫

a)       購物（IOI95-2）

              可將每種物品按5進制編碼。（5為每種物品數(shù)的上限）

       由于物品數(shù)的上限為5，比較小，也可直接開數(shù)組存。

b)      Roger游戲任務(wù)一（CTSC98 Day2 4）

              一個正方體在一個方格內(nèi)的狀態(tài)只有24種，而且可以通過頂面和前面來表示，這樣用3維的狀態(tài)(x,y,p)就可以解決，p為1到24種狀態(tài)中的一種。

c)      TSP問題

觀察一下TSP的搜索過程： for (x in 未選點) TSP(x)

即當前路的最后一個節(jié)點為x,現(xiàn)在要選擇下一個節(jié)點y,而y要在未選點的集合中。若未選點或已選點的集合已確定，則后效性消除。可以DP。狀態(tài)為令X為當前路的已選點的集合(含i)，當前路的最后一個節(jié)點為i。2元組(X,i)為經(jīng)過已選點的集合X到節(jié)點i的最短長度。將X編碼即可。

注意：并沒有因為動態(tài)規(guī)劃將問題從NP類帶到P類。

應(yīng)用: DNA Laboratory(Problem B,TU-Darmstadt Programming Contest 2004)

將每個串的交迭部分求出，就可以將問題專成TSP

但要輸出字典序最小的，則需要注意DP順序。

有具體的報告。

d)      炮兵陣地

十分經(jīng)典，詳見報告。

應(yīng)用:

Another Chocolate Maniac(sgu132) 類似炮兵的做法的最值，只不過是求最小值，麻煩點。

Hardwood floor(sgu131) 類似炮兵的做法的統(tǒng)計

Little Knights(sgu225) 類似炮兵的做法的統(tǒng)計,數(shù)據(jù)量太大要const

Little Kings(sgu223) 類似炮兵的做法的統(tǒng)計

Bugs公司(CEOI 2002) 類似炮兵的做法的最值

1.7. 利用動態(tài)規(guī)劃思想求最值，編號（循環(huán)變量）的迭代

共性總結(jié)

       要利用上次的一些運算“剩下”的循環(huán)變量作當前循環(huán)的邊界，主要在于找出一種決策順序，使之成立。

題庫

a)       奶牛浴場

      

b)      Communication System

將數(shù)據(jù)有序化, 從大到小枚舉帶寬, 每次可利用上次處理的結(jié)果Min, 來決策當前狀態(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)計(CTSC99 1)

2)卡特蘭數(shù)

circle(sgu130)

       3)鷹蛋

2.2. 求一系列的分割（合并）點（劃分問題）

2.2.1.    決策的分割點有序

共性總結(jié)

a)       有序性

              每次決策的點的編號是有序的，即要按決策的順序輸出分割點的編號的話，編號是有序的，滿足分割點的編號按升序排列。

b)      方程一般形式

              f(n,m)=optimize{f(k,m-1)+w(k+1,n)}

              (n,m)表示從1到n個點中劃分為m個部分的最優(yōu)值；k為決策的分割點，即第m個部分為k+1到n；這里optimize可以為max,min。

題庫

a)       整數(shù)劃分

常應(yīng)用在將一個權(quán)分配給一定的小分割塊，如：將大堆的石子分成一定的小堆，小堆可為空，大堆要分完。有時應(yīng)用在樹型動態(tài)規(guī)劃（二叉轉(zhuǎn)多叉）中。

b)      乘積最大(NOIP00 Advance 2)

              就是按上面的一般式的方程做。

 

2.2.2.          決策的分割點無序

共性總結(jié)

a)       無序性

       每次決策的點的編號是無序的，即要按決策的遞歸順序輸出分割點的編號的話，編號是無序的。

b)      方程一般形式

       f(i,j)=optimize{f(i,k-1)+f(k+1,j)}+w(i,j)

       (i,j)表示從i到j的范圍內(nèi)選取一個分割點k的最優(yōu)值，子問題是分割點左邊(i,k-1)和右邊(k+1,j)的點的范圍的最優(yōu)值；這里optimize可以為max,min。

       方程很類似2叉樹的性質(zhì)。

c)      四邊形不等式

此類的問題，有些可用四邊形不等式優(yōu)化。見優(yōu)化章。

題庫

a)       石子合并(NOI95 2)

經(jīng)典，詳見報告。

可用四邊形不等式優(yōu)化成O(n²)

其實還可以用類似堆的數(shù)據(jù)結(jié)構(gòu)在O(nlogn)的時間內(nèi)完成，但這就不是動態(tài)規(guī)劃了。

應(yīng)用：

構(gòu)造最優(yōu)二叉排序樹(CTSC96 2)

 

b)      多邊形(IOI98)

這題值的正負號處理要注意，乘法運算，由于符號的加入，使原本的正的最優(yōu)解，一下變成負的。

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)

       這題的分割點不是一個元素，而是元素間的一條線。

       主要的思維方式是從遞歸定義。

2.3. 路徑問題

共性總結(jié)

a)       行走方向決定階段性

有規(guī)定源點與終點。每次行走方向都有一定的規(guī)定，使原點到終點的所有路徑形成無環(huán)有向圖。

b)      多源或多匯

當多源或多匯時，應(yīng)該加維，使得每個源，都有一個路徑的狀態(tài)與之對應(yīng)。如有n個源的網(wǎng)格類問題，常常轉(zhuǎn)態(tài)是(x1,y1)(x2,y2)…(xn,yn)。但是源太多的話，空間上不允許，可以降問題轉(zhuǎn)成網(wǎng)絡(luò)流問題。

c)      雙向動態(tài)規(guī)劃

由于有規(guī)定源點與終點，可以雙向動態(tài)規(guī)劃，但要考慮效果好不好，理論上是比原來少1/2，但有時由于可用于決策的狀態(tài)較少，效果就不錯了。

d)      決策稀疏性

就是所謂走法，若對于一個狀態(tài)，它的前驅(qū)或者后繼數(shù)很少(從無環(huán)有向圖角度，就是入度或出度少)，稱決策稀疏。

e)       狀態(tài)稀疏性

就是很多狀態(tài)是沒有用的，如排列的LCS,狀態(tài)為2維的(x,y)，但對于一個x只有一個y是有效個。所以實質(zhì)上狀態(tài)數(shù)還是線形的。

本類一些技巧性的東西較多，在題庫中具體說明。

題庫

a)       方格取數(shù)(NOIP00 advance 4)

       (x1,y1)(x2,y2)

       對角線空間優(yōu)化

b)      花店櫥窗布置(IOI99)

      

       我對本題有個小改造：若花瓶無序，如何做，有序指：對于花束i<花束j, 花束i對應(yīng)的花瓶編號<花束j對應(yīng)的花瓶編號。那么這樣就是一個NP問題了，可用后面的基于狀態(tài)壓縮的動態(tài)規(guī)劃解決。

 

3.   動態(tài)規(guī)劃的優(yōu)化

3.1. 迭代

3.2. 四邊形

3.3. 凸性的優(yōu)化