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

杨利霞

非常好的动态规划总结，DP总结
" |& r) K/ U' g( {
详细资料请下载附件
2 c5 C5 Z2 d0 I/ c/ D
目录  

+ T3 N" `" k( c, s+ [% B
一、动态规划初探
      1、递推
      2、记忆化搜索
4 z3 n9 v2 f* r  k/ a# X% j      3、状态和状态转移
& O# I- ?- |& U( c& B+ \      4、最优化原理和最优子结构
      5、决策和无后效性
8 R: U) O( y  c5 Z2 V

: q( t4 Z6 [0 J: o5 p二、动态规划的经典模型
9 L2 y* s2 f5 L9 J( |8 d       1、线性模型
$ x; Q1 B0 S; m9 |3 O       2、区间模型
4 M% f7 h* M! B4 P       3、背包模型
       4、状态压缩模型
       5、树状模型

4 _6 o' ^9 `7 ~5 x! P1 v1 C3 Z" }
1 g  X  R# T5 e; h, e" x三、动态规划的常用状态转移方程

" j% V" e  G- R- b; Y      1、1D/1D
       2、2D/0D
  ?6 D! P3 a1 v9 O& X0 L       3、2D/1D
       4、2D/2D
; I8 O& u$ j% B0 J
四、动态规划和数据结构结合的常用优化
; N, J% W5 B" X! m1、滚动数组
, [& \/ W9 b/ |       2、最长单调子序列的二分优化
6 M, i: |, {1 U; p& |2 d9 c       3、矩阵优化
0 |# a9 w) {& ?' P. E! |. @: ~       4、斜率优化
       5、树状数组优化
$ K7 J: J: M  i+ C$ l2 U+ M       6、线段树优化
7 P6 |! Q# F$ l& j       7、其他优化
* B& U5 Y0 a( B) j4 V  r8 W
9 e6 g( o$ l+ \五、动态规划题集整理

( F- S; |4 h6 c3 R' M- u  Z

' M. c0 H1 y* X9 h. x, d  o
7 j9 d9 Q9 M1 U( g/ _
$ I/ b" y: Q  n1 ]6 w0 q/ v