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

杨利霞

, R5 ]7 x4 D4 n5 q( L, t& A* n( {3 `8 O非常好的动态规划总结，DP总结

详细资料请下载附件

' b, `# O5 O6 O$ d目录  
8 C$ n8 U) Q* ^

# _* w0 ?" o$ g一、动态规划初探
      1、递推
& ^6 s+ {* _" P; `$ @' ]  v; i# E      2、记忆化搜索
2 e# k1 w/ l! e/ m3 o1 m      3、状态和状态转移
      4、最优化原理和最优子结构
; B) ^9 c2 n7 l& U: R. U$ \& g      5、决策和无后效性


8 r! T. }4 W: Q二、动态规划的经典模型
9 [& J* A. r2 u8 U) `       1、线性模型
       2、区间模型
! V' O  `5 P' |$ j2 r. b       3、背包模型
       4、状态压缩模型
       5、树状模型


三、动态规划的常用状态转移方程
- T  L; _. w0 A
      1、1D/1D
  ^0 g, b2 e3 @, P- W! G       2、2D/0D
       3、2D/1D
       4、2D/2D
8 p. b' q  T( [* j: }8 E) M; Q
* U7 X) L3 ~; G) y, Y/ X; h6 c' `' K四、动态规划和数据结构结合的常用优化
1、滚动数组
, K7 n. B! U3 e% \& Y: i0 f& j3 _       2、最长单调子序列的二分优化
       3、矩阵优化
5 c' h4 i' W! a& D. e& a       4、斜率优化
       5、树状数组优化
1 k" y0 \, Y1 B- `       6、线段树优化
- h8 E! f. c# s/ T, r       7、其他优化
& O) G  ^0 X* d% ]
+ i% L* {) `% U( W2 N6 \5 s五、动态规划题集整理
" h! ]$ y& c1 `4 I


9 h1 A. _5 K' i/ ?3 J

6 H4 j5 p, {5 @2 z" d0 x