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

杨利霞

6 H# Z" [# p: b非常好的动态规划总结，DP总结
! v* |% L! M. y4 ^2 c$ H
  L/ I& a& k8 z详细资料请下载附件

目录  

" R* L/ F: R8 |4 l% @) E
一、动态规划初探
      1、递推
' D/ H( u7 Z+ _5 j+ k      2、记忆化搜索
      3、状态和状态转移
. v% i- N$ R. ?; Z      4、最优化原理和最优子结构
7 M5 z+ U1 s) n3 d! }+ Q      5、决策和无后效性
, [2 r2 b9 ]9 e4 ?
0 @8 T! F! w# k9 m+ \
二、动态规划的经典模型
2 p) I% j, P, \  c       1、线性模型
       2、区间模型
       3、背包模型
- w* O; e( Z* x* A. E) p       4、状态压缩模型
       5、树状模型
! E( Z& h0 V& t

& I6 }4 Y- {7 O7 ?8 W9 Q三、动态规划的常用状态转移方程
) C* p! q2 G- H
      1、1D/1D
       2、2D/0D
       3、2D/1D
( o# L  q: _7 W. I+ G% z/ k       4、2D/2D

8 |) K8 c+ B, X1 B四、动态规划和数据结构结合的常用优化
5 z; N$ Z+ o. `1 Q1、滚动数组
7 Q. p" G* T( Z5 `       2、最长单调子序列的二分优化
9 d+ w! g1 B( |0 A       3、矩阵优化
       4、斜率优化
) U4 @& q! q; D* k! j       5、树状数组优化
# H9 k' u: q8 }: n4 ^       6、线段树优化
( ?# w+ ]! W5 _$ V8 V       7、其他优化
6 C- T( q2 i) L4 {9 y
2 q. V1 p1 Q2 Z/ h4 n* Y五、动态规划题集整理

. ?; l8 ~4 b+ ~) C  `5 ?


: S% E/ T" a$ d$ N  [4 v( j; b