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

杨利霞

8 S! I, @. w9 ?5 d非常好的动态规划总结，DP总结
# y8 D* d2 H' T1 c
* o% B; u# Z/ V7 }详细资料请下载附件

目录  


一、动态规划初探
% r, w3 f2 y" N) Z      1、递推
      2、记忆化搜索
      3、状态和状态转移
7 W3 B7 C+ O( E( x& a( f) M4 a      4、最优化原理和最优子结构
      5、决策和无后效性
5 q: G6 i$ ^3 q5 ?: m
, h; f  M# ?$ Y+ Q: D, Q9 x
二、动态规划的经典模型
       1、线性模型
$ [: H' O/ W$ `3 L       2、区间模型
" C6 E0 t" p) A5 K6 Y; N6 u       3、背包模型
, W9 J4 z8 d4 A$ h- M       4、状态压缩模型
  x! i0 W7 M( D3 v8 P( J       5、树状模型
# N! Z) o; `. T
9 G7 G- r9 b% m* p5 \
三、动态规划的常用状态转移方程

      1、1D/1D
       2、2D/0D
8 J4 W  s: C0 Z/ p! Z       3、2D/1D
+ E5 P" w$ A; v$ M       4、2D/2D

: n8 [* M1 |1 L3 @2 S2 Q9 p四、动态规划和数据结构结合的常用优化
1、滚动数组
0 D2 C! Y. W1 p5 M( L4 Z       2、最长单调子序列的二分优化
9 a$ B8 s8 ~$ f! |9 N       3、矩阵优化
2 W7 R% n; ^3 C' I' x       4、斜率优化
) s2 l2 c5 ]8 N9 o       5、树状数组优化
       6、线段树优化
  J+ M; q7 j- U7 p3 n. Y       7、其他优化
, w" g; ^4 h: |
, P/ M# ^6 g) E, ?: J1 @五、动态规划题集整理
( k* r. D& K3 D3 w  D6 b3 y: T


* d9 H5 O1 y% x( o3 n3 l
" m/ o8 D3 h6 M' i3 T. o  z+ v% X% ^
/ I& r; B  Z1 ]