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

杨利霞

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

/ [  e. y: F, j: f3 f( g6 b详细资料请下载附件

" A: X$ g- S) U) G: O; I0 b2 O目录  

! C% r* D( B! I( l
5 J0 Y" X" {5 q, Z) ]一、动态规划初探
      1、递推
      2、记忆化搜索
      3、状态和状态转移
: i& y2 S) k7 ]0 M1 o- v; @      4、最优化原理和最优子结构
) D2 T6 b/ o1 \, D8 q7 D+ ]      5、决策和无后效性


二、动态规划的经典模型
1 N' c. ~7 B! c$ q       1、线性模型
       2、区间模型
       3、背包模型
       4、状态压缩模型
. v# P' o, i' T! A4 E4 {. L7 K       5、树状模型
0 x/ E& o8 @' U' l' V. t7 b3 n: r

三、动态规划的常用状态转移方程
4 g, H0 O0 P" Z# c+ {5 N# B
4 g: f7 y3 d. ^5 K' e6 t      1、1D/1D
) @& H' R" @; c$ J$ f" [       2、2D/0D
       3、2D/1D
- t) i, J! @9 A' |) {& W1 r       4、2D/2D
! [: g; ^$ Z+ c, B1 b; c
) k7 ]+ S; G1 I: {4 x四、动态规划和数据结构结合的常用优化
1、滚动数组
! {) g) |$ D9 {1 M  p       2、最长单调子序列的二分优化
# z+ s$ \' E2 i; L       3、矩阵优化
       4、斜率优化
       5、树状数组优化
/ D6 a6 \' N5 z2 L2 R3 D- Q8 a       6、线段树优化
       7、其他优化
/ |+ {7 `3 D8 y0 b3 F
五、动态规划题集整理
) V0 H( t0 Q2 s) m  R+ ?( W* W


  [/ _: _* f) f& H0 |) @
; G9 R' Z# g4 f1 I' r0 P9 x3 x