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

杨利霞

2 h- ?( l; `, b, l' a  k  a& ?非常好的动态规划总结，DP总结
0 K  L! J# P+ w! C$ g' y
详细资料请下载附件
% G- \2 y& x% k
1 u' h3 K6 b/ e8 }3 J目录  
4 g9 G5 K" G$ k9 P8 L* c/ E+ O
) E; w* }; J4 C$ g
一、动态规划初探
      1、递推
6 b; _% Z4 Z( h) u  S( {      2、记忆化搜索
5 h& h$ y7 e( ^4 j# L$ Q: Z      3、状态和状态转移
7 l$ w7 l5 @* t5 d' \; @      4、最优化原理和最优子结构
5 h- w0 I1 G( h      5、决策和无后效性
! l5 \$ ]$ w8 G4 \+ T5 e
  u) Y8 V/ `8 r2 M! y' \9 ?
: ]* Q5 G8 o- v+ O( M/ m二、动态规划的经典模型
  Z1 ]! N) E! R: q       1、线性模型
, P4 H& G- ~+ A1 {) e1 c3 w2 ~6 o6 Y. X       2、区间模型
! ]0 M! a4 G+ r% C& x- J       3、背包模型
) D: V: G8 v  W: S9 q       4、状态压缩模型
       5、树状模型
) {  J/ t$ `, v3 h

, X0 V' c8 t/ x6 T$ R# Z) f: b" c三、动态规划的常用状态转移方程
7 {: R" y' ~$ b* p
7 j- P# I  C8 M' @6 y      1、1D/1D
" w1 b7 [* R8 }4 k5 Q0 H, i$ M       2、2D/0D
8 E$ L& u5 M: M3 Z9 `' ~4 ]       3、2D/1D
# L0 D" J6 }" w& e; b: P; T       4、2D/2D
3 t9 m  s4 y( }
四、动态规划和数据结构结合的常用优化
1、滚动数组
6 z) q3 F. r. t0 N       2、最长单调子序列的二分优化
' `9 l8 j2 P6 v, c       3、矩阵优化
       4、斜率优化
       5、树状数组优化
       6、线段树优化
- T; a. X( B/ t7 w2 `       7、其他优化

' M. l. x% G! R6 S2 p) \五、动态规划题集整理
3 |0 o" l5 E2 ]" k4 L

5 q" E& b5 Z% ?; @' b
$ T9 b+ g# M: w0 D' g6 A- W

9 w* w. R: H) z2 U