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

杨利霞

8 H/ j4 O! _2 x) H# l/ v非常好的动态规划总结，DP总结
+ ?& R/ Q5 V! u# ^
详细资料请下载附件
+ J3 v5 r) U) d% |2 ~, D
" _# h/ z( a# v7 `1 o( Y目录  


一、动态规划初探
$ ]7 k+ U7 d8 \1 N      1、递推
      2、记忆化搜索
      3、状态和状态转移
      4、最优化原理和最优子结构
- b' X8 ]7 K: A4 n" `2 `      5、决策和无后效性
& R3 ]( p: j, U/ _

4 y8 F/ U  F$ I, D1 {$ v2 ?/ [) S二、动态规划的经典模型
       1、线性模型
       2、区间模型
3 L. R) F$ O( U' M# ~6 B. @/ r) d# E       3、背包模型
1 [# u' {% U" M8 V# y) a5 e! |       4、状态压缩模型
4 a: O# R! M( X) M3 |) a$ m& j+ [       5、树状模型


三、动态规划的常用状态转移方程
) C6 T! x. v! T* _  ^8 m, M( b
      1、1D/1D
       2、2D/0D
       3、2D/1D
& [. P0 `) Q5 @: T       4、2D/2D

% P  V) P* R+ G1 ^# ]: |" C; N3 l- Y四、动态规划和数据结构结合的常用优化
4 ?' Z: M' x: M3 ?8 A8 {  I1、滚动数组
       2、最长单调子序列的二分优化
       3、矩阵优化
  M+ }& R- U. y; w* x. X2 g% E- z) H       4、斜率优化
       5、树状数组优化
       6、线段树优化
       7、其他优化
! J9 y+ Z* k' I7 U' E! h( x1 h
五、动态规划题集整理


. _* U' m) w5 a; f& O6 F; E
0 d2 D, w- J) V. V2 |

7 d8 g* F" z9 X7 \& v( H% H& _7 b