動(dòng)態(tài)規(guī)劃分類有很多劃分方法，網(wǎng)上有很多是按照狀態(tài)來(lái)分，分為一維、二維、區(qū)間、樹形等等。我覺(jué)得還是按功能即解決的問(wèn)題的類型以及難易程度來(lái)分比較好，下面按照我自己的理解和歸納，把動(dòng)態(tài)規(guī)劃的分類如下：
一、簡(jiǎn)單基礎(chǔ)dp
這類dp主要是一些狀態(tài)比較容易表示，轉(zhuǎn)移方程比較好想，問(wèn)題比較基本常見(jiàn)的。主要包括遞推、背包、LIS（最長(zhǎng)遞增序列），LCS（最長(zhǎng)公共子序列），下面針對(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 折線分割平面 找遞推公式
推薦：
CF 429B B.Working out 四個(gè)角遞推
zoj 3747 Attack on Titans 帶限制條件的計(jì)數(shù)遞推dp
hdu 4489 The King's Ups and Downs
2、背包
經(jīng)典的背包九講：http://love-oriented.com/pack/
推薦博客：http://blog.csdn.net/woshi250hua/article/details/7636866
主要有0-1背包、完全背包、分組背包、多重背包。
簡(jiǎn)單：
hdu 2955 Robberies 01背包
hdu 1864 最大報(bào)銷額 01背包
hdu 2844 Coins 多重背包
hdu 2159 FATE 完全背包
推薦：
woj 1537 A Stone-I 轉(zhuǎn)化成背包
woj 1538 B Stone-II 轉(zhuǎn)化成背包
poj 1170 Shopping Offers 狀壓+背包
zoj 3769 Diablo III 帶限制條件的背包
zoj 3638 Fruit Ninja 背包的轉(zhuǎn)化成組合數(shù)學(xué)
hdu 3092 Least common multiple 轉(zhuǎn)化成完全背包問(wèn)題
poj 1015 Jury Compromise 擴(kuò)大區(qū)間+輸出路徑
3、LIS
最長(zhǎng)遞增子序列，樸素的是o(n^2)算法，二分下可以寫成o(nlgn)：維護(hù)一個(gè)當(dāng)前最優(yōu)的遞增序列——找到恰好大于它更新
簡(jiǎn)單：
推薦：
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
最長(zhǎng)公共子序列，通常o(n^2)的算法
uva 111 History Grading 要先排個(gè)序
二、區(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
hdu 4283 You Are the One 常見(jiàn)寫法
三、樹形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)比較好想，通過(guò)dfs維護(hù)從根到葉子或從葉子到根的狀態(tài)轉(zhuǎn)移。
hdu 4514 求樹的直徑
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 樹直徑的思想 思維
四、數(shù)位dp
推薦一篇論文：http://wenku.baidu.com/view/d2414ffe04a1b0717fd5dda8.html
數(shù)位dp,主要用來(lái)解決統(tǒng)計(jì)滿足某類特殊關(guān)系或有某些特點(diǎn)的區(qū)間內(nèi)的數(shù)的個(gè)數(shù)，它是按位來(lái)進(jìn)行計(jì)數(shù)統(tǒng)計(jì)的，可以保存子狀態(tài)，速度較快。數(shù)位dp做多了后，套路基本上都差不多，關(guān)鍵把要保存的狀態(tài)給抽象出來(lái)，保存下來(lá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
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ìng)賽中一類數(shù)學(xué)期望問(wèn)題的解決方法》
一般來(lái)說(shuō)概率正著推，期望逆著推。有環(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 推公式比較水
jobdu 1546 迷宮問(wèn)題 高斯消元+概率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
六、狀態(tài)壓縮dp
這類問(wèn)題有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 4568 Hunter 最短路+TSP
hdu 4539 插頭dp
七、數(shù)據(jù)結(jié)構(gòu)優(yōu)化的dp
有時(shí)盡管狀態(tài)找好了，轉(zhuǎn)移方程的想好了，但時(shí)間復(fù)雜度比較大，需要用數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化。常見(jiàn)的優(yōu)化有二進(jìn)制優(yōu)化、單調(diào)隊(duì)列優(yōu)化、斜率優(yōu)化、四邊形不等式優(yōu)化等。
1、二進(jìn)制優(yōu)化
主要是優(yōu)化背包問(wèn)題，背包九講里面有介紹，比較簡(jiǎn)單，這里只附上幾道題目。
2、單調(diào)隊(duì)列優(yōu)化
推薦論文：http://wenku.baidu.com/view/4d23b4d128ea81c758f578ae.html
推薦博客：http://www.cnblogs.com/neverforget/archive/2011/10/13/ll.html
poj 3245 Sequece Partitioning 二分+單調(diào)隊(duì)列優(yōu)化
3、斜率優(yōu)化
推薦論文：用單調(diào)性優(yōu)化動(dòng)態(tài)規(guī)劃
推薦博客：http://www.cnblogs.com/ronaflx/archive/2011/02/05/1949278.html
4、四邊形不等式優(yōu)化
推薦博客：http://www.cnblogs.com/ronaflx/archive/2011/03/30/1999764.html
推薦博客：http://www.cnblogs.com/zxndgv/archive/2011/08/02/2125242.html
