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

杨利霞

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

详细资料请下载附件
8 J7 `2 ^) j/ E& W
6 B  `! j$ o1 M2 o! H目录  
% r5 B) S1 l9 G4 V" J! A! w

; k- ?3 f& k' A" Y' y% H一、动态规划初探
2 _- }' Q8 i3 l9 C  w6 l      1、递推
      2、记忆化搜索
      3、状态和状态转移
      4、最优化原理和最优子结构
1 I) y! o; ~8 c0 U      5、决策和无后效性
. P1 q1 B8 M: {& p5 [
2 X' p9 H+ e" J1 k) I7 S
3 i' B6 \. v0 p! g0 e) f二、动态规划的经典模型
       1、线性模型
       2、区间模型
1 a5 F, T' N3 n  W+ o, G8 T" {       3、背包模型
. p" o+ b5 q) h4 Z- u( ?' }7 _( E- S       4、状态压缩模型
       5、树状模型
  t2 V4 ^. S/ F% Q' D& S: ?0 ~
- y/ V! W0 `2 t
1 R' I! G; f4 {9 [* p0 @/ A% z1 }- Q5 r# k三、动态规划的常用状态转移方程

6 X$ L: Q* q" f& y% ~6 D      1、1D/1D
% {1 }7 ?4 ]5 f6 B: G0 a       2、2D/0D
& r2 C* g+ @: t& n" z$ H       3、2D/1D
$ n1 @* q8 W$ U1 V       4、2D/2D

/ v& h! ?- j. F8 _! u四、动态规划和数据结构结合的常用优化
1、滚动数组
/ F% ]" _% `) z6 x* o3 {       2、最长单调子序列的二分优化
# {/ f/ A$ \7 b6 Y+ q1 ]# C       3、矩阵优化
       4、斜率优化
       5、树状数组优化
       6、线段树优化
       7、其他优化

! T5 S- t5 T0 l五、动态规划题集整理

* c( K( i+ p* ?" ]( q% v) G


5 J4 o5 t. w# J2 j1 _