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

杨利霞

  ?. N0 s4 [# s+ S6 @" ?非常好的动态规划总结，DP总结
# j  v# m7 P# d% B- U
* d$ ^: {6 ?9 T  k' Z+ i详细资料请下载附件
  k: p) ~1 E2 J0 ?1 P
6 F4 u3 h: i. K& H目录  

4 P9 G9 R6 f# E  s/ \' B4 \1 S
! ]- I! s, ~: A# T5 o2 K( h一、动态规划初探
      1、递推
      2、记忆化搜索
      3、状态和状态转移
      4、最优化原理和最优子结构
      5、决策和无后效性

% w1 K0 `: y, i3 ~; Z
二、动态规划的经典模型
       1、线性模型
       2、区间模型
6 m1 Q& \) N! a  o( ^; R# X& q       3、背包模型
       4、状态压缩模型
; l1 O' o1 s0 ?* `8 O% Y       5、树状模型

1 u' \2 g% P( @1 R5 U9 D
0 [, S1 {0 _+ A' _) O三、动态规划的常用状态转移方程
) Y" M& N8 U/ n0 p2 v9 D' _/ o3 w
      1、1D/1D
& G: W! h; V4 j- N& R       2、2D/0D
( @: K: Q" ^4 V8 P       3、2D/1D
1 W) M' {$ l; R7 K6 a) p       4、2D/2D

5 b3 P% I; v! i/ C四、动态规划和数据结构结合的常用优化
1、滚动数组
7 @$ e  ?6 c! _" z       2、最长单调子序列的二分优化
5 M/ i' M, m% ]9 ~3 l0 H) k! x) C       3、矩阵优化
       4、斜率优化
4 v! `- H3 J2 j1 Y' s       5、树状数组优化
1 j. C% G( F; U       6、线段树优化
       7、其他优化

0 Y! j8 X' Q* n8 I; z: `五、动态规划题集整理




% f9 u* j0 O. a. {8 j' D+ s
  g" N2 C) ^5 p+ a* j5 w