100个经典的动态规划方程

杨利霞

100个经典的动态规划方程
$ `5 b, e3 S9 B+ V- B/ L( J/ d

详细资源请下载附件

  M8 W2 G" J' Y/ A2 l+ t

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]);

. J5 ~6 H; S4 ~* ?5 w

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

F = max{f[j]+1}

& m+ {/ }. D7 Q3 }+ Q- a

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

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

" i# D+ w! B- g

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

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

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

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

! v' N, j8 w8 n& u: r* W# Q# Q2 F) m

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 n# K- _" g6 b% `; ~! N3 @

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

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

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

' }( A1 s' c* N% m5 x
8 H/ o1 V2 p0 h+ E6 a
: ]2 |5 ?. Y+ f# s, c& j7 a# j  v  c
( w2 _5 B. C6 H! |
  ?- ~/ |1 ]( n
+ Y; I3 V! l  D