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

杨利霞

非常好的动态规划总结，DP总结
( a+ p- F' X1 x
详细资料请下载附件
  ?( w. A% {+ j2 J3 ]" h: o
! X% h; B+ W  s$ L目录  
) k# i# ^+ X5 J! R1 D/ t' `$ R' j
/ g& r3 K% n$ v- u) r( o
一、动态规划初探
6 q6 a2 \, {# C( x8 Q      1、递推
! |9 t3 z- t: \* y6 u. b      2、记忆化搜索
      3、状态和状态转移
8 d$ _9 N8 J1 u' L/ Y      4、最优化原理和最优子结构
# g/ L& X. D/ q7 Z) E5 g1 u      5、决策和无后效性
7 U' J; \$ {" g/ X& a
3 a2 M* K; M3 v  r
二、动态规划的经典模型
       1、线性模型
       2、区间模型
       3、背包模型
- Q- e1 H2 j6 j9 W       4、状态压缩模型
4 m. ?* E' c5 G. G       5、树状模型
4 i2 P$ U/ Q/ _0 ?

# J6 u0 e  z% q$ j; Q7 c9 o三、动态规划的常用状态转移方程

      1、1D/1D
2 v9 ?' {' r: [' T4 j* B       2、2D/0D
5 {% Z- G/ w  e& W       3、2D/1D
       4、2D/2D

四、动态规划和数据结构结合的常用优化
- w5 O% }& t0 c% Z/ O0 e" ~2 L. d6 j1、滚动数组
       2、最长单调子序列的二分优化
' S" y- p3 ?7 V       3、矩阵优化
/ a5 I" M4 w7 Z- }) H       4、斜率优化
       5、树状数组优化
7 ?8 {) w" u8 l       6、线段树优化
       7、其他优化

五、动态规划题集整理

* P6 Z- l7 Q4 L5 a