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

杨利霞

非常好的动态规划总结，DP总结
1 l( o" Q( Z4 k) O7 F2 a
详细资料请下载附件

& y5 S9 {1 z1 ]. f% ]  ?% R  }目录  


1 \+ i+ O: `6 u" M0 ^/ _一、动态规划初探
6 ~" c" p% s; v) E/ z      1、递推
      2、记忆化搜索
      3、状态和状态转移
! u1 N) b3 [6 |  I1 D      4、最优化原理和最优子结构
  y% t! }# `; F: I      5、决策和无后效性
: d1 A0 W) b/ M9 Z3 t
5 q9 w$ A. M( d/ c: r, k2 J  |
二、动态规划的经典模型
       1、线性模型
       2、区间模型
       3、背包模型
- w  {) o- i+ V, g       4、状态压缩模型
/ v4 J  y* v% G  {8 z       5、树状模型
) x" W9 @% p' \) G6 ]8 J

% g) s& i5 u# B" Y5 u8 ^: u三、动态规划的常用状态转移方程

2 D$ Y9 G, k8 `3 ?0 N4 D      1、1D/1D
       2、2D/0D
8 H3 `& J) E* i' ^" N& v' Q       3、2D/1D
       4、2D/2D

: e: x0 u4 Z4 Y3 T" Y7 Z四、动态规划和数据结构结合的常用优化
1、滚动数组
# Z5 f4 z; \2 x( u( D1 A7 n       2、最长单调子序列的二分优化
+ c) S2 x" g4 g6 M, Q3 L       3、矩阵优化
       4、斜率优化
) z2 k& _) b4 o* X; \9 W$ F       5、树状数组优化
" ]; R! s5 d) `$ [( G       6、线段树优化
       7、其他优化
, n# x# i. W; Q" b; s( K
五、动态规划题集整理

8 J& a: |6 T& P" Y1 R! n# Y4 U/ C
$ S* c% h0 @7 K
& G) x* p8 C) E

/ i6 L& f6 H6 V( c