dp啊

2019-11-11 04:14:42

字體：大中小

供稿：網(wǎng)友

動(dòng)態(tài)規(guī)劃一直是ACM競(jìng)賽中的重點(diǎn)，同時(shí)又是難點(diǎn)，因?yàn)樵撍惴〞r(shí)間效率高，代碼量少，多元性強(qiáng)，主要考察思維能力、建模抽象能力、靈活度。

******************************************************************************************

動(dòng)態(tài)規(guī)劃（英語：Dynamic PRogramming，DP）是一種在數(shù)學(xué)、計(jì)算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)中使用的，通過把原問題分解為相對(duì)簡(jiǎn)單的子問題的方式求解復(fù)雜問題的方法。動(dòng)態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題，動(dòng)態(tài)規(guī)劃方法所耗時(shí)間往往遠(yuǎn)少于樸素解法。

動(dòng)態(tài)規(guī)劃背后的基本思想非常簡(jiǎn)單。大致上，若要解一個(gè)給定問題，我們需要解其不同部分（即子問題），再合并子問題的解以得出原問題的解。通常許多子問題非常相似，為此動(dòng)態(tài)規(guī)劃法試圖僅僅解決每個(gè)子問題一次，從而減少計(jì)算量：一旦某個(gè)給定子問題的解已經(jīng)算出，則將其記憶化存儲(chǔ)，以便下次需要同一個(gè)子問題解之時(shí)直接查表。這種做法在重復(fù)子問題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長時(shí)特別有用。

動(dòng)態(tài)規(guī)劃問題滿足三大重要性質(zhì)

最優(yōu)子結(jié)構(gòu)性質(zhì)：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，我們就稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（即滿足最優(yōu)化原理）。最優(yōu)子結(jié)構(gòu)性質(zhì)為動(dòng)態(tài)規(guī)劃算法解決問題提供了重要線索。

子問題重疊性質(zhì)：子問題重疊性質(zhì)是指在用遞歸算法自頂向下對(duì)問題進(jìn)行求解時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題會(huì)被重復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對(duì)每一個(gè)子問題只計(jì)算一次，然后將其計(jì)算結(jié)果保存在一個(gè)表格中，當(dāng)再次需要計(jì)算已經(jīng)計(jì)算過的子問題時(shí)，只是在表格中簡(jiǎn)單地查看一下結(jié)果，從而獲得較高的效率。

無后效性：將各階段按照一定的次序排列好之后，對(duì)于某個(gè)給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當(dāng)前的這個(gè)狀態(tài)。換句話說，每個(gè)狀態(tài)都是過去歷史的一個(gè)完整總結(jié)。這就是無后向性，又稱為無后效性。

********************************************************************************************

動(dòng)態(tài)規(guī)劃分類有很多劃分方法，網(wǎng)上有很多是按照狀態(tài)來分，分為一維、二維、區(qū)間、樹形等等。我覺得還是按功能即解決的問題的類型以及難易程度來分比較好，下面按照我自己的理解和歸納，把動(dòng)態(tài)規(guī)劃的分類如下：

一、簡(jiǎn)單基礎(chǔ)dp

這類dp主要是一些狀態(tài)比較容易表示，轉(zhuǎn)移方程比較好想，問題比較基本常見的。主要包括遞推、背包、LIS（最長遞增序列），LCS（最長公共子序列），下面針對(duì)這幾種類型，推薦一下比較好的學(xué)習(xí)資料和題目。

1、遞推：

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

簡(jiǎn)單:

hdu 2084 數(shù)塔簡(jiǎn)單從上往下遞推

hdu 2018 母牛的故事簡(jiǎn)單遞推計(jì)數(shù)

hdu 2044 一只小蜜蜂... 簡(jiǎn)單遞推計(jì)數(shù)（Fibonacci）

hdu 2041 超級(jí)樓梯 Fibonacci

hdu 2050 折線分割平面找遞推公式

推薦：

uva 10635 Prince and Princess LCS轉(zhuǎn)化成LIS

hdu 4352 XHXJ's LIS　數(shù)位dp+LIS思想

srm div2 1000 狀態(tài)壓縮+LIS

poj 1239 Increasing Sequence 兩次dp

4、LCS

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

hdu 1503 Advanced Fruits

hdu 1159 Common Subsequence

uva 111 History Grading 要先排個(gè)序

poj 1080 Human Gene Functions

二、區(qū)間dp

推薦博客：http://blog.csdn.net/woshi250hua/article/details/7969225

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

poj 1141 Brackets Sequence 括號(hào)匹配并輸出方案

hdu 4745 Two Rabbits 轉(zhuǎn)化成求回文串

zoj 3541 The Last Puzzle 貪心+區(qū)間dp

poj 2955 Brackets

hdu 4283 You Are the One 常見寫法

hdu 2476 String Printer

zoj 3537 Cake

CF 149D Coloring Brackets

zoj 3469 Food Delivery

三、樹形dp

比較好的博客：http://blog.csdn.net/woshi250hua/article/details/7644959

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

樹形dp是建立在樹這種數(shù)據(jù)結(jié)構(gòu)上的dp,一般狀態(tài)比較好想，通過dfs維護(hù)從根到葉子或從葉子到根的狀態(tài)轉(zhuǎn)移。

hdu 4123 Bob's Race 二分+樹形dp+單調(diào)隊(duì)列

hdu 4514 求樹的直徑

poj 1655 Balancing Act

hdu 4714 Tree2Cycle 思維

hdu 4616 Game

hdu 4126 Genghis Kehan the Conqueror MST+樹形dp 比較經(jīng)典

hdu 4756 Install Air Conditioning MST+樹形dp 同上

hdu 3660 Alice and Bob's Trip 有點(diǎn)像對(duì)抗搜索

CF 337D Book of Evil 樹直徑的思想思維

hdu 2196 Computer 搜兩遍

四、數(shù)位dp

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

數(shù)位dp,主要用來解決統(tǒng)計(jì)滿足某類特殊關(guān)系或有某些特點(diǎn)的區(qū)間內(nèi)的數(shù)的個(gè)數(shù)，它是按位來進(jìn)行計(jì)數(shù)統(tǒng)計(jì)的，可以保存子狀態(tài)，速度較快。數(shù)位dp做多了后，套路基本上都差不多，關(guān)鍵把要保存的狀態(tài)給抽象出來，保存下來。

hdu 2089 不要62 簡(jiǎn)單數(shù)位dp

hdu 3709 Balanced Number 比較簡(jiǎn)單

CF 401D Roman and Numbers 狀壓+數(shù)位dp

hdu 4398 X mod f(x) 把模數(shù)加進(jìn)狀態(tài)里面

hdu 4734 F(x) 簡(jiǎn)單數(shù)位dp

hdu 3693 Math teacher's homework 思維變換的數(shù)位dp

hdu 4352 XHXJ's LIS　數(shù)位dp+LIS思想

CF 55D Beautiful Numbers 比較巧妙的數(shù)位dp

hdu 3565 Bi-peak Numbers 比較難想

CF 258B Little Elephant and Elections 數(shù)位dp+組合數(shù)學(xué)+逆元

五、概率(期望) dp

推薦博客：http://www.cnblogs.com/kuangbin/archive/2012/10/02/2710606.html

推薦博客：http://blog.csdn.net/woshi250hua/article/details/7912049

推薦論文：

《走進(jìn)概率的世界》

《淺析競(jìng)賽中一類數(shù)學(xué)期望問題的解決方法》

《有關(guān)概率和期望問題的研究》

一般來說概率正著推，期望逆著推。有環(huán)的一般要用到高斯消元解方程。期望可以分解成多個(gè)子期望的加權(quán)和，權(quán)為子期望發(fā)生的概率，即 E(aA+bB+...) = aE(A) + bE(B) +...

ural 1776 Anniversiry Firework 比較基礎(chǔ)

hdu 4418 Time travel 比較經(jīng)典BFS+概率dp+高斯消元

hdu 4586 Play the Dice 推公式比較水

hdu 4487 Maximum Random Walk

jobdu 1546 迷宮問題高斯消元+概率dp+BFS預(yù)處理

hdu 3853 LOOPS 簡(jiǎn)單概率dp

hdu 4405 Aeroplane chess 簡(jiǎn)單概率dp,比較直接

hdu 4089 Activation 比較經(jīng)典

poj 2096 Collecting Bugs 題目比較難讀懂

zoj 3640 Help me Escape 從后往前，比較簡(jiǎn)單

hdu 4034 Maze 經(jīng)典好題，借助樹的概率dp

hdu 4336 Card Collector 狀態(tài)壓縮+概率dp

hdu 4326 Game 這個(gè)題狀態(tài)有點(diǎn)難抽象

六、狀態(tài)壓縮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 1693 Eat the Trees 插頭dp

hdu 4568 Hunter 最短路+TSP

hdu 4539 插頭dp

hdu 4529 狀壓dp

poj 1185 炮兵陣地

poj 2411 Mandriann's Dream 輪廓線dp

hdu 3811 Permutation

poj 1038

poj 2441

hdu 2167

hdu 4026

hdu 4281

七、數(shù)據(jù)結(jié)構(gòu)優(yōu)化的dp

有時(shí)盡管狀態(tài)找好了，轉(zhuǎn)移方程的想好了，但時(shí)間復(fù)雜度比較大，需要用數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化。常見的優(yōu)化有二進(jìn)制優(yōu)化、單調(diào)隊(duì)列優(yōu)化、斜率優(yōu)化、四邊形不等式優(yōu)化等。

1、二進(jìn)制優(yōu)化

主要是優(yōu)化背包問題，背包九講里面有介紹，比較簡(jiǎn)單，這里只附上幾道題目。

hdu 1059 Diving

hdu 1171 Big Event in Hdu

poj 1048 Follow My Magic

2、單調(diào)隊(duì)列優(yōu)化

推薦論文：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 二分+單調(diào)隊(duì)列優(yōu)化

3、斜率優(yōu)化

推薦論文：用單調(diào)性優(yōu)化動(dòng)態(tài)規(guī)劃