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

杨利霞

: z* T6 G4 B" {( }非常好的动态规划总结，DP总结
8 |, s- V$ ~+ j9 }
详细资料请下载附件
) h% d( F7 ^) Q% q6 [9 q; r
目录  

7 L% D( `  K: }8 y2 k/ Q: S
一、动态规划初探
$ |; M- ?1 }5 w% ^, x5 t      1、递推
      2、记忆化搜索
2 W/ J: e1 ^7 b& D! U  l      3、状态和状态转移
* w- W& `& z3 N3 i      4、最优化原理和最优子结构
. N4 u$ Q4 T' W& B. S! Z      5、决策和无后效性
4 @) n$ ~9 D+ z! \! E

二、动态规划的经典模型
       1、线性模型
& O, N7 V; I6 T0 D; |       2、区间模型
       3、背包模型
       4、状态压缩模型
       5、树状模型
1 s3 c7 I  n- v; F0 o6 v

4 ~" _( u6 c* T# L" y8 ]. H三、动态规划的常用状态转移方程
' W/ ^2 b, f7 |$ t: t' S
      1、1D/1D
       2、2D/0D
       3、2D/1D
       4、2D/2D
/ ]+ M, H2 ?# s; x9 `% G( ]% {
. U+ _* Q5 e% x' X四、动态规划和数据结构结合的常用优化
1、滚动数组
* e2 E" P' Z9 T9 {! b8 m       2、最长单调子序列的二分优化
       3、矩阵优化
       4、斜率优化
: e' Z4 L. x/ Y" N& X       5、树状数组优化
# O' [+ a: U4 V) Y       6、线段树优化
       7、其他优化
( U+ A0 Z+ P9 I1 {2 g# V0 E0 ]
4 G  u7 C# o" Y3 a5 |' g! @五、动态规划题集整理




7 e5 V1 I; b0 n0 [: T3 u$ |) s