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

杨利霞

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

. y% @+ ^, \1 }8 I详细资料请下载附件

1 d: g# d" q' |1 o3 ?目录  
' [# K* [4 ]9 Q3 y4 H
, |" j/ J9 N6 A: O: c* s) h
5 p: L* {' a) p7 R% q' T一、动态规划初探
      1、递推
      2、记忆化搜索
      3、状态和状态转移
1 T% ]6 d8 E/ ]. _      4、最优化原理和最优子结构
      5、决策和无后效性

# q) {% d" ^: t" V+ W$ y
二、动态规划的经典模型
2 H" {2 D. c2 r) R0 V& z* G/ b1 v       1、线性模型
( p) Q( I& b2 t: l6 C8 J9 i  K       2、区间模型
2 T& ]9 ]+ B& m8 [8 o- _# e0 P       3、背包模型
       4、状态压缩模型
       5、树状模型


1 Y& j1 B! q* j% Z/ |" }三、动态规划的常用状态转移方程

      1、1D/1D
       2、2D/0D
$ O( I( N$ q* r4 F       3、2D/1D
# V1 F' {2 v. v4 Z. c       4、2D/2D
- A: Y: g/ c0 i/ ?) \
0 k/ A0 l2 c2 `: U四、动态规划和数据结构结合的常用优化
2 f0 K2 j! i' u+ u# h2 J! \( c1、滚动数组
7 o  w! ^/ R8 j       2、最长单调子序列的二分优化
8 v. g) z9 d6 ^7 q       3、矩阵优化
6 h! q  _- H3 W+ i2 d  f6 k. w       4、斜率优化
       5、树状数组优化
       6、线段树优化
$ b. V, l5 [7 d3 x9 ]: X5 `$ X9 R       7、其他优化

6 E9 l& M) p! I3 Z9 t五、动态规划题集整理




$ z2 A0 ]( D% a, A* N% o