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

杨利霞

8 F- V9 F: h" B) Q- K& m! Y5 A非常好的动态规划总结，DP总结
  t7 v8 l/ D7 f
详细资料请下载附件
2 ?; N' l+ n% p, v0 B
目录  


# {9 b" }& R+ G& r( j. X一、动态规划初探
# L' H+ i# J6 G. B. g! Y1 s      1、递推
: S, p+ d0 n; @9 }      2、记忆化搜索
      3、状态和状态转移
      4、最优化原理和最优子结构
      5、决策和无后效性
+ \! {+ O% {" P
6 v6 o+ j% l  l( y& z0 }
: w) i; A. \" Y9 P  K8 R二、动态规划的经典模型
       1、线性模型
       2、区间模型
       3、背包模型
9 S" o$ p2 ^! X& d4 W1 G* O+ A       4、状态压缩模型
. M4 M( r/ j6 s; \       5、树状模型


# @% ]7 b8 I5 v: E9 D5 f2 ^' [' j三、动态规划的常用状态转移方程

) D* p4 J7 W0 a" X      1、1D/1D
       2、2D/0D
       3、2D/1D
       4、2D/2D

: E: u" r- @$ E: ?" L* m1 h四、动态规划和数据结构结合的常用优化
1、滚动数组
$ T7 ~6 Y, M" I) r8 K; Y) D4 n) ?       2、最长单调子序列的二分优化
3 [2 @! K& ?) Z9 |  v       3、矩阵优化
       4、斜率优化
       5、树状数组优化
       6、线段树优化
       7、其他优化

五、动态规划题集整理
; M. A# s, E% c2 F/ O
0 Y1 E% G" J( Q/ m( h% ~

3 I2 G8 E& }' a+ y9 W5 z( {