算法學習之動态規劃（一）動态規劃入門

動态規劃一直不敢碰 這次決定死磕了

學不會就學不會 哈哈

什麼是動态規劃

• 動态規劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優化的數學方法。

  20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decision

  process)的優化問題時，提出了著名的最優化原理(principle of

  optimality)，把多階段過程轉化為一系列單階段問題，逐個求解，創立了解決這類過程優化問題的新方法——動态規劃。1957年出版了他的名著Dynamic

  Programming，這是該領域的第一本著作。

應用：

動态規劃問世以來，在經濟管理、生産排程、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源配置設定、裝置更新、排序、裝載等問題，用動态規劃方法比用其它方法求解更為友善。

基本模型

多階段決策過程的最優化問題：

如果一類活動過程可以分為若幹個互相聯系的階段，在每一個階段都需作出決策(采取措施)，一個階段的決策确定以後，常常影響到下一個階段的決策，進而就完全确定了一個過程的活動路線，則稱它為多階段決策問題。

.

動态規劃的解題要領

重要要明确

• 階段
• 狀态

• 無後效性

  ：我們要求狀态具有下面的性質：如果給定某一階段的狀态，則在這一階段以後過程的發展不受這階段以前各段狀态的影響，所有各階段都确定時，整個過程也就确定了。換句話說，過程的每一次實作可以用一個狀态序清單示，在前面的例子中每階段的狀态是該線路的始點，确定了這些點的序列，整個線路也就完全确定。從某一階段以後的線路開始，當這段的始點給定時，不受以前線路（所通過的點）的影響。狀态的這個性質意味着過程的曆史隻能通過目前的狀态去影響它的未來的發展，這個性質稱為無後效性。

• 政策

  ：由每個階段的決策組成的序列稱為政策。對于每一個實際的多階段決策過程，可供選取的政策有一定的範圍限制，這個範圍稱為允許政策集合。允許政策集合中達到最優效果的政策稱為最優政策。

• 狀态轉移方程

  ：給定k階段狀态變量x(k)的值後，如果這一階段的決策變量一經确定，第k+1階段的狀态變量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k階段的決策u(k)的值變化而變化，那麼可以把這一關系看成(x(k)，u(k))與x(k+1)确定的對應關系，用x(k+1)=Tk(x(k),u(k))表示。這是從k階段到k+1階段的狀态轉移規律，稱為狀态轉移方程。

• 最優性原理:

  作為整個過程的最優政策，它滿足：相對前面決策所形成的狀态而言，餘下的子政策必然構成“最優子政策”。

動态規劃的定義：

動态規劃的基本思想是

把待求解的問題分解成若幹個子問題，

先求解子問題，然後再從這些子問題的解得到原問題的解，

其中用動态規劃分解得到的子問題往往不是互相獨立的。

動态規劃在查找有很多重疊子問題的情況的最優解時有效。它将問題重新組合成子問題。為了避免多次解決這些子問題，它們的結果都逐漸被計算并被儲存，從簡單的問題直到整個問題都被解決。是以，動态規劃儲存遞歸時的結果，因而不會在解決同樣的問題時花費時間。

動态規劃隻能應用于有最優子結構的問題。

最優子結構的意思是局部最優解能決定全局最優解(對有些問題這個要求并不能完全滿足，故有時需要引入一定的近似)。簡單地說，問題能夠分解成子問題來解決。

求解步驟如下：

1. 找出最優解的性質，并刻畫其結構特征；

2. 遞歸地定義最優值；

3. 以自底向上的方式計算出最優值；

4. 根據計算最優值時得到的資訊，構造最優解。

動态規劃類題目有兩個特點：一是問題包含最優子結構；二是子狀态可以重複取到。和搜尋一樣，是計算機擅長而人不擅長的處理問題的方式。是以一開始了解起來确實多有不便。

動态規劃的要素有二：一是狀态方式的選取；二是狀态轉移方程或轉化公式

動規解題的一般思路

1. 将原問題分解為子問題把原問題分解為若幹個子問題
子問題和原問題形式相同或類似，隻不過規模變小了。子問題都解決，原問題即解決(數字三角形例）。
子問題的解一旦求出就會被儲存，是以每個子問題隻需求 解一次。
2. 确定狀态
3. 确定一些初始狀态（邊界狀态）的值
4. 确定狀态轉移方程  也就是遞推公式
           

特征：

重疊子問題

子問題最優結構

無後效性

動态規劃的幾種分類

分為一維、二維、區間、樹形

一.簡單基礎dp

這類dp主要是一些狀态比較容易表示，轉移方程比較好想，問題比較基本常見的。主要包括遞推、背包、LIS（最長遞增序列），LCS（最長公共子序列）

1、遞推：

遞推一般形式比較單一，從前往後，分類枚舉就行。

簡單:
hdu  數塔 簡單從上往下遞推
hdu  母牛的故事 簡單遞推計數
hdu  一隻小蜜蜂... 簡單遞推計數（Fibonacci）
hdu  超級樓梯 Fibonacci
hdu  折線分割平面 找遞推公式
推薦：
CF 429B B.Working out 四個角遞推
zoj  Attack on Titans 帶限制條件的計數遞推dp
uva  Coin Toss 同上題
hdu  Mex 
hdu  The King's Ups and Downs
hdu 4054 Number String
           

2、背包

經典的背包九講：http://love-oriented.com/pack/

推薦部落格：http://blog.csdn.net/woshi250hua/article/details/7636866

主要有0-1背包、完全背包、分組背包、多重背包。

簡單：
hdu  Robberies 背包
hdu  最大報帳額 背包
hdu  Bone Collector 背包
hdu  Coins 多重背包
hdu  FATE 完全背包
推薦：
woj  A Stone-I  轉化成背包
woj  B Stone-II 轉化成背包
poj  Shopping Offers 狀壓+背包
zoj  Diablo III 帶限制條件的背包
zoj  Fruit Ninja 背包的轉化成組合數學
hdu  Least common multiple 轉化成完全背包問題
poj  Jury Compromise 擴大區間+輸出路徑
           

3、LIS

最長遞增子序列，樸素的是o(n^2)算法，二分下可以寫成o(nlgn)：維護一個目前最優的遞增序列——找到恰好大于它更新

簡單：
hdu  Max Sum
hdu  Super Jumping!
推薦：
uva  Prince and Princess LCS轉化成LIS
hdu  XHXJ's LIS　數位dp+LIS思想
srm div2   狀态壓縮+LIS
poj  Increasing Sequence 兩次dp
           

4、LCS

最長公共子序列，通常o(n^2)的算法

hdu 1503 Advanced Fruits
hdu 1159 Common Subsequence
uva 111 History Grading 要先排個序
poj 1080 Human Gene Functions
           

二、區間dp

推薦部落格：http://blog.csdn.net/woshi250hua/article/details/7969225

區間dp,一般是枚舉區間，把區間分成左右兩部分，然後求出左右區間再合并。

poj  Brackets Sequence 括号比對并輸出方案
hdu  Two Rabbits 轉化成求回文串 
zoj  The Last Puzzle  貪心+區間dp
poj  Brackets
hdu  You Are the One  常見寫法
hdu  String Printer 
zoj  Cake
CF D Coloring Brackets
zoj  Food Delivery
           

三、樹形dp

比較好的部落格：http://blog.csdn.net/woshi250hua/article/details/7644959

一篇論文：http://doc.baidu.com/view/f3b19d0b79563c1ec5da710e.html

樹形dp是建立在樹這種資料結構上的dp,一般狀态比較好想，通過dfs維護從根到葉子或從葉子到根的狀态轉移。

hdu   求樹的直徑
poj  Balancing Act 
hdu  Tree2Cycle 思維
hdu  Game
hdu  Genghis Kehan the Conqueror MST+樹形dp 比較經典
hdu  Install Air Conditioning MST+樹形dp 同上
hdu  Alice and Bob's Trip 有點像對抗搜尋
CF D Book of Evil  樹直徑的思想 思維
hdu  Computer 搜兩遍
           

四、數位dp

推薦一篇論文：http://wenku.baidu.com/view/d2414ffe04a1b0717fd5dda8.html

數位dp,主要用來解決統計滿足某類特殊關系或有某些特點的區間内的數的個數，它是按位來進行計數統計的，可以儲存子狀态，速度較快。數位dp做多了後，套路基本上都差不多，關鍵把要儲存的狀态給抽象出來，儲存下來。

hdu  不要 簡單數位dp
hdu  Balanced Number 比較簡單
CF D Roman and Numbers 狀壓+數位dp
hdu  X mod f(x) 把模數加進狀态裡面
hdu  F(x)  簡單數位dp
hdu  Math teacher's homework 思維變換的數位dp
hdu 4352 XHXJ's LIS　數位dp+LIS思想
CF D Beautiful Numbers  比較巧妙的數位dp
hdu  Bi-peak Numbers 比較難想
CF B Little Elephant and Elections 數位dp+組合數學+逆元
           

五、機率(期望) dp

推薦部落格：http://www.cnblogs.com/kuangbin/archive/2012/10/02/2710606.html

推薦部落格：http://blog.csdn.net/woshi250hua/article/details/7912049

推薦論文：

《走進機率的世界》

《淺析競賽中一類數學期望問題的解決方法》

《有關機率和期望問題的研究》

一般來說機率正着推，期望逆着推。有環的一般要用到高斯消元解方程。期望可以分解成多個子期望的權重和，權為子期望發生的機率，即 E(aA+bB+…) = aE(A) + bE(B) +…

ural  Anniversiry Firework 比較基礎
hdu  Time travel  比較經典BFS+機率dp+高斯消元
hdu  Play the Dice 推公式比較水
hdu  Maximum Random Walk 
jobdu  迷宮問題 高斯消元+機率dp+BFS預處理
hdu  LOOPS 簡單機率dp
hdu  Aeroplane chess 簡單機率dp,比較直接
hdu  Activation 比較經典
poj  Collecting Bugs 題目比較難讀懂
zoj  Help me Escape 從後往前，比較簡單
hdu  Maze 經典好題，借助樹的機率dp
hdu  Card Collector 狀态壓縮+機率dp
           

六、狀态壓縮dp

這類問題有TSP、插頭dp等。

推薦論文：http://wenku.baidu.com/view/ce445e4f767f5acfa1c7cd51.html

推薦部落格：http://blog.csdn.net/sf____/article/details/15026397

推薦部落格：http://www.notonlysuccess.com/index.php/plug_dp/

hdu  Hunter 最短路+TSP
hdu   插頭dp
hdu  狀壓dp
poj  炮兵陣地
hdu  Permutation
poj  Mandriann's Dream
poj 
poj 
hdu 
hdu 
hdu 
           

七、資料結構優化的dp

有時盡管狀态找好了，轉移方程的想好了，但時間複雜度比較大，需要用資料結構進行優化。常見的優化有二進制優化、單調隊列優化、斜率優化、四邊形不等式優化等。

1、二進制優化

主要是優化背包問題，背包九講裡面有介紹，比較簡單，這裡隻附上幾道題目。

hdu  Diving 
hdu  Big Event in Hdu
poj  Follow My Magic
           

2、單調隊列優化

推薦論文：http://wenku.baidu.com/view/4d23b4d128ea81c758f578ae.html

推薦部落格：http://www.cnblogs.com/neverforget/archive/2011/10/13/ll.html

hdu 3401 Trade  
poj 3245 Sequece Partitioning 二分+單調隊列優化
           

3、斜率優化

推薦論文：用單調性優化動态規劃

推薦部落格：http://www.cnblogs.com/ronaflx/archive/2011/02/05/1949278.html

hdu  Print Article
poj  Pearls
hdu  Lawrence
hdu  Max Average Problem
           

4、四邊形不等式優化

推薦部落格：http://www.cnblogs.com/ronaflx/archive/2011/03/30/1999764.html

推薦部落格：http://www.cnblogs.com/zxndgv/archive/2011/08/02/2125242.html

hdu 2952 Counting Sheep
poj 1160 Post Office
hdu 3480 Division
hdu 3516 Tree Construction
hdu 2829 Lawrence
           

常見的動态規化類型總結

後續再總結