非常好的动态规划总结，DP总结

杨利霞

非常好的动态规划总结，DP总结

详细资料请下载附件
& c7 {$ v$ L7 i3 K% [# |
目录  
0 k' q1 {* w" S

一、动态规划初探
6 m& |  Y! o; J      1、递推
- m/ _5 x4 w2 Y2 m* A/ Q0 w- `( F) A      2、记忆化搜索
; q' L& j! x" R/ B( M% I      3、状态和状态转移
      4、最优化原理和最优子结构
6 H; g1 P8 ?# Q# [8 U      5、决策和无后效性

; u, C0 z4 v0 J) o1 Z: `4 v
二、动态规划的经典模型
       1、线性模型
       2、区间模型
; S2 J0 |) F+ b9 _       3、背包模型
       4、状态压缩模型
. j6 c6 v; `. m       5、树状模型
% F1 f, t  E. |" o. K# U4 M
3 B+ n) Q) ^! M6 Y
三、动态规划的常用状态转移方程
( B4 e5 q& e' j, B! G% Y3 C( ^2 K+ b
      1、1D/1D
! c. C0 y9 q" o       2、2D/0D
       3、2D/1D
       4、2D/2D
, o% P! \+ u, B
四、动态规划和数据结构结合的常用优化
4 s1 C* b' P) f1、滚动数组
       2、最长单调子序列的二分优化
, C: x6 l" H# P: c, N( y: K       3、矩阵优化
       4、斜率优化
       5、树状数组优化
1 M$ t) i# k7 \" R" q       6、线段树优化
       7、其他优化
! i0 n( P4 w, i( }$ B! g
五、动态规划题集整理
/ D1 p' w; I/ D7 F/ P/ I

% A! @4 h* w5 G7 k9 {/ s
8 I8 i& l! R$ [7 u5 t* N
6 [/ Q, T7 X* {( ~8 a& G
' O( L, {/ B1 o+ B/ w+ Y