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

杨利霞

, Q  o  j6 e7 Y+ g" l3 J非常好的动态规划总结，DP总结

详细资料请下载附件

目录  


一、动态规划初探
. Z) L) o: b: U' j, h      1、递推
; M. p+ ~4 J4 Q" f; a. B      2、记忆化搜索
. W7 s0 F! @+ d* Q( p9 _      3、状态和状态转移
      4、最优化原理和最优子结构
      5、决策和无后效性

. A: _( i1 ]- G# j+ r# F
二、动态规划的经典模型
" b2 p7 ~2 ]* t" l/ ]8 v3 T       1、线性模型
; x3 Z* k2 V( T% z% _! I       2、区间模型
  e# Y: n# `8 [( b       3、背包模型
       4、状态压缩模型
       5、树状模型
3 V: N' K4 h$ D% x
+ a4 X# Z  Z$ O
三、动态规划的常用状态转移方程

- \$ h; W3 _+ s6 W      1、1D/1D
       2、2D/0D
, C/ S. P. j+ u9 q7 `4 s( N       3、2D/1D
- I; z' h" z6 x' A2 }1 E       4、2D/2D

四、动态规划和数据结构结合的常用优化
1、滚动数组
, \3 Z. m' l  P+ n! ~# D+ q  K, E       2、最长单调子序列的二分优化
3 B3 k* Q$ o! y- r- ^) p; V/ ]9 V       3、矩阵优化
       4、斜率优化
6 N2 u% @) `: m  Z       5、树状数组优化
8 x. \5 v% J) e       6、线段树优化
9 P+ H) n5 P( j; O, z; t       7、其他优化

6 W# T7 m% B- r. S6 w3 [五、动态规划题集整理



' d/ z7 C" L( J7 z+ Q( e5 k" v