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

杨利霞

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

$ S+ _3 \. M  j  w详细资料请下载附件
) \/ d$ ~& ~2 {& E+ V
. F! |* i7 S2 h$ n目录  
2 @1 A" o& H: E4 y& }& X5 _# }
2 f$ p3 F9 \) v( C
一、动态规划初探
      1、递推
8 Q4 e* Q' q; Z+ d' y      2、记忆化搜索
      3、状态和状态转移
0 i. T! u% W3 E  S/ b! o; b      4、最优化原理和最优子结构
+ b+ ^7 @% l8 Z5 |" V      5、决策和无后效性


二、动态规划的经典模型
# }1 [9 R- R; f* J5 a  E& u       1、线性模型
9 G" p2 F5 Y1 ]3 n2 j$ R% \0 M       2、区间模型
# N) `! k) }: c& @1 s       3、背包模型
       4、状态压缩模型
       5、树状模型
5 N$ |8 `! o0 F* j
$ y/ a5 T7 {1 |; P; l
2 D5 J# _: A7 t. r" q: D三、动态规划的常用状态转移方程

      1、1D/1D
       2、2D/0D
# Y7 F2 C7 t) l3 ?& h0 h2 W       3、2D/1D
3 q  ^$ e- L% z! _- n/ B- d, u       4、2D/2D
' N' [6 m3 Y$ m2 S# \' f3 B
四、动态规划和数据结构结合的常用优化
1、滚动数组
       2、最长单调子序列的二分优化
$ p& ?# e0 S5 e# g& N5 U4 K- ]5 L       3、矩阵优化
       4、斜率优化
       5、树状数组优化
       6、线段树优化
; L& j" X6 T9 I       7、其他优化
/ {$ N; `' X- Y! S
0 i5 Q3 A0 M/ d五、动态规划题集整理

% ]% |- Z, R7 B; r. a
; Q/ @( P5 G$ e$ W
9 A- W4 J9 o2 ]) X3 \