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

by Amber

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

寫(xiě)在前面：

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

1.1. 編號(hào)（長(zhǎng)度）動(dòng)態(tài)規(guī)劃

共性總結(jié)

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

一般來(lái)說(shuō)，有兩種編號(hào)的狀態(tài)：

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

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

題庫(kù)

a)       最長(zhǎng)不下降子序列

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

一些問(wèn)題可將數(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位匹配，得到的最長(zhǎng)的串。若有多個(gè)串要LCS，則加維，即幾個(gè)串就幾個(gè)維。我也將此題歸入路徑問(wèn)題。

c)      花店櫥窗布置(IOI99)

              見(jiàn)路徑問(wèn)題。

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

共性總結(jié)

       本類(lèi)問(wèn)題與下一章的劃分問(wèn)題的決策的分割點(diǎn)無(wú)序交集比較大（占本類(lèi)問(wèn)題的30%）。

題庫(kù)

a)       石子合并

              見(jiàn)劃分問(wèn)題

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è)郵局，無(wú)最優(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)。

       不過(guò)可以發(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.

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

              決策數(shù)量又少了一個(gè)數(shù)量級(jí)。

1.3. 坐標(biāo)動(dòng)態(tài)規(guī)劃

共性總結(jié)

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

題庫(kù)

a)       棋盤(pán)分割(NOI99 4)

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

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

后見(jiàn)路徑問(wèn)題。

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

共性總結(jié)

 

       題庫(kù)

a)       01背包

              應(yīng)用：

       裝箱問(wèn)題（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)      取火柴問(wèn)題(sgu153 Playing with matches)

             

c)      Stone Pile(ural1005 Stone Pile)

d)      公路巡邏(CTSC2000)

1.5. 5.樹(shù)型動(dòng)態(tài)規(guī)劃

共性總結(jié)

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

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

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

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

3）  加當(dāng)前點(diǎn)的選或不選的常數(shù)維

              加此維解決的是后效性問(wèn)題。

……………………

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

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

5）  復(fù)雜度

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

題庫(kù)

a)       選課(CTSC97-3)

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

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

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

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

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

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

d)      求樹(shù)中的點(diǎn)最遠(yuǎn)距離最近。

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

Computer Network (sgu149)

Computer Net (ural1056)

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

共性總結(jié)

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

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

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

2)      編碼

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

利用數(shù)據(jù)的可枚舉性，將枚舉的狀態(tài)(集合)編碼。一般來(lái)說(shuō)碼值的范圍要很?。ūM量排除無(wú)用的碼值，如炮兵：當(dāng)前格和上格存在炮兵的情況是非法的，可以排除）。

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

有時(shí)候可以直接利用編碼的順序動(dòng)態(tài)規(guī)劃，因?yàn)檫@時(shí)編碼已經(jīng)是拓補(bǔ)有序。如TSP問(wèn)題當(dāng)前已選點(diǎn)集合的狀態(tài)的前驅(qū)的編碼的值一定比當(dāng)前的編碼的值小。

3)      狀態(tài)壓縮

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

題庫(kù)

a)       購(gòu)物（IOI95-2）

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

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

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

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

c)      TSP問(wèn)題

觀察一下TSP的搜索過(guò)程： 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)的集合已確定，則后效性消除?？梢?/span>DP。狀態(tài)為令X為當(dāng)前路的已選點(diǎn)的集合(含i)，當(dāng)前路的最后一個(gè)節(jié)點(diǎn)為i。2元組(X,i)為經(jīng)過(guò)已選點(diǎn)的集合X到節(jié)點(diǎn)i的最短長(zhǎng)度。將X編碼即可。

注意：并沒(méi)有因?yàn)閯?dòng)態(tài)規(guī)劃將問(wèn)題從NP類(lèi)帶到P類(lèi)。

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

將每個(gè)串的交迭部分求出，就可以將問(wèn)題專(zhuān)成TSP

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

有具體的報(bào)告。

d)      炮兵陣地

十分經(jīng)典，詳見(jiàn)報(bào)告。

應(yīng)用:

Another Chocolate Maniac(sgu132) 類(lèi)似炮兵的做法的最值，只不過(guò)是求最小值，麻煩點(diǎn)。

Hardwood floor(sgu131) 類(lèi)似炮兵的做法的統(tǒng)計(jì)

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

Little Kings(sgu223) 類(lèi)似炮兵的做法的統(tǒng)計(jì)

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

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

共性總結(jié)

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

題庫(kù)

a)       奶牛浴場(chǎng)

      

b)      Communication System

將數(shù)據(jù)有序化, 從大到小枚舉帶寬, 每次可利用上次處理的結(jié)果Min, 來(lái)決策當(dāng)前狀態(tài)。稱(chēng)作迭代, 或就是一種動(dòng)態(tài)規(guī)劃。

(zju1409, Problem C Tehran 2002 Iran Nationwide Internet Programming Contest)

1.8. 記憶化搜索

題庫(kù)

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)（劃分問(wèn)題）

2.2.1.    決策的分割點(diǎn)有序

共性總結(jié)

a)       有序性

              每次決策的點(diǎn)的編號(hào)是有序的，即要按決策的順序輸出分割點(diǎn)的編號(hào)的話，編號(hào)是有序的，滿足分割點(diǎn)的編號(hào)按升序排列。

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。

題庫(kù)

a)       整數(shù)劃分

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

b)      乘積最大(NOIP00 Advance 2)

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

 

2.2.2.          決策的分割點(diǎn)無(wú)序

共性總結(jié)

a)       無(wú)序性

       每次決策的點(diǎn)的編號(hào)是無(wú)序的，即要按決策的遞歸順序輸出分割點(diǎn)的編號(hào)的話，編號(hào)是無(wú)序的。

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)值，子問(wèn)題是分割點(diǎn)左邊(i,k-1)和右邊(k+1,j)的點(diǎn)的范圍的最優(yōu)值；這里optimize可以為max,min。

       方程很類(lèi)似2叉樹(shù)的性質(zhì)。

c)      四邊形不等式

此類(lèi)的問(wèn)題，有些可用四邊形不等式優(yōu)化。見(jiàn)優(yōu)化章。

題庫(kù)

a)       石子合并(NOI95 2)

經(jīng)典，詳見(jiàn)報(bào)告。

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

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

應(yīng)用：

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

 

b)      多邊形(IOI98)

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

c)      加分二叉樹(shù)(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)      括號(hào)序列(Problem B, NEERC 2001)

       這題的分割點(diǎn)不是一個(gè)元素，而是元素間的一條線。

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

2.3. 路徑問(wèn)題

共性總結(jié)

a)       行走方向決定階段性

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

b)      多源或多匯

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

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

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

d)      決策稀疏性

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

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

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

本類(lèi)一些技巧性的東西較多，在題庫(kù)中具體說(shuō)明。

題庫(kù)

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

       (x1,y1)(x2,y2)

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

b)      花店櫥窗布置(IOI99)

      

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

 

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

3.1. 迭代

3.2. 四邊形

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