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

杨利霞

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

详细资料请下载附件

目录  
3 p+ ]. y6 b" b/ Z! T" \( P$ t

: ~% L; g6 C* P; @8 j一、动态规划初探
      1、递推
      2、记忆化搜索
      3、状态和状态转移
      4、最优化原理和最优子结构
      5、决策和无后效性
4 k0 M) V0 Y; b6 f% ~/ m

3 L! q/ F' V8 \& }# q3 K3 X二、动态规划的经典模型
! y' ~7 B% I4 T2 x6 \* t8 p       1、线性模型
       2、区间模型
, d8 U( y2 E( _  ^9 c       3、背包模型
5 n6 [6 l0 ^7 y       4、状态压缩模型
       5、树状模型
1 `, m$ j2 ^9 E

三、动态规划的常用状态转移方程
: t4 W/ t7 s" F* L0 A* l' j7 u5 F6 f" W
6 k& Y, ^* {5 H. f3 V' x7 y      1、1D/1D
       2、2D/0D
3 n4 a. d, R  f0 v8 V3 e       3、2D/1D
4 `4 b! ?5 w& `( z       4、2D/2D

. N% |% A* p1 l0 e2 x$ r, \" z四、动态规划和数据结构结合的常用优化
& U" h& o& m, t, h1、滚动数组
% Q% C/ N; g1 g/ `& y$ l       2、最长单调子序列的二分优化
       3、矩阵优化
       4、斜率优化
1 p$ C( O$ y& z4 M       5、树状数组优化
       6、线段树优化
8 H  t7 B% _+ H- h( x; w% r. M       7、其他优化

五、动态规划题集整理

& i" K! @- g! k$ z/ q

4 ]/ f6 ~* N) H$ q% G; [$ f" R. {
% _2 [$ ~& K% A: S3 z: M9 ~: G