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

杨利霞

2 o. _8 ?9 w7 P  M+ L# U+ `$ g/ c非常好的动态规划总结，DP总结

2 L) Y8 p% [' v0 G详细资料请下载附件

目录  


一、动态规划初探
      1、递推
      2、记忆化搜索
$ M4 p, Z& ]( l! I% y; i      3、状态和状态转移
* O5 P( S; J7 K- h$ s' N8 M      4、最优化原理和最优子结构
      5、决策和无后效性
8 [1 @4 K" [' Z
& l8 H* Q6 @' m: I* _5 k
- W$ P+ @8 |' p二、动态规划的经典模型
# H: U. L' s; s: R9 l       1、线性模型
% E+ v- _- Y/ W. G6 ]       2、区间模型
# ~4 o( H* q$ D* u% o- _7 H       3、背包模型
       4、状态压缩模型
       5、树状模型
  x2 {# Z! O; z+ U) f& @
) ?& v0 P$ F, [3 L
三、动态规划的常用状态转移方程

      1、1D/1D
7 `  N. S; E5 \( P7 F       2、2D/0D
/ J: Q5 O, d6 b/ N& V       3、2D/1D
       4、2D/2D

0 O, n9 E6 H& R, k$ r  \; O9 z四、动态规划和数据结构结合的常用优化
1、滚动数组
       2、最长单调子序列的二分优化
       3、矩阵优化
) c% s. M, H, }; V. S       4、斜率优化
- G6 O5 m8 h7 }$ C# l: Y  C" \( x: a4 Q       5、树状数组优化
       6、线段树优化
" S5 e9 q$ O. b3 d/ {       7、其他优化
% D# {7 e) {, X2 `' T
五、动态规划题集整理
! l; R9 A! W6 y: w  U

" e9 s) O6 y3 G( ?
- h2 v% H: p2 K9 _) F! P
( k( @3 q* y* B1 F* f