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

杨利霞

非常好的动态规划总结，DP总结
! F5 ?* A, {5 {4 t) {! O
, w9 _# l1 `+ J8 H, {1 Z  o详细资料请下载附件
& ?$ s" a, O& }: K
目录  
7 G7 i! B) l. \4 e( j. P7 [) h/ `) r4 {

一、动态规划初探
* m: ?. L9 ?3 }7 I      1、递推
+ g! g/ c: a2 X* M3 u4 N      2、记忆化搜索
      3、状态和状态转移
      4、最优化原理和最优子结构
      5、决策和无后效性
2 o  _' w6 ?+ b8 e
$ h# b( R) U3 s1 o8 F
2 o% Z* y, x3 Y# d/ T* Q. F9 m二、动态规划的经典模型
       1、线性模型
& Q5 A/ s8 r+ {+ {  ~9 L% ]# f       2、区间模型
       3、背包模型
' P/ J+ `" T, N  e3 C' Z       4、状态压缩模型
       5、树状模型


" B8 H4 t& M& @0 T# x6 }& f5 K$ _7 V三、动态规划的常用状态转移方程
9 R9 |- W$ I) }! Z! l
) b9 j" D& ~  Q/ Y9 M- g' M      1、1D/1D
       2、2D/0D
       3、2D/1D
       4、2D/2D

四、动态规划和数据结构结合的常用优化
1、滚动数组
       2、最长单调子序列的二分优化
       3、矩阵优化
" a$ j0 l8 c4 Q5 T% i2 l0 r       4、斜率优化
       5、树状数组优化
" E6 N3 F: f9 r       6、线段树优化
       7、其他优化
) I+ U* P5 S& c7 v# [# J3 c! H
: _5 j) N" h' x# r6 B2 _五、动态规划题集整理




1 ?6 H4 g! X7 X5 V9 H3 a- p
" u! E6 }" ~) _