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

杨利霞

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

% Q& L, O. C* _详细资料请下载附件

目录  
) W4 w/ p- b) |% x" @& H# i7 Z

+ Q. w. H' N6 ?8 r0 b一、动态规划初探
4 z. w; w, G9 J  A      1、递推
      2、记忆化搜索
      3、状态和状态转移
% _6 f. W1 o3 l1 O      4、最优化原理和最优子结构
# N& Z2 ]- ]: F5 ]3 W2 [+ L, T      5、决策和无后效性

4 O* p8 d6 t+ q1 ]# ]# N! I- J
2 q8 k1 S# B% t* G) y) J& W二、动态规划的经典模型
       1、线性模型
       2、区间模型
7 }+ e) N* ^+ ]6 ?( K% a       3、背包模型
% I, M/ ?/ _, X4 {4 X  L& q       4、状态压缩模型
8 f9 \/ {7 [/ t  F9 l0 m8 H/ w9 G       5、树状模型


; q, e  z3 ^3 i+ s8 h. l0 _三、动态规划的常用状态转移方程
2 s) `: I; s4 m3 Y
  `* q% }. f, n7 t3 m! z5 D      1、1D/1D
       2、2D/0D
       3、2D/1D
       4、2D/2D
- H2 Y2 [3 |! v1 f  V6 X1 Z2 U3 o7 {
四、动态规划和数据结构结合的常用优化
% C, ?& D+ ~5 ]# E" l1、滚动数组
       2、最长单调子序列的二分优化
) @2 Q! [; }+ V, L8 z       3、矩阵优化
       4、斜率优化
       5、树状数组优化
       6、线段树优化
* \3 g6 t8 T$ [2 W  \       7、其他优化
7 _! }/ n* o4 N- n# F
五、动态规划题集整理
3 f2 d  j! {( i" H% g/ r5 D7 y/ N
: ]$ |8 Z+ G8 _  D, ]) t2 V

+ ]; B/ q# d5 s# `

1 a: G& e6 B# f$ S6 K6 v/ C