数学建模社区-数学中国

标题: 非常好的动态规划总结，DP总结 [打印本页]
作者: 杨利霞    时间: 2019-3-27 15:10
标题: 非常好的动态规划总结，DP总结
. z7 @/ n2 O, e5 s1 f% D
非常好的动态规划总结，DP总结# F- W1 ]" c  T- \+ {9 V: c/ m

& `$ u5 ^* b: J9 r) q详细资料请下载附件
# i$ G: B/ {$ e/ x  f: S6 w; {7 Q  _, w$ ~- w: G: Q$ e
目录  
' a% m& [2 Y: R0 |. S7 O- m; ]( o! y1 v- x9 ?1 k

- F% ^: Z  h9 \! M' {( I8 c) q7 }一、动态规划初探, h; m* t5 y) x$ r5 F* v
      1、递推
4 P) Q# a* k9 o/ f: O      2、记忆化搜索
$ Z" x$ C5 n1 V4 T0 ~* O, A6 I      3、状态和状态转移
* l+ t: |: O4 ]% P; F0 N; z      4、最优化原理和最优子结构
/ m3 Q1 d' _' J: l      5、决策和无后效性9 M% _' g8 i0 A# s7 o
8 k* J6 ]- o2 K% P! w  y) _/ ]7 y

2 [% i) C( C/ k二、动态规划的经典模型
! I1 G, p4 [: |& ]. A( ~6 L       1、线性模型
2 E, O, C3 l  e3 ?$ o       2、区间模型
6 }7 _" @8 [0 n3 f; Q       3、背包模型
  t2 Z- w5 C9 h4 @) P( j       4、状态压缩模型* M5 c* r9 D* N+ \- _
       5、树状模型  r  S+ Y  \+ }/ Q  [" o

+ G/ z. r- H' p0 o) N
. z" [- \4 H4 F/ l7 h' d" d三、动态规划的常用状态转移方程, P8 m; \+ L+ d: \# H, [* L1 f

7 Y4 a* c1 i/ |: w, U" m      1、1D/1D/ f% h3 r2 [* N4 ^8 \: ]
       2、2D/0D
2 R+ ^4 k0 i- H- w- w0 ^7 s       3、2D/1D* [6 V% X1 _2 J8 y1 C! C" @
       4、2D/2D
2 v. D( V4 p) @& v8 Q1 S
$ b" w# x# k# Z* v0 }  X) X四、动态规划和数据结构结合的常用优化! `5 K& Z/ J: W) _9 s! E
1、滚动数组
* a$ p, Q" O, v8 A       2、最长单调子序列的二分优化
( M) Y' F/ N  m0 ~       3、矩阵优化
: a1 x0 e' A! h2 j4 y" W: i& _       4、斜率优化
! H+ j/ w6 A0 Q3 W4 ^9 S0 b       5、树状数组优化
8 G: _3 b; {. I       6、线段树优化( i# Y' G$ U& G; k; s, \) w
       7、其他优化
3 p' c; I. l$ d! p5 V+ B/ b/ V" ^2 D- }  K1 y# w  G) y+ `
五、动态规划题集整理  X7 a3 j0 _4 d9 U

7 Y2 ~8 r( |7 I6 R# n. P9 ]3 e
& g0 P6 w# f4 ^; E2 N: ?1 l
# s8 o9 G+ j7 h% y/ U$ C% i2 u: [* j
0 i" m0 ~( I8 F! _
' }  V( O9 r) B2 s0 ]  W

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

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



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