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

杨利霞

) \! _; W% G7 X* b非常好的动态规划总结，DP总结

详细资料请下载附件

; B2 e- q5 z( c- B5 I目录  
: U5 @, m: t9 B4 O2 ]0 }
! P" Z7 O6 B+ A* h
一、动态规划初探
      1、递推
      2、记忆化搜索
5 M, f. E1 R# j, s3 |      3、状态和状态转移
# U, j6 o2 Z% C3 i/ j0 q* n) v9 i      4、最优化原理和最优子结构
      5、决策和无后效性
' _. M/ `9 c2 D6 D
" @+ [9 k* s' W% Y3 k
二、动态规划的经典模型
       1、线性模型
       2、区间模型
       3、背包模型
  a' f2 @& i! ]       4、状态压缩模型
6 `) u3 X. F  X2 g6 @5 K       5、树状模型


三、动态规划的常用状态转移方程

1 I, c1 n% z4 Q+ S3 \" m      1、1D/1D
       2、2D/0D
       3、2D/1D
       4、2D/2D

# p4 ]( X- y, I7 _. W& a' H四、动态规划和数据结构结合的常用优化
8 }$ ^2 w" T7 A1、滚动数组
- `$ @% K1 x, t       2、最长单调子序列的二分优化
( d6 U( n* C! R7 V! u% z* m6 B# P% Z       3、矩阵优化
& h& a3 q( c* L* T- |       4、斜率优化
       5、树状数组优化
- `  n# @* F5 {* `; s4 k       6、线段树优化
       7、其他优化

五、动态规划题集整理
# n, U9 U( j+ ?' G


  B" Z) |: t# J7 ^
3 ?& a9 M4 \  g. o# g" X2 w