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

杨利霞

非常好的动态规划总结，DP总结
9 d8 W2 d) A8 V: ]" O5 K5 B$ y
详细资料请下载附件

目录  


( V) J; s5 w4 }7 a一、动态规划初探
' N$ Z% h! V4 A      1、递推
      2、记忆化搜索
- D* l. k2 F  d/ i# o) l# x* o6 |      3、状态和状态转移
' g5 w# Z8 ?' e      4、最优化原理和最优子结构
      5、决策和无后效性

4 g3 h7 g. v5 D5 b4 A' w4 v
( b- K0 E0 O' l6 A3 x! ^* }5 X$ a二、动态规划的经典模型
' m" M+ l% B" o       1、线性模型
       2、区间模型
% V5 Z1 _  s/ o" ]       3、背包模型
       4、状态压缩模型
       5、树状模型
& |% H1 b% q, N/ b( x
" ]. g/ n) f! @: k/ O1 Y
三、动态规划的常用状态转移方程

      1、1D/1D
7 H9 p3 B( V! m" l       2、2D/0D
8 z/ g1 @# \  e3 L, _       3、2D/1D
       4、2D/2D
5 Z1 L- Z0 ~. _- p% t
四、动态规划和数据结构结合的常用优化
, I7 j4 ?) Z# B6 P, r1、滚动数组
+ x: ]! I2 [/ `; h       2、最长单调子序列的二分优化
       3、矩阵优化
       4、斜率优化
       5、树状数组优化
       6、线段树优化
       7、其他优化
* _/ Y5 p6 X9 v0 {: i3 y
五、动态规划题集整理
0 J: a; M. z; Q, T5 w6 G
" U6 }  e" z) Q* ]
3 d; V; ^2 G; ~( I5 M# L, T
2 F# K6 }3 U2 c, X

5 p% }% L) T! o, y1 ?6 t  \