100个经典的动态规划方程

杨利霞

100个经典的动态规划方程

详细资源请下载附件

8 [4 l$ X4 o2 n4 \: e4 A9 {& b! n
# ^' N& h- t7 ?0 `* Z

1.资源问题1-----机器分配问题

F[I,j] = max(f[i-1,k]+w[i,j-k])

2.资源问题2------01背包问题

F[i,j] = max(f[i-1,j-v]+w,f[i-1,j]);

3.线性动态规划1-----朴素最长非降子序列

F = max{f[j]+1}

4.剖分问题1-----石子合并

F[i,j] = min(f[i,k]+f[k+1,j]+sum[i,j]);

5.剖分问题2-----多边形剖分

F[I,j] = min(f[i,k]+f[k,j]+a[k]*a[j]*a);

: C! W4 r) P* {+ r. ~; z

6.剖分问题3------乘积最大

f[i,j] = max(f[k,j-1]*mult[k,i]);

* D; N( m. B& n) ~' P

7.资源问题3-----系统可靠性(完全背包)

F[i,j] = max{f[i-1,j-c*k]*P[I,x]}

8.贪心的动态规划1-----快餐问题

F[i,j,k] = max{f[i-1,j',k']+(T-(j-j')*p1-(k-k')*p2)div p3}

5 H* `4 ~6 ~  y) R8 S. D; F

9. 贪心的动态规划2----过河

f=min{{f(i-k)} (not stone)

{f(i-k)}+1} (stone); +贪心压缩状态

1 x* v* S8 ?* d/ O" M. t) c

4 c1 U0 f0 U8 M; w7 L
  V* f2 S: n' @7 P9 f+ p5 T

' n0 a8 ]0 u! O6 \# l' B. r
$ }: X( M; J! N) R: N# j$ B& p
  Q! g" e8 J- j  Z9 _
. P* l# I) c: _