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

杨利霞

非常好的动态规划总结，DP总结
2 E! C( @) R5 J  g: M/ F% [
详细资料请下载附件

目录  
  ?6 r. |) w) `6 h

; n! ]+ t. Y7 M6 `: @) M一、动态规划初探
      1、递推
. ?6 u3 q% Q, Y) U      2、记忆化搜索
# [; T) f& E; Z2 u9 m$ H8 A      3、状态和状态转移
      4、最优化原理和最优子结构
* N; r3 O1 y5 y( P" ^      5、决策和无后效性

- a; s! a. F9 `, p) ^% e
( y' l6 o5 o/ {( D9 {7 I. ^8 p& Z二、动态规划的经典模型
       1、线性模型
) E5 f& Q, |6 ?& x       2、区间模型
       3、背包模型
! G5 ]0 l9 Z. r1 b4 l: v$ d( ^4 I       4、状态压缩模型
       5、树状模型
: R9 X4 Y& [  b

三、动态规划的常用状态转移方程
% }' P& C! T( Y; L
, h' {5 Q- G+ @( z9 y      1、1D/1D
/ [% Z8 t4 m9 n       2、2D/0D
3 f/ v8 v3 C) q5 d! F) t( ]       3、2D/1D
       4、2D/2D
: k+ Z0 r& d5 D/ o( [- ]0 N
- Y1 `" C4 h: c2 |# L1 e四、动态规划和数据结构结合的常用优化
1、滚动数组
       2、最长单调子序列的二分优化
+ |  n9 K6 Y9 h       3、矩阵优化
- c6 @9 R2 t* v+ p: B8 @       4、斜率优化
/ \/ y! T. M4 K, ?  x) E       5、树状数组优化
7 ^- N8 G9 _# d       6、线段树优化
( h5 _6 D  ?" V. g) X3 _, Z# w: B       7、其他优化

五、动态规划题集整理
7 x8 D2 a9 @& Z( o. z) B+ G



# ]" O  {  O, G% ~, a# W$ t
0 \1 S5 ]3 e3 q; ~4 G# O+ f