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

杨利霞

  H$ ^9 L4 d/ T) Z$ B* ?8 j非常好的动态规划总结，DP总结
3 n0 [8 y2 \6 A  v. W8 _1 t
详细资料请下载附件
. L0 P* o! w9 F) b9 c2 M6 G& o0 X) }
) T" U) |9 j3 p, y) Q, m目录  
1 T, C5 U! s3 W& H: E3 ?

一、动态规划初探
7 d6 d2 J8 y: _( i" v7 `      1、递推
      2、记忆化搜索
      3、状态和状态转移
" @$ F6 \7 _$ z. T      4、最优化原理和最优子结构
      5、决策和无后效性
: i# h8 p$ Q4 a9 A$ p/ q1 a" V

) q8 ^+ ~6 L' v( T7 L% O4 v. @6 q# q二、动态规划的经典模型
       1、线性模型
, L: U3 e( {% D       2、区间模型
) h4 {6 h9 h" h       3、背包模型
       4、状态压缩模型
       5、树状模型
8 I  @. M9 P; i+ @8 _, m

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

7 t4 S/ b: S$ @# R0 {      1、1D/1D
8 |. J, k( Q* a0 }* u: F       2、2D/0D
       3、2D/1D
       4、2D/2D

四、动态规划和数据结构结合的常用优化
8 }: L* U; h. q& X  |0 A1、滚动数组
       2、最长单调子序列的二分优化
       3、矩阵优化
       4、斜率优化
, j8 @$ O, H" R1 }2 p* e       5、树状数组优化
       6、线段树优化
# ]% B  J3 u. T       7、其他优化
5 w) s* p/ n7 Y
五、动态规划题集整理
2 u1 K$ H7 e$ V# }5 n& ^

% L+ k! V0 _. h( L$ \% x6 w