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

杨利霞

% L3 m1 _8 r' S( q( x+ |9 C$ w- Q非常好的动态规划总结，DP总结
) H7 W. Z. F7 y
4 ^" t3 R/ p& `/ g详细资料请下载附件
) c3 N( n  Z5 Z0 o: ~/ l! f0 l
目录  

) w# |% B" R1 v% u! N" ]
一、动态规划初探
      1、递推
6 M8 m7 H5 i  n+ a      2、记忆化搜索
      3、状态和状态转移
* j/ _7 M5 R3 W$ W0 ]      4、最优化原理和最优子结构
      5、决策和无后效性
- j" a' ?. _4 d

二、动态规划的经典模型
       1、线性模型
       2、区间模型
. @: v4 ^4 h3 S       3、背包模型
       4、状态压缩模型
( N$ r# W$ ^4 y4 {5 }% g% d) Z       5、树状模型
' n$ W# S/ Y  i& n% |$ L% U- i% F- C

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

      1、1D/1D
' f: w( I2 P- G$ B  G       2、2D/0D
       3、2D/1D
       4、2D/2D

  w# g% N1 c* o2 z6 j/ n$ v$ k四、动态规划和数据结构结合的常用优化
3 e+ U# S0 k, k* |3 V& W4 P1、滚动数组
5 t+ ?3 N8 d" C" f  z; \& g+ W( R/ t       2、最长单调子序列的二分优化
       3、矩阵优化
$ a4 j! {: a* }9 o1 [/ R+ W# a8 q       4、斜率优化
3 N8 [. r5 a" j0 b1 r       5、树状数组优化
       6、线段树优化
7 |2 s4 D. e/ d- t( V; \       7、其他优化

! O# x, F# p# ~$ A五、动态规划题集整理


: o4 q. S6 A) B5 j7 _! l2 B

6 J# e, x- q/ r! }& `
# q: F  v  H; d; e; m' Q8 K  a