100个经典的动态规划方程
! N: z8 p5 \- J; D# V- e" {5 c$ `详细资源请下载附件
# m9 ?6 u) F6 F) [3 Q
8 _( Z. K( b) w P: u1.资源问题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]);
) b1 ?" J* [ u. `* b* e" T( z3.线性动态规划1-----朴素最长非降子序列 F = max{f[j]+1} ( D( F. z! F# v2 e
4.剖分问题1-----石子合并 F[i,j] = min(f[i,k]+f[k+1,j]+sum[i,j]);
2 i# l. u2 H( ?1 \5.剖分问题2-----多边形剖分 F[I,j] = min(f[i,k]+f[k,j]+a[k]*a[j]*a);
' Z4 {* e" [4 f7 p2 [! F6.剖分问题3------乘积最大 f[i,j] = max(f[k,j-1]*mult[k,i]); % l O( Y0 E) A( V" U
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} ; u, ], H5 ?. B9 b( N
9. 贪心的动态规划2----过河 f=min{{f(i-k)} (not stone) {f(i-k)}+1} (stone); +贪心压缩状态
6 u0 m: N P& d; p
9 t+ _ s: E4 y5 T \3 J( y1 p# t6 Y" y! }/ w4 q0 K
& l2 Q* r6 s @0 ^' }1 h0 p6 n( F5 A) l. A4 u3 K7 K7 z
6 J& W" `9 U2 @3 j0 ~, j' w
# x# B. G! [0 L6 P! ]- h& I* z7 O N9 [/ m
|