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

杨利霞

7 W7 w: ^( f, z非常好的动态规划总结，DP总结
4 Q% y& S" k4 c4 J4 }6 U+ V; M6 ^
详细资料请下载附件

% v3 T) W8 |( S- V目录  
& c' ~9 f: v6 V% M

一、动态规划初探
      1、递推
! ~# y! t9 e  k+ R$ j6 L      2、记忆化搜索
      3、状态和状态转移
      4、最优化原理和最优子结构
- O6 i! b( P7 o7 D4 w- T0 t      5、决策和无后效性
9 W# Z2 q8 n5 V: |5 i+ ^$ b- G

% K% g5 f6 T; r6 i4 `0 k二、动态规划的经典模型
       1、线性模型
       2、区间模型
) P9 i2 t' I; u8 c  R2 j; L       3、背包模型
2 `# t& [1 Y! B4 u& q( a       4、状态压缩模型
; }3 T6 H  o5 l# d- c       5、树状模型
  T+ I: D# v9 E1 L6 w

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

5 m& f  a* L7 W: v. E1 g      1、1D/1D
$ u4 ?1 c! x  z% E9 V" w       2、2D/0D
( F3 U: E6 e) i6 U& i: }! F+ R4 |       3、2D/1D
) T$ C) K. \2 X' T+ C* k: {       4、2D/2D
' Y: f) i- H) ~6 \
四、动态规划和数据结构结合的常用优化
1、滚动数组
       2、最长单调子序列的二分优化
& P. F, @- f5 C. M8 B# [( V       3、矩阵优化
       4、斜率优化
       5、树状数组优化
' J; |/ f% m6 J' h2 L& p& `+ n       6、线段树优化
7 d' h3 {8 a3 j+ p# J& m% u4 `  A       7、其他优化
, L! I4 W4 a  y+ E
) C; n+ m& g" J五、动态规划题集整理


9 v9 l& L4 _9 D1 D" C/ I$ V6 b3 k2 \


& }0 `5 U/ W* G3 g& {- @