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

杨利霞

非常好的动态规划总结，DP总结
# y7 E3 Y* ?0 Z' U6 V
9 \1 ~& Q( A7 g4 A详细资料请下载附件
6 a' a" Y* u# `  S5 X; `/ p
6 s# ^5 E6 b1 N$ ^; m  b; G4 R- Z目录  
7 i0 o2 }5 v' Z" p8 ~

一、动态规划初探
      1、递推
" c4 @7 R" N4 I- M. f; L      2、记忆化搜索
      3、状态和状态转移
      4、最优化原理和最优子结构
      5、决策和无后效性
- ~- p, M+ v1 U

6 Q5 o8 n, X. D) z; g二、动态规划的经典模型
       1、线性模型
       2、区间模型
2 d, G3 y% ]: n! Z       3、背包模型
: K7 Q+ u* t) c) o0 u       4、状态压缩模型
2 c4 a. W4 X+ K2 Z" @       5、树状模型


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

      1、1D/1D
       2、2D/0D
       3、2D/1D
       4、2D/2D

四、动态规划和数据结构结合的常用优化
% B  @: P7 U) V, }1、滚动数组
       2、最长单调子序列的二分优化
5 u1 W' L: K" d       3、矩阵优化
       4、斜率优化
       5、树状数组优化
       6、线段树优化
7 `4 U8 f: A0 W4 X       7、其他优化
, q; Y' T0 }5 @& o& r6 C
五、动态规划题集整理

% L  b5 m2 D& N- e) M( n
) V% {9 s% L! b/ D/ s
+ q3 K! e* @, }8 j2 W

" d( v. F( W% f3 V: h