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

杨利霞

: C+ S7 D' @4 V& {# f$ i1 W非常好的动态规划总结，DP总结

详细资料请下载附件
9 l, d, u, d' G+ b, `2 c* H
3 G9 x. t5 N3 W. O6 s9 }( a  [' n, S目录  
' `, \+ x2 R9 z$ J$ Q$ i( y7 B

一、动态规划初探
      1、递推
# @8 y; }4 ]* Q      2、记忆化搜索
9 K% m9 ?+ I8 X4 u: _  D/ m' U      3、状态和状态转移
      4、最优化原理和最优子结构
      5、决策和无后效性

# U! R4 B% h& Y
二、动态规划的经典模型
5 x9 ]; i3 p9 `2 u$ Q1 v) H       1、线性模型
       2、区间模型
, g! z, J" t  B% F       3、背包模型
# X* v/ A  \( K  L# m5 N0 l       4、状态压缩模型
( G5 c2 Y2 K' Z+ t3 ~3 ]       5、树状模型


- n  M8 s. c; z, g! U1 J三、动态规划的常用状态转移方程
. p4 M: v" q* b
      1、1D/1D
3 c& _( b* z- R2 p& D       2、2D/0D
       3、2D/1D
3 R' y0 ?) \3 N& s" y       4、2D/2D

/ ^! r- p8 Z% C9 I  ~% W  X5 M四、动态规划和数据结构结合的常用优化
1、滚动数组
5 u8 ?$ B8 g& N- I$ E+ ~       2、最长单调子序列的二分优化
# Z9 V6 V' b9 f" _( z       3、矩阵优化
       4、斜率优化
       5、树状数组优化
% i* }. A9 N9 A8 c7 {  s1 {       6、线段树优化
6 H8 s) l5 V8 C( }/ U0 t2 O$ k       7、其他优化

五、动态规划题集整理



$ p4 S6 S$ E; ?& Y) l3 D) m

* p; ^5 g/ r5 J( t9 n: ]0 d