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

杨利霞

非常好的动态规划总结，DP总结
% G4 q" z4 T' U! z1 T
详细资料请下载附件

目录  


- z1 Q# z0 p- u6 A; K8 }. L' D, O一、动态规划初探
# C% @& T$ S: n) s) d# o7 [      1、递推
      2、记忆化搜索
      3、状态和状态转移
; G( w* @) l. e! ~2 N! _- X/ y      4、最优化原理和最优子结构
      5、决策和无后效性


2 N; T- ^  y$ m; L* G& f$ a/ R8 M二、动态规划的经典模型
       1、线性模型
       2、区间模型
, \& M+ k9 F2 d2 V6 D3 P" S- ?       3、背包模型
       4、状态压缩模型
7 ]# G( N& W. Z& o" ?       5、树状模型
: @0 i9 q2 g, c# T; T% c3 Q' Z# P: x
/ F) S( S' E, t2 w- Z, P
' T; m: j- j1 {3 U; Y! y/ [  X三、动态规划的常用状态转移方程

! Z- g& A8 {9 J. R; X3 A( j6 i      1、1D/1D
       2、2D/0D
       3、2D/1D
. L* \1 U1 w3 F/ h* {2 o       4、2D/2D

四、动态规划和数据结构结合的常用优化
1、滚动数组
! e/ W- T  Z2 a$ P) V, W       2、最长单调子序列的二分优化
       3、矩阵优化
       4、斜率优化
5 {- {- z! p/ }       5、树状数组优化
       6、线段树优化
       7、其他优化

五、动态规划题集整理

4 q( u% _6 F( ]& ?  z
0 `  N8 Q5 Z* D- A
9 n" I; e4 R. }& j) V: g- h' q
# ]) O" n6 z2 I" h% H