数学建模社区-数学中国

标题: 非常好的动态规划总结，DP总结 [打印本页]
作者: 杨利霞    时间: 2019-3-27 15:10
标题: 非常好的动态规划总结，DP总结
; z7 t) C3 B6 U/ {: i; S2 W4 c
非常好的动态规划总结，DP总结
1 }6 T& n- O% p# ~: I/ T" R  {& C% }3 B8 U$ Z
详细资料请下载附件6 Z5 Z% {  e) p! u4 g" R4 o
5 R5 q# ?" w6 ~+ J  a2 j3 y, C
目录  & x; q; j* C5 ^$ n
" k' S' \: G. C) ~$ y9 M
  R% L- p# ~2 k
一、动态规划初探! Q! q% x& s3 u5 G
      1、递推3 f. t. T! u2 u
      2、记忆化搜索, a  `- o/ n0 F# z
      3、状态和状态转移  Q+ l! ^3 s8 [. [5 k: t- `
      4、最优化原理和最优子结构2 i' E) g$ f8 ^7 b
      5、决策和无后效性  z( n* Q9 x- \+ Z; x! a( H: z
& Q* ]7 W( @0 o+ E8 ~
: y% f+ s  M. p  p( L
二、动态规划的经典模型
8 {( Z2 j! t4 F) V  F       1、线性模型
8 o) G2 Q: T" I  G, U# Z& H4 j/ H       2、区间模型5 `2 q6 h8 {2 K) V$ b$ I* n
       3、背包模型
+ T+ d* }, |2 j8 i( R; U# w       4、状态压缩模型1 T  Z% g4 p" H/ D
       5、树状模型
  G' i0 ?7 n. v2 j0 S, W0 P) T& @
9 b$ o3 ?# A! b
6 G9 T+ F+ A- T$ {; o+ s/ w三、动态规划的常用状态转移方程
6 t; Z, H9 U+ \4 B8 U4 n3 o0 h& f3 V
      1、1D/1D
) K, f1 m5 X. E/ U* q" l9 ]       2、2D/0D
0 x# T) i3 A0 r8 ~- s       3、2D/1D$ L8 y9 O, D# T' U$ v
       4、2D/2D
# Y3 O" @$ S! M& [- \! l; y; P5 I1 d$ B
四、动态规划和数据结构结合的常用优化
" ~9 ~. t* c1 k/ L7 L, K1、滚动数组* S  ?2 Z# f7 T9 v& E! B
       2、最长单调子序列的二分优化8 I# L% v- z1 J3 X7 D. S4 B" F6 F
       3、矩阵优化, d3 M" d) S: {& l4 t1 x
       4、斜率优化* e  L0 |9 A- W' m
       5、树状数组优化: P6 V, x0 a! t# y! }. M& ?3 g3 J
       6、线段树优化
  B" r6 D0 V2 Z       7、其他优化$ m" I% `% |+ D1 O" V7 j# L( z& v

2 U; L0 [4 e- ^( I五、动态规划题集整理! P" ]9 {9 l3 Q

- y6 d; ~" y$ G8 p1 R* c* m& D  e4 k9 Y# R* w

2 a6 f8 Q/ j' G7 i3 d; Z( Q- A: z- a* A% ?0 x

1 W4 q  g* P( y/ [  Z; n) M5 v3 \

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

234.57 KB, 下载次数: 9, 下载积分: 体力 -2 点



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5