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

杨利霞

! K' G. l/ v9 s0 `非常好的动态规划总结，DP总结
" j* G# ]. K' N0 s$ O% d- e
4 n/ X' v5 t& u0 n- j详细资料请下载附件
  E( j- w1 C5 F
1 O! r2 v, o+ t0 u目录  
* Q$ u! d, A/ U! ?$ Y
& _6 G; b4 |" L- z; J, P
$ ^7 N  o4 Z+ l4 C+ ?- Z) O! O一、动态规划初探
1 T7 R' n. z4 o/ }; R      1、递推
; i* T+ E+ X  N, L7 }      2、记忆化搜索
% j  X) H  v0 j      3、状态和状态转移
      4、最优化原理和最优子结构
      5、决策和无后效性
; {; S0 l! G7 g

* c! z% ^2 i& P* \6 n0 Y3 T二、动态规划的经典模型
. O/ s/ U! R: Y6 H  l& _       1、线性模型
       2、区间模型
" e! q' n$ ~6 F# Q       3、背包模型
) w& m& P7 b$ \       4、状态压缩模型
( v3 u1 C. F( ^! j6 w( b       5、树状模型

, R* Q  g- F* I0 ]5 u( F6 h
三、动态规划的常用状态转移方程

, T4 i0 g- |! Y" f" B8 K; R0 O      1、1D/1D
       2、2D/0D
/ i3 G" b; a: l- T8 H- Y: B, U       3、2D/1D
       4、2D/2D
4 o- Y& u( P" L/ I3 ]. n- ~- ~
6 q. v6 P' Z' U3 t3 Y* ^. ?$ z6 J四、动态规划和数据结构结合的常用优化
1、滚动数组
4 m' @1 a: @4 w) i       2、最长单调子序列的二分优化
       3、矩阵优化
       4、斜率优化
       5、树状数组优化
       6、线段树优化
7 p+ s# y& L4 S2 a/ R1 c       7、其他优化
) P5 `! ~4 x; S  L7 d
五、动态规划题集整理
4 x4 P& G2 d# k6 O' c3 X4 J, y
& Q& n3 Q( h; @" ^* x& ~0 b: @: f1 |


# {0 I# C. L/ o" T' N2 ]
8 s5 i% ~& \  B$ R7 j! {- o