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

杨利霞

) l3 e3 W1 C; ^, _& X. J. X" v非常好的动态规划总结，DP总结
4 K8 C( N7 a- ~- _& d0 _
. l% ~$ v% l5 J! e* M# c) j5 k详细资料请下载附件

! @3 ]5 |( |- h目录  


一、动态规划初探
/ ?' t  w7 ?; y  K. P# R% D      1、递推
7 N# f. d; Y1 e" O7 G9 o      2、记忆化搜索
+ z: z5 P' I* L1 H& {. x/ |! G/ \      3、状态和状态转移
& L* d: b2 t" i6 n& j) h+ z      4、最优化原理和最优子结构
      5、决策和无后效性
! `2 W8 x" Y  q" W. _/ i6 a

( [2 S7 B( h* A6 F/ s) @, j二、动态规划的经典模型
       1、线性模型
       2、区间模型
' Z% q. z4 X( Z" Z% g& P       3、背包模型
       4、状态压缩模型
7 g' t2 J9 ]* |4 h- K1 J1 e1 g% P       5、树状模型
$ K+ F, J- n8 c3 q( }* b- O  Z9 Q# I
$ K% s$ r- I1 O* y& U! N! t
: l: u& G$ L( B; n三、动态规划的常用状态转移方程
) r& H; k" {- |$ b& @
, O. ]/ I( L7 g) o      1、1D/1D
* F  a# f3 Y' t+ a: K( ]       2、2D/0D
       3、2D/1D
7 Y# O0 u/ r# w       4、2D/2D

3 i( I4 P  a- K8 w: F+ I四、动态规划和数据结构结合的常用优化
4 S! E) ~7 R: ^- h0 n) e8 r; ?3 e5 x, ]1、滚动数组
       2、最长单调子序列的二分优化
3 G. u9 S  G! k) d       3、矩阵优化
% m* Q' I$ n& w; S2 }/ C: a       4、斜率优化
       5、树状数组优化
, m# }7 q# T3 k* x- k       6、线段树优化
       7、其他优化

五、动态规划题集整理

/ z& {/ \' N0 N. F/ O# o
$ c1 T+ ]  k; P