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

杨利霞

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

, J0 y" P- e; N* R0 }- d详细资料请下载附件

目录  

- B& J4 V. l; @& s7 j+ e
8 W& x4 E8 F; V& X  X- U一、动态规划初探
      1、递推
      2、记忆化搜索
      3、状态和状态转移
) R+ z6 e( \; p( ^' l, Z5 B      4、最优化原理和最优子结构
4 z& |( E/ ]( g5 @+ `7 T$ p      5、决策和无后效性

7 e  S7 x5 v5 B6 W
二、动态规划的经典模型
; v5 t$ h: @9 L( p, l2 ?' o       1、线性模型
       2、区间模型
+ y9 N4 S$ P! O. L' G4 {       3、背包模型
" j: Z+ o8 b9 h8 U* W       4、状态压缩模型
       5、树状模型
$ d/ [4 {9 R: ?8 Q/ H7 i. A

0 X5 [6 K& R+ l, s" m9 P( q三、动态规划的常用状态转移方程
  }: ~" ~  z* M0 H/ v
6 K/ G. ~3 R3 r5 }0 i      1、1D/1D
       2、2D/0D
       3、2D/1D
       4、2D/2D

四、动态规划和数据结构结合的常用优化
+ l! b; Y- @( s! O. x  W1、滚动数组
4 i9 h. a1 e3 J) J5 f       2、最长单调子序列的二分优化
% }7 R- y# t. i) w' a       3、矩阵优化
       4、斜率优化
       5、树状数组优化
       6、线段树优化
( {$ y: C1 z+ w7 Z& }       7、其他优化

五、动态规划题集整理
% I2 p' U/ U5 O
: p* D* {' c4 p  }% j) ?

" g; ?2 J  @) m* q- ^- M