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

杨利霞

非常好的动态规划总结，DP总结
3 |- w  f& L# i  I
' d: K, c9 i- D- m$ v详细资料请下载附件
5 W* ?" i& p/ P9 D% r
目录  

" p& |% `$ V9 V3 R  B+ ]+ s" x% ^
一、动态规划初探
      1、递推
      2、记忆化搜索
      3、状态和状态转移
      4、最优化原理和最优子结构
  n4 o5 w3 l) e9 N% s9 h      5、决策和无后效性
( B3 O$ b1 W" S, q
& R  C% h- ~0 r
; H0 p, O! `; N5 x4 p二、动态规划的经典模型
       1、线性模型
' s: v+ i  ^3 n' M3 N8 c       2、区间模型
- R* f, G; N- l+ D7 f, a       3、背包模型
% R" _* x3 _% P: D5 [# c; ^3 K/ i) o       4、状态压缩模型
       5、树状模型
; D/ P! m# V( a

! c' T" w) s' l- W- z三、动态规划的常用状态转移方程
8 ?' E9 H' w/ g7 h$ v
& o: A" a6 M0 ]  p; b, ~      1、1D/1D
       2、2D/0D
       3、2D/1D
       4、2D/2D
0 G9 B- W' e% j/ x4 V. `
; {9 s" G, x& r# u% q* p四、动态规划和数据结构结合的常用优化
1、滚动数组
       2、最长单调子序列的二分优化
6 ]% L) t3 D6 F9 o) H       3、矩阵优化
       4、斜率优化
       5、树状数组优化
: f* B/ A/ B/ b' y7 T       6、线段树优化
& u% n0 F) @' V       7、其他优化
5 m0 p9 b' S6 i9 b/ n+ ^3 ]3 H( _
五、动态规划题集整理

/ B2 M4 U! B" s4 e
) y) ^( p  A1 W0 f0 W+ L0 q

1 {: U5 W" q9 O. c5 i9 s0 b
% d$ R: C, E' p8 H/ J  F