数学建模社区-数学中国

标题: 非常好的动态规划总结，DP总结 [打印本页]
作者: 杨利霞    时间: 2019-3-27 15:10
标题: 非常好的动态规划总结，DP总结

9 K' s, I# k1 V9 A$ o- f8 V非常好的动态规划总结，DP总结$ \. q% Z+ o  b& Y0 ]+ n
% |. J7 Z* F6 T5 y! [0 W0 G
详细资料请下载附件
2 }; V9 q2 t, e. @. W. `* h8 |  a" L+ a& ?/ z% q: x( [! u, c' u4 W
目录  " e* A9 `; V& F" ]8 \2 r
  d3 H9 X3 ^3 {9 e( M6 A

0 L% b# i' x9 G! Z- Y6 x一、动态规划初探3 o8 m4 B" W) @, D$ N: l4 d$ t; u
      1、递推
1 w! X% G, f5 M7 ?2 G: y      2、记忆化搜索% o, j- j5 [* G, i$ f
      3、状态和状态转移
1 N6 p6 `0 P! J8 l      4、最优化原理和最优子结构5 T, C! V& o; i# v
      5、决策和无后效性5 _# T8 ?+ ]4 _4 ~+ H& {, T8 e, r6 F
8 h) K1 E6 s8 z  ?" A( @

' [2 b. T5 Z! T二、动态规划的经典模型
1 |1 F/ _7 E5 P. F( {- Q/ |1 G       1、线性模型
' f( W) A  U. H       2、区间模型
' q: l2 D: r/ X* j       3、背包模型
+ a; X& {4 l6 ^5 d& U8 j       4、状态压缩模型
) v2 R+ t. `- h- ^       5、树状模型
1 Y/ U! \0 ~2 o5 c/ g3 P) U+ U  {/ I+ g- h" o. O

: ?- j( m; k2 ^; M  y8 x/ ]三、动态规划的常用状态转移方程+ }7 ~2 d) x, \" V, D% K
" _' s) P% o1 W
      1、1D/1D
6 I+ s+ D; q% L7 O# D% |% L' O+ J       2、2D/0D5 I' ~' @0 c7 Y, r  A) _6 t4 [' a! }; Z  c
       3、2D/1D( `8 Y$ @- f( g
       4、2D/2D
; k$ S8 n6 V% x0 I% a$ N2 U
' z8 C% P( L* K7 j4 x/ p- v/ V5 ^) n四、动态规划和数据结构结合的常用优化
) q1 Z1 v. E0 d; Y" ^# Y: k1、滚动数组5 F8 d  s1 h0 N* O* B9 n; i! Y, k
       2、最长单调子序列的二分优化. ^( f% S8 ?' W# R) G0 l
       3、矩阵优化! L, `$ V* ^: o( u8 a, G
       4、斜率优化: @2 W) ]0 J  ?+ `0 [7 x9 n
       5、树状数组优化! R1 M3 u# k; q
       6、线段树优化
* K  i" Z; J5 N, q. ~7 b       7、其他优化
, {9 {9 g# Y+ g9 o8 c7 v; B: ^" L1 d9 u9 O9 o  z
五、动态规划题集整理
5 e/ a" d# v6 ?  R+ f9 U4 Y; C' O( ^& G: l) ~1 s

/ H% D; X* B6 u+ K- {% e4 s0 L8 H
! Y( F1 l& z6 j$ O3 v
8 g* c% K" K) z, i' N; ~2 S5 v! t$ Y6 u/ [# S

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

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



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