動態規劃總結

by Amber

1.   按狀態類型分

寫在前面：

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

1.1. 編號（長度）動態規劃

共性總結

本類的狀態是基礎的基礎，大部分的動態規劃都要用到它，成為一個維。

一般來說，有兩種編號的狀態：

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

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

題庫

a)       最長不下降子序列

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

一些問題可將數據有序化，轉化成本題。

              應用：

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

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

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

b)      LCS

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

c)       花店櫥窗布置(IOI99)

              見路徑問題。

1.2. 區間動態規劃

共性總結

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

題庫

a)       石子合并

              見劃分問題

b)      模版匹配(CEOI01,Patten)

              這題特殊的地方是狀態的值是一個集合而不是一個數。

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

d)      Electric Path(ural1143)

e)       郵局(IOI2000 Day2 1)

若狀態表示的思路從第i個村莊可以從屬于哪個郵局，無最優子結構。轉變一個方向：第k個郵局可以“控制”一個區間的村莊[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]間最好的一個郵局點。

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

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

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

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

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

              決策數量又少了一個數量級。

1.3. 坐標動態規劃

共性總結

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

題庫

a)       棋盤分割(NOI99 4)

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

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

后見路徑問題。

1.4. 數軸動態規劃

共性總結

 

       題庫

a)       01背包

              應用：

       裝箱問題（NOIP01 Trade 4）

就是原題。

值幣分割

              可利用方程的性質，空間降1維。

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

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

另給狀態加一個屬性last,記錄上一次剩下的可用的同幣值硬幣數（利用了當前轉移是唯一前驅的特點）。

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

             

c)       Stone Pile(ural1005 Stone Pile)

d)      公路巡邏(CTSC2000)

1.5. 5.樹型動態規劃

共性總結

1） 動態規劃的順序

一般按照后序遍歷的順序，即處理完兒子再處理當前節點，才符合樹的子結構的性質。

2） 多叉樹轉換為二叉樹

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

3） 加當前點的選或不選的常數維

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

……………………

4） 在將邊信息轉成樹時的技巧

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

5） 復雜度

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

題庫

a)       選課(CTSC97-3)

              由于要分配課程數，所以要多叉樹轉換為二叉樹。

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

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

              這樣就把問題轉化成：附加維是大頭吃的個數，當前點由不由大頭吃的常數維的動態規劃。由于涉及劃分問題，所以要多叉樹轉換為二叉樹。

c)       求樹的質心(sgu134 Centroid)

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

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

給出一棵邊帶權的樹，求樹中的點，使得此點到樹中的其他結點的最遠距離最近。

Computer Network (sgu149)

Computer Net (ural1056)

1.6. 集合動態規劃（狀態壓縮）

共性總結

1)      數據特殊性

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

              一個枚舉的狀態是一個集合。

2)      編碼

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

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

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

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

3)      狀態壓縮

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

題庫

a)       購物（IOI95-2）

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

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

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

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

c)       TSP問題

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

即當前路的最后一個節點為x,現在要選擇下一個節點y,而y要在未選點的集合中。若未選點或已選點的集合已確定，則后效性消除?？梢?/span>DP。狀態為令X為當前路的已選點的集合(含i)，當前路的最后一個節點為i。2元組(X,i)為經過已選點的集合X到節點i的最短長度。將X編碼即可。

注意：并沒有因為動態規劃將問題從NP類帶到P類。

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

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

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

有具體的報告。

d)      炮兵陣地

十分經典，詳見報告。

應用:

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

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

Little Knights(sgu225) 類似炮兵的做法的統計,數據量太大要const

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

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

1.7. 利用動態規劃思想求最值，編號（循環變量）的迭代

共性總結

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

題庫

a)       奶牛浴場

      

b)      Communication System

將數據有序化, 從大到小枚舉帶寬, 每次可利用上次處理的結果Min, 來決策當前狀態。稱作迭代, 或就是一種動態規劃。

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

1.8. 記憶化搜索

題庫

a)       Magic Trick (Problem G, TU-Darmstadt Programming Contest 2004)

2.   按轉移方式分

2.1. 存在性

遞推

1)01統計(CTSC99 1)

2)卡特蘭數

circle(sgu130)

       3)鷹蛋

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

2.2.1.    決策的分割點有序

共性總結

a)       有序性

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

b)      方程一般形式

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

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

題庫

a)       整數劃分

常應用在將一個權分配給一定的小分割塊，如：將大堆的石子分成一定的小堆，小堆可為空，大堆要分完。有時應用在樹型動態規劃（二叉轉多叉）中。

b)      乘積最大(NOIP00 Advance 2)

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

 

2.2.2.          決策的分割點無序

共性總結

a)       無序性

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

b)      方程一般形式

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

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

       方程很類似2叉樹的性質。

c)       四邊形不等式

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

題庫

a)       石子合并(NOI95 2)

經典，詳見報告。

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

其實還可以用類似堆的數據結構在O(nlogn)的時間內完成，但這就不是動態規劃了。

應用：

構造最優二叉排序樹(CTSC96 2)

 

b)      多邊形(IOI98)

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

c)       加分二叉樹(NOIP03 Advance 3)

方程就是一般式，轉移的函數：w(i,j)=sum(i,k-1)*sum(k+1,j)+d(k)。由于w(i,j)不滿足凸單調性，所以不能用四邊形不等式優化。

d)      括號序列(Problem B, NEERC 2001)

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

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

2.3. 路徑問題

共性總結

a)       行走方向決定階段性

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

b)      多源或多匯

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

c)       雙向動態規劃

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

d)      決策稀疏性

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

e)       狀態稀疏性

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

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

題庫

a)       方格取數(NOIP00 advance 4)

       (x1,y1)(x2,y2)

       對角線空間優化

b)      花店櫥窗布置(IOI99)

      

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

 

3.   動態規劃的優化

3.1. 迭代

3.2. 四邊形

3.3. 凸性的優化

 

    最主要的未總結，給出相關的題與已有的報告（自己或他人的）