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

杨利霞

% m3 N- O( d' ~3 c: ^  f7 z非常好的动态规划总结，DP总结

% ^/ j6 S% n4 l$ K' r详细资料请下载附件
# k) N4 m/ Z: q/ a9 c$ P! e
& D) q! {. V5 _/ ~) r目录  
. d: o6 g- R0 D3 H. b# t

& B: x( q- w6 X. t一、动态规划初探
0 h+ }! T; X: l! M. ^: H  \      1、递推
2 G$ s. |4 W2 H- ?: _5 L4 S, l0 X      2、记忆化搜索
8 m- {' X4 c! Z. f5 |      3、状态和状态转移
$ K" b& k% m- u& }9 v# m6 T      4、最优化原理和最优子结构
  j( t- Z& ]0 ]9 B* a- @      5、决策和无后效性
0 `1 m1 Q& H6 t  o7 A$ e
1 A! f& c3 m7 j6 O8 {5 K
, f% {1 R: f4 M& Q$ c2 b" e6 ?二、动态规划的经典模型
       1、线性模型
       2、区间模型
       3、背包模型
       4、状态压缩模型
4 ~) d1 S5 K( Z; R" _" Z: Y       5、树状模型
$ k0 J* p# I. o( e2 d2 Z! F+ P

; `* A2 p# J, V; x' s! M  W* f9 I三、动态规划的常用状态转移方程
, o( ~) j3 n5 s5 t( ~, r
  Q' _8 r2 M0 u1 k# C      1、1D/1D
       2、2D/0D
9 k  t5 `+ u5 p" X- W. ^3 B' p       3、2D/1D
, P: ~0 i+ A, j! ?3 ?       4、2D/2D

; ?$ y$ d. v7 ]) u) {* ~1 w四、动态规划和数据结构结合的常用优化
1、滚动数组
/ C6 z5 `# i0 p" g& t( W2 @" Q       2、最长单调子序列的二分优化
! p6 |( q& W. N) T( k5 m* @* s       3、矩阵优化
       4、斜率优化
       5、树状数组优化
       6、线段树优化
3 A1 ^1 a, {2 P& \% S       7、其他优化

五、动态规划题集整理

& O  E: I) C& X) G2 `$ O$ v' X. O  F
/ J+ k4 @% z% |2 O

/ H5 R/ w! I" N
' z9 f$ D( A5 r0 f* g+ r! J" V