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

杨利霞

非常好的动态规划总结，DP总结
4 f2 C, q* W+ Q$ K3 t& r7 t" j
* H" Q* L0 y( E: N详细资料请下载附件

目录  

$ ~( V9 A7 l2 [2 m$ y
4 \9 ]" _: `$ F3 H$ s+ T, l一、动态规划初探
      1、递推
      2、记忆化搜索
6 n- c4 e# g! F      3、状态和状态转移
      4、最优化原理和最优子结构
. C8 V0 g0 h- ?1 L5 r      5、决策和无后效性

  u4 P. i4 n+ n# s3 \# q
二、动态规划的经典模型
       1、线性模型
       2、区间模型
       3、背包模型
       4、状态压缩模型
       5、树状模型
% Q- d9 u7 q6 m! N3 ]
. k- Q, W. Y6 z& b* V
三、动态规划的常用状态转移方程
" T/ N) z- X- R7 w% q1 V+ N0 a5 m
      1、1D/1D
       2、2D/0D
( k  |" M2 |6 l) q0 K+ h) R4 \' E       3、2D/1D
       4、2D/2D

四、动态规划和数据结构结合的常用优化
1、滚动数组
# O% @. O9 L, R; Y9 ~' {       2、最长单调子序列的二分优化
       3、矩阵优化
" J2 d' a- i' _  r' o# }       4、斜率优化
       5、树状数组优化
       6、线段树优化
6 H$ Z8 F, x0 p1 [7 F       7、其他优化

1 [/ Z+ B+ v( x5 B/ n五、动态规划题集整理
8 s3 Y+ r- Q- n6 r. L. U4 q: Y% C* f


2 ?3 Z4 ]1 D4 F& r3 k