数学建模社区-数学中国

标题: 非常好的动态规划总结，DP总结 [打印本页]
作者: 杨利霞    时间: 2019-3-27 15:10
标题: 非常好的动态规划总结，DP总结
  ^  C" o0 j2 M5 Q
非常好的动态规划总结，DP总结. Y0 Y. ?9 D4 }4 P
0 ~% d  Y% V' M( i$ `: {; U
详细资料请下载附件
$ C* K7 v7 I0 ~7 [
( P) _6 l# x5 {: H1 f( y目录  2 h. V- M1 i9 v* S% r
' `9 u' N$ k1 |- m
4 w5 K$ Q- r  Q0 H0 B9 A  N
一、动态规划初探% U& ~5 e* K( F; H7 c# z
      1、递推
3 Z. `2 [$ P, k5 q# `) p      2、记忆化搜索/ R# w4 M2 x; i8 J+ S( m
      3、状态和状态转移  C2 v1 |) H  H/ |3 z# v6 f
      4、最优化原理和最优子结构
2 G2 c1 U" s+ H4 q" i3 y" j" O      5、决策和无后效性
% _! r8 S$ A( K; O; r) b2 U9 n# @7 X/ ~
( {8 v# M- O# R8 r
二、动态规划的经典模型* o1 r3 E' S# I
       1、线性模型$ [: E* Z; I* q! g6 \0 g
       2、区间模型+ x4 A0 E0 \1 ~
       3、背包模型
/ @9 |. {# O; s9 {( B       4、状态压缩模型
2 j5 E1 ]7 q1 \) f% S, M3 R       5、树状模型: J2 x( L4 g: H/ N) G6 H: j% b

5 a% \" J5 g' @4 f( m0 Y! C+ b' ?5 }; R; ?" h3 `3 o  x# G, c
三、动态规划的常用状态转移方程8 v8 j, c; f6 T. U0 J; b

' C4 r. p% E% r. P  f6 B3 u, H      1、1D/1D
3 c; ^5 N8 d1 R% x       2、2D/0D
7 E, d8 F+ p$ U6 j       3、2D/1D4 c, `$ P8 B1 [. I( K: R; u: L
       4、2D/2D# a3 |+ g6 D, ]0 u8 E( O
" O. @; `1 X$ z% o+ w2 B! v, c, }# [
四、动态规划和数据结构结合的常用优化
  X1 z9 |' k6 h2 S" g- T1、滚动数组
! L6 a4 m( I& H       2、最长单调子序列的二分优化
/ f! s& ~6 n3 a1 ~8 s       3、矩阵优化
7 j& D# e( z5 [# D1 J, h5 D6 W* ]       4、斜率优化
6 x6 x* H$ e3 E. U  x+ I4 Z$ a       5、树状数组优化, e/ I+ W- i  h: p" K/ E5 w" E) S
       6、线段树优化
# C- R! W2 r- Q: D- e1 t, Y       7、其他优化
# N( f& A5 [7 w8 N
* d+ {, C) o5 z  O8 F5 M五、动态规划题集整理
" t8 G$ t% `; v( k9 _' @; b6 t$ P! Z) d. g' V0 G0 r9 P- Y
3 f; B" ]3 C0 W0 Y! l5 u- d$ D

9 ]# W6 C( ?4 @# j* O4 O& J
4 p6 I' l- U0 i
( f# K/ t' R! v- `5 M* k

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

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



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