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

杨利霞

非常好的动态规划总结，DP总结
( n0 Y8 E9 v- P4 {4 W
, T0 K/ a& r3 ~. [, {详细资料请下载附件
9 j4 A/ a) C8 }% o3 w
1 W8 f( k3 c0 ~; @  t# I: o目录  


一、动态规划初探
      1、递推
/ w. U0 L  i9 q; H4 W" V4 @      2、记忆化搜索
( g8 x6 U% C5 u  H( K* e      3、状态和状态转移
' w1 f) e; B4 K: c6 j1 |8 }      4、最优化原理和最优子结构
      5、决策和无后效性
! \: m- N. {8 r9 u+ k
/ [, s3 C( p8 W, C' n8 j6 W
. l7 G4 S: b1 t二、动态规划的经典模型
       1、线性模型
$ ]  z4 a' e) O' t8 v       2、区间模型
       3、背包模型
       4、状态压缩模型
       5、树状模型
; R+ F8 ~( g. c3 K% W/ `5 ~5 \

三、动态规划的常用状态转移方程
5 R! O8 w7 ]# e* I7 v8 x1 b
      1、1D/1D
       2、2D/0D
, B) A- \" ~# K( g       3、2D/1D
5 ^  a. A* Z: v6 ]  Z       4、2D/2D
! E: U/ j6 v0 M& g3 ?, f% h
四、动态规划和数据结构结合的常用优化
! k. ?- F, d; |9 B6 P5 l1、滚动数组
       2、最长单调子序列的二分优化
       3、矩阵优化
       4、斜率优化
       5、树状数组优化
! o# O/ {$ A5 {8 O* ^       6、线段树优化
       7、其他优化

6 U2 t' p8 S: m. Y6 W8 K6 M, n五、动态规划题集整理
; k5 d) {7 m# x. S* F
$ ~$ k3 G/ o5 n, z


2 p' q4 Y6 |, h/ r/ i% V# ^' z1 a. H