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

杨利霞

4 y8 M( ?! g) x: B! a非常好的动态规划总结，DP总结

详细资料请下载附件
! I+ w/ _  x) u! D
目录  
9 {0 Z! c4 E2 h( E* q" i
4 D9 K/ W: c- d5 N; J% T3 Y) A
( l& O% C+ x: J: U% N/ q3 R( i一、动态规划初探
1 p2 C8 V, A- U      1、递推
5 F3 }' A: `9 u+ [5 Q. r# y# B! o      2、记忆化搜索
* c& \. ]4 K# ^+ a* f      3、状态和状态转移
      4、最优化原理和最优子结构
# b2 J% R2 g  [. U* O      5、决策和无后效性

* g1 }" ~4 D7 |9 N6 S% h/ a
二、动态规划的经典模型
       1、线性模型
       2、区间模型
       3、背包模型
; i  B2 I. T! H2 {4 y& ], K1 ]       4、状态压缩模型
       5、树状模型

/ O8 T; c. `9 z; G3 K, j9 y; g
) H2 o% T# g3 d7 i7 `$ P三、动态规划的常用状态转移方程

, n5 n* Q% ^, X" B, t0 y      1、1D/1D
& z/ ]* R& k) ]- g) V* N       2、2D/0D
1 L9 _+ z8 R) y$ z9 k$ o/ S. L# d       3、2D/1D
       4、2D/2D
8 D: V2 ^) |! ~# ?2 P3 e6 w
$ B$ \" \: H  U* Y& l" G6 ^% R四、动态规划和数据结构结合的常用优化
1、滚动数组
       2、最长单调子序列的二分优化
       3、矩阵优化
       4、斜率优化
       5、树状数组优化
       6、线段树优化
       7、其他优化

五、动态规划题集整理


; v3 p; |/ q) n) O


0 ^) m0 \3 ?, u5 I