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

杨利霞

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

详细资料请下载附件
) g; b- o6 {# n, Y' o1 S
目录  


  h0 f: s. D0 Y/ S, Z一、动态规划初探
& R/ B  x* R( L. `% M      1、递推
, E; @' P5 J. |' B  m+ v0 n      2、记忆化搜索
      3、状态和状态转移
. u+ B. v% W( v% ^' H/ X" u      4、最优化原理和最优子结构
0 v$ A$ M4 G: ?9 e      5、决策和无后效性
  V5 `( @! h/ ~: v1 I" _6 n
/ A# @" Q5 ~' S0 h% V; \# c: j5 o. ]
9 A6 y. R( X' l$ o1 z4 s二、动态规划的经典模型
5 E2 q# v7 v6 r6 z       1、线性模型
# P/ ~+ n( w2 V/ [5 p       2、区间模型
0 X; Z( u, V! y       3、背包模型
6 ~$ M! i" p. r. E9 B7 @       4、状态压缩模型
* _6 U/ Z2 k( D' }5 ^* [: w5 h       5、树状模型
. F8 f5 H- r' z9 W+ X6 n1 Z
$ C- G7 i) Q4 S
& }6 H9 d) I+ k三、动态规划的常用状态转移方程

9 Y5 F1 X& ?: X# C      1、1D/1D
, _+ a- C3 f% l: ~, R       2、2D/0D
1 k( \0 k, ]1 h  o  x       3、2D/1D
, g9 Z4 T7 W. B+ d# t       4、2D/2D

四、动态规划和数据结构结合的常用优化
1、滚动数组
" {) a- f% j. w       2、最长单调子序列的二分优化
1 Z2 j% o  c* D: f4 I3 f0 V       3、矩阵优化
5 k, R% @: v/ J$ }: Y% \       4、斜率优化
       5、树状数组优化
       6、线段树优化
       7、其他优化
2 O) t: g# z' H7 g3 i/ [+ b
五、动态规划题集整理




( w9 |: v+ b6 \: l
6 z2 B6 g2 \7 H