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

杨利霞

6 c# |" p6 ^, e非常好的动态规划总结，DP总结
, M8 ?: D, i( f- C% h% \6 i( e+ o
! e" M* W& g8 P6 H$ E# d7 d8 n3 U& i详细资料请下载附件

* T( r2 ]6 m* P" j+ |8 i目录  
/ g# f0 b, c" r
7 A- e+ W; g' L& a% N+ Y
一、动态规划初探
      1、递推
+ [% z6 h" D; @6 z" e1 R/ c0 T( D      2、记忆化搜索
      3、状态和状态转移
  N, W- t* G* U      4、最优化原理和最优子结构
      5、决策和无后效性
( @4 V$ i: y* [  c$ V

二、动态规划的经典模型
7 f1 o; }0 ^* z! U3 k; P       1、线性模型
       2、区间模型
       3、背包模型
  Y, a' ?. ]+ {. y2 x       4、状态压缩模型
% V! C/ ^1 h9 M, @1 Z: G% T* m* S       5、树状模型

: s1 Z- u# g- ^7 Z, g, r( D* p
  e7 P& y! ]5 z3 m三、动态规划的常用状态转移方程
8 x: H$ n2 U( N: D3 v
3 h: f, m' b2 \# b      1、1D/1D
       2、2D/0D
       3、2D/1D
4 n2 E0 _4 }5 g# H' s& d# k       4、2D/2D
2 Y* J  O6 j$ m- b$ }! L
1 ~- f0 S* j  N( t2 L: `+ ]四、动态规划和数据结构结合的常用优化
% n, m3 d+ t" v: }8 f" c2 v3 \0 J, c1、滚动数组
! N$ N$ J# }1 @4 _4 s! K/ _0 h       2、最长单调子序列的二分优化
) m6 d! t, J# m' e       3、矩阵优化
       4、斜率优化
% v+ N7 d1 d! A8 q6 }       5、树状数组优化
       6、线段树优化
/ [! F- f! V% s% Z7 ~* F% p       7、其他优化

五、动态规划题集整理


. l# P+ m2 h3 h2 K' T) N" |


1 ?/ E) o2 j& x# h4 b! u3 B