一、簡單基礎dp
這類dp主要是一些狀态比較容易表示，轉移方程比較好想，問題比較基本常見的。主要包括遞推、背包、LIS（最長遞增序列），LCS（最長公共子序列），下面針對這幾種類型，推薦一下比較好的學習資料和題目。
1、遞推：
遞推一般形式比較單一，從前往後，分類枚舉就行。
簡單:
hdu 2084 數塔 簡單從上往下遞推
hdu 2018 母牛的故事 簡單遞推計數
hdu 2044 一隻小蜜蜂... 簡單遞推計數（Fibonacci）
hdu 2041 超級樓梯 Fibonacci
hdu 2050 折線分割平面 找遞推公式
推薦：
CF 429B B.Working out 四個角遞推
zoj 3747 Attack on Titans 帶限制條件的計數遞推dp
uva 10328 Coin Toss 同上題
hdu 4747 Mex
hdu 4489 The King's Ups and Downs
hdu 4054 Number String
2、背包
經典的背包九講：http://love-oriented.com/pack/
推薦部落格：javascript:void(0)
主要有0-1背包、完全背包、分組背包、多重背包。
簡單：
hdu 2955 Robberies 01背包
hdu 1864 最大報帳額 01背包
hdu 2602 Bone Collector 01背包
hdu 2844 Coins 多重背包
hdu 2159 FATE 完全背包
woj 1537 A Stone-I 轉化成背包
woj 1538 B Stone-II 轉化成背包
poj 1170 Shopping Offers 狀壓+背包
zoj 3769 Diablo III 帶限制條件的背包
zoj 3638 Fruit Ninja 背包的轉化成組合數學
hdu 3092 Least common multiple 轉化成完全背包問題
poj 1015 Jury Compromise 擴大區間+輸出路徑
3、LIS
最長遞增子序列，樸素的是o(n^2)算法，二分下可以寫成o(nlgn)：維護一個目前最優的遞增序列——找到恰好大于它更新
hdu 1003 Max Sum
hdu 1087 Super Jumping!
uva 10635 Prince and Princess LCS轉化成LIS
hdu 4352 XHXJ's LIS 數位dp+LIS思想
srm div2 1000 狀态壓縮+LIS
poj 1239 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
區間dp,一般是枚舉區間，把區間分成左右兩部分，然後求出左右區間再合并。
poj 1141 Brackets Sequence 括号比對并輸出方案
hdu 4745 Two Rabbits 轉化成求回文串
zoj 3541 The Last Puzzle 貪心+區間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
比較好的部落格：javascript:void(0)
一篇論文：http://doc.baidu.com/view/f3b19d0b79563c1ec5da710e.html
樹形dp是建立在樹這種資料結構上的dp,一般狀态比較好想，通過dfs維護從根到葉子或從葉子到根的狀态轉移。
hdu 4514 求樹的直徑
poj 1655 Balancing Act
hdu 4714 Tree2Cycle 思維
hdu 4616 Game
hdu 4126 Genghis Kehan the Conqueror MST+樹形dp 比較經典
hdu 4756 Install Air Conditioning MST+樹形dp 同上
hdu 3660 Alice and Bob's Trip 有點像對抗搜尋
CF 337D Book of Evil 樹直徑的思想 思維
hdu 2196 Computer 搜兩遍
四、數位dp
推薦一篇論文：http://wenku.baidu.com/view/d2414ffe04a1b0717fd5dda8.html
數位dp,主要用來解決統計滿足某類特殊關系或有某些特點的區間内的數的個數，它是按位來進行計數統計的，可以儲存子狀态，速度較快。數位dp做多了後，套路基本上都差不多，關鍵把要儲存的狀态給抽象出來，儲存下來。
hdu 2089 不要62 簡單數位dp
hdu 3709 Balanced Number 比較簡單
CF 401D Roman and Numbers 狀壓+數位dp
hdu 4398 X mod f(x) 把模數加進狀态裡面
hdu 4734 F(x) 簡單數位dp
hdu 3693 Math teacher's homework 思維變換的數位dp
CF 55D Beautiful Numbers 比較巧妙的數位dp
hdu 3565 Bi-peak Numbers 比較難想
CF 258B Little Elephant and Elections 數位dp+組合數學+逆元
五、機率(期望) dp
推薦論文：
《走進機率的世界》
《淺析競賽中一類數學期望問題的解決方法》
《有關機率和期望問題的研究》
一般來說機率正着推，期望逆着推。有環的一般要用到高斯消元解方程。期望可以分解成多個子期望的權重和，權為子期望發生的機率，即 E(aA+bB+...) = aE(A) + bE(B) +...
ural 1776 Anniversiry Firework 比較基礎
hdu 4418 Time travel 比較經典BFS+機率dp+高斯消元
hdu 4586 Play the Dice 推公式比較水
hdu 4487 Maximum Random Walk
jobdu 1546 迷宮問題 高斯消元+機率dp+BFS預處理
hdu 3853 LOOPS 簡單機率dp
hdu 4405 Aeroplane chess 簡單機率dp,比較直接
hdu 4089 Activation 比較經典
poj 2096 Collecting Bugs 題目比較難讀懂
zoj 3640 Help me Escape 從後往前，比較簡單
hdu 4034 Maze 經典好題，借助樹的機率dp
hdu 4336 Card Collector 狀态壓縮+機率dp
六、狀态壓縮dp
這類問題有TSP、插頭dp等。
推薦論文：http://wenku.baidu.com/view/ce445e4f767f5acfa1c7cd51.html
推薦部落格：http://www.notonlysuccess.com/index.php/plug_dp/
hdu 4568 Hunter 最短路+TSP
hdu 4539 插頭dp
hdu 4529 狀壓dp
poj 1185 炮兵陣地
hdu 3811 Permutation
poj 2411 Mandriann's Dream
poj 1038
poj 2441
hdu 2167
hdu 4026
hdu 4281
七、資料結構優化的dp
有時盡管狀态找好了，轉移方程的想好了，但時間複雜度比較大，需要用資料結構進行優化。常見的優化有二進制優化、單調隊列優化、斜率優化、四邊形不等式優化等。
1、二進制優化
主要是優化背包問題，背包九講裡面有介紹，比較簡單，這裡隻附上幾道題目。
hdu 1059 Diving
hdu 1171 Big Event in Hdu
poj 1048 Follow My Magic
2、單調隊列優化
推薦論文：http://wenku.baidu.com/view/4d23b4d128ea81c758f578ae.html
hdu 3401 Trade
poj 3245 Sequece Partitioning 二分+單調隊列優化
3、斜率優化
推薦論文：用單調性優化動态規劃
hdu 3507 Print Article
poj 1260 Pearls
hdu 2829 Lawrence
hdu 2993 Max Average Problem
4、四邊形不等式優化
hdu 2952 Counting Sheep
poj 1160 Post Office
hdu 3480 Division
hdu 3516 Tree Construction
五、動态規劃題集整理
1、遞推
Recursion Practice ★☆☆☆☆ 幾個初級遞推
Put Apple ★☆☆☆☆
Tri Tiling ★☆☆☆☆ 【例題1】
Computer Transformation ★☆☆☆☆ 【例題2】
Train Problem II ★☆☆☆☆
How Many Trees? ★☆☆☆☆
Buy the Ticket ★☆☆☆☆
Game of Connections ★☆☆☆☆
Count the Trees ★☆☆☆☆
Circle ★☆☆☆☆
Combinations, Once Again ★★☆☆☆
Closing Ceremony of Sunny Cup ★★☆☆☆
Rooted Trees Problem ★★☆☆☆
Water Treatment Plants ★★☆☆☆
One Person ★★☆☆☆
Relax! It’s just a game ★★☆☆☆
N Knight ★★★☆☆
Connected Graph ★★★★★ 樓天城“男人八題”之一
2、記憶化搜尋
Function Run Fun ★☆☆☆☆ 【例題3】
FatMouse and Cheese ★☆☆☆☆ 經典迷宮問題
Cheapest Palindrome ★★☆☆☆
A Mini Locomotive ★★☆☆☆
Millenium Leapcow ★★☆☆☆
Brackets Sequence ★★★☆☆ 經典記憶化
Chessboard Cutting ★★★☆☆ 《算法藝術和資訊學競賽》例題
Number Cutting Game ★★★☆☆
Constructing Roads In JG Kingdom ★★☆☆☆
Stock Exchange ★★☆☆☆
Wooden Sticks ★★☆☆☆
Bridging signals ★★☆☆☆
BUY LOW, BUY LOWER ★★☆☆☆ 要求需要輸出方案數
Longest Ordered Subsequence ★★☆☆☆
Crossed Matchings ★★☆☆☆
Jack's struggle ★★★☆☆ 稍微做點轉化
Max Sum Plus Plus ★★☆☆☆ 最大M子段和
To The Max ★★☆☆☆ 最大子矩陣
Max Sequence ★★☆☆☆ 最大2子段和
Maximum sum ★★☆☆☆ 最大2子段和
最大連續子序列 ★★☆☆☆ 最大子段和
Largest Rectangle in a Histogram ★★☆☆☆ 最大子矩陣變形
City Game ★★☆☆☆ 最大子矩陣擴充
Matrix Swapping II ★★★☆☆ 最大子矩陣變形後擴充
Super Jumping! Jumping! Jumping! ★☆☆☆☆
Milking Time ★★☆☆☆ 區間問題的線性模型
Computers ★★☆☆☆ 【例題5】
Bridge over a rough river ★★★☆☆ 【例題6】
Crossing River ★★★☆☆ 【例題6】大資料版
Blocks ★★★☆☆
Parallel Expectations ★★★★☆ 線性模型黑書案例
6、區間模型
Palindrome ★☆☆☆☆ 【例題7】
See Palindrome Again ★★★☆☆
7、背包模型
飯卡 ★☆☆☆☆ 01背包
I NEED A OFFER! ★☆☆☆☆ 機率轉化
Bone Collector ★☆☆☆☆ 01背包
最大報帳額 ★☆☆☆☆ 01背包
Duty Free Shop ★★☆☆☆ 01背包
Robberies ★★☆☆☆ 【例題8】
Piggy-Bank ★☆☆☆☆ 完全背包
Cash Machine ★☆☆☆☆ 多重背包
Coins ★★☆☆☆ 多重背包，樓天城“男人八題”之一
I love sneakers! ★★★☆☆ 背包變形
8、狀态壓縮模型
ChessboardProblem ★☆☆☆☆ 比較基礎的狀态壓縮
Number of Locks ★☆☆☆☆ 簡單狀态壓縮問題
Islands and Bridges ★★☆☆☆ 【例題9】
Tiling a Grid With Dominoes ★★☆☆☆ 骨牌鋪方格 4XN的情況
Mondriaan's Dream ★★☆☆☆ 【例題10】的簡易版
Renovation Problem ★★☆☆☆ 簡單擺放問題
The Number of set ★★☆☆☆
Hardwood floor ★★★☆☆ 【例題10】二進制狀态壓縮鼻祖
Tetris Comes Back ★★★☆☆ 紙老虎題
Bugs Integrated, Inc. ★★★☆☆ 三進制狀态壓縮鼻祖
Another Chocolate Maniac ★★★☆☆ 三進制
Emplacement ★★★☆☆ 類似Bugs那題，三進制
Toy bricks ★★★☆☆ 四進制， 左移運算高于&
Quad Tiling ★★★☆☆ 骨牌鋪方格 4XN的情況 利用矩陣優化
Eat the Trees ★★★☆☆ 插頭DP入門題
Formula 1 ★★★☆☆ 插頭DP入門題
The Hive II ★★★☆☆ 插頭DP
Plan ★★★☆☆ 插頭DP
Manhattan Wiring ★★★☆☆ 插頭DP
Pandora adventure ★★★★☆ 插頭DP
Tony's Tour ★★★★☆ 插頭DP，樓天城“男人八題”之一
Pipes ★★★★☆ 插頭DP
circuits ★★★★☆ 插頭DP
Beautiful Meadow ★★★★☆ 插頭DP
I-country ★★★★☆ 高維狀态表示
Permutaion ★★★★☆ 牛逼的狀态表示
01-K Code ★★★★☆
Tour in the Castle ★★★★★ 插頭DP（難）
The Floor Bricks ★★★★★ 四進制（需要優化）
9、樹狀模型
Anniversary party ★☆☆☆☆ 樹形DP入門
Strategic game ★☆☆☆☆ 樹形DP入門
Computer ★★☆☆☆
Long Live the Queen ★★☆☆☆
最優連通子集 ★★☆☆☆
Computer Network ★★☆☆☆
Rebuilding Roads ★★★☆☆ 樹形DP+背包
New Year Bonus Grant ★★★☆☆
How Many Paths Are There ★★★☆☆
Intermediate Rounds for Multicast ★★★★☆
Fire ★★★★☆
Walking Race ★★★★☆
Tree ★★★★★ 樹形DP，樓天城“男人八題”之一
10、滾動數組優化常見問題
Palindrome ★☆☆☆☆
Telephone Wire ★☆☆☆☆
Gangsters ★☆☆☆☆
Dominoes ★☆☆☆☆
Cow Exhibition ★☆☆☆☆
Supermarket ★★☆☆☆
11、決策單調性
Print Article ★★★☆☆
Lawrence ★★★☆☆
Batch Scheduling ★★★☆☆
K-Anonymous Sequence ★★★☆☆
Cut the Sequence ★★★☆☆
12、常用優化
Divisibility ★★☆☆☆ 利用同餘性質
Magic Multiplying Machine ★★☆☆☆ 利用同餘性質
Moving Computer ★★☆☆☆ 散列HASH表示狀态
Post Office ★★★☆☆ 四邊形不等式
Minimizing maximizer ★★★☆☆ 線段樹優化
Man Down ★★★☆☆ 線段樹優化
So you want to be a 2n-aire? ★★★☆☆ 期望問題
Expected Allowance ★★★☆☆ 期望問題
Greatest Common Increase Subseq ★★★☆☆ 二維線段樹優化
Traversal ★★★☆☆ 樹狀數組優化
Find the nondecreasing subsequences ★★★☆☆ 樹狀數組優化
Not Too Convex Hull ★★★★☆ 利用凸包進行狀态轉移
In Action ★★★☆☆ 最短路+背包
Search of Concatenated Strings ★★★☆☆ STL bitset 應用
13、其他類型的動态規劃
Common Subsequence 2D/0D
Advanced Fruits 2D/0D
Travel 2D/1D
RIPOFF 2D/1D
Balls 2D/1D
Projects 2D/1D
Cow Roller Coaster 2D/1D
LITTLE SHOP OF FLOWERS 2D/1D
Pearls 2D/1D
Spiderman 2D/0D
The Triangle 2D/0D
Triangles 2D/0D
Magazine Delivery 3D/0D
Tourist 3D/0D
Rectangle 2D/1D
Message 2D/1D
Bigger is Better 2D/1D
Girl Friend II 2D/1D
Phalanx 2D/1D
Spiderman 最壞複雜度O(NK)，K最大為1000000，呵呵
Find a path 3D/1D 公式簡化，N維不能解決的問題試着用N+1維來求解 ![web前端布局練手項目[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)