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

杨利霞

" x2 y5 w( a3 q& g, C非常好的动态规划总结，DP总结
  N# K8 d$ Z/ e, ^
8 b9 q6 y6 K: j# Q# I, p# R详细资料请下载附件
& l' [( h4 W& r$ z" O* ^
目录  


一、动态规划初探
      1、递推
7 N# z) P# Z8 L& [8 ?. ~: e      2、记忆化搜索
      3、状态和状态转移
      4、最优化原理和最优子结构
      5、决策和无后效性
. W! X: @* {. G+ G8 h
2 p' _% W" }# j1 M
& W( J/ F5 ]! n1 r6 A二、动态规划的经典模型
       1、线性模型
       2、区间模型
, x! s! n" i. b1 f- L       3、背包模型
" ]4 P% M5 E  d# i' c0 L       4、状态压缩模型
  C' N& x5 F7 m       5、树状模型


三、动态规划的常用状态转移方程
# f1 L! l7 D5 V+ g7 x
- L+ u& c1 p6 L2 }8 P      1、1D/1D
       2、2D/0D
       3、2D/1D
       4、2D/2D
% x  O0 k1 {$ A* T9 w* @
四、动态规划和数据结构结合的常用优化
1 L9 X+ T7 ?4 R+ d6 l1、滚动数组
2 e( ?" [7 J6 a       2、最长单调子序列的二分优化
       3、矩阵优化
       4、斜率优化
9 `' p/ j  D; q# H0 K, q       5、树状数组优化
       6、线段树优化
. |( D) G' O7 D7 t# g( i       7、其他优化

# n" \6 x/ q2 |7 c$ G' `$ m五、动态规划题集整理


  X* s' ?2 r; e; k5 ~! ~# d
- D2 I( X. L% Q. h; v& V
1 T: x1 W  E9 S! y! M% g0 `
0 o# i4 n: y: l6 Z' _6 R