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

杨利霞

1 l7 x6 Q4 k0 L2 g非常好的动态规划总结，DP总结

详细资料请下载附件

目录  
' q: Q7 ]/ I1 _0 t
6 v% o# L- N( ?5 m: C# d7 |
一、动态规划初探
      1、递推
1 z# ^7 Z2 J6 u      2、记忆化搜索
      3、状态和状态转移
      4、最优化原理和最优子结构
  B' [6 F) U2 U; t, H9 c      5、决策和无后效性

0 u5 Q1 a; H" `' W* g4 S
! F. s2 {8 z( i& V6 p" L二、动态规划的经典模型
       1、线性模型
       2、区间模型
       3、背包模型
       4、状态压缩模型
! B* B1 X! M& Z4 ~. [- n       5、树状模型


三、动态规划的常用状态转移方程
5 L+ N- }% n# a  `" `
      1、1D/1D
9 j. r7 I$ R  r& W3 V0 T2 [/ `       2、2D/0D
       3、2D/1D
       4、2D/2D
' r+ M/ H2 J" h
四、动态规划和数据结构结合的常用优化
8 i# j$ z" C* \: O: M. z  j1、滚动数组
       2、最长单调子序列的二分优化
( f5 V" t0 l# G' g8 W2 b( I) y1 x       3、矩阵优化
/ ~/ s- V3 h' M0 @  I       4、斜率优化
! S4 h' T) h, C& j+ A& o       5、树状数组优化
       6、线段树优化
9 N7 p* H9 w1 w4 d       7、其他优化

五、动态规划题集整理

- v9 N* L0 k8 B/ i6 d


' O8 p: n% |" @3 Q
  h. M4 Z& p4 v