100个经典的动态规划方程
( Z& J, Q! a$ R9 F详细资源请下载附件
1 T+ y I' ]. F0 r3 s. \
5 {7 s8 d% c# ?8 `$ _5 j/ R3 v0 Z1.资源问题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]); 4 O/ B5 u4 k# j2 }9 Z) U* t3 ^
3.线性动态规划1-----朴素最长非降子序列 F = max{f[j]+1} d, |& |( R% f. q4 B C
4.剖分问题1-----石子合并 F[i,j] = min(f[i,k]+f[k+1,j]+sum[i,j]); ^# m0 F4 e3 H' k% Y" d1 P, B0 A
5.剖分问题2-----多边形剖分 F[I,j] = min(f[i,k]+f[k,j]+a[k]*a[j]*a);
1 L; N0 ]7 g+ h. v0 U7 ?: v' t3 t6.剖分问题3------乘积最大 f[i,j] = max(f[k,j-1]*mult[k,i]);
% D1 J+ y n9 [" R, Z1 ]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} ' N: o9 x% i4 o2 s0 F
9. 贪心的动态规划2----过河 f=min{{f(i-k)} (not stone) {f(i-k)}+1} (stone); +贪心压缩状态
1 q. L* J& \3 ^8 L9 A& E $ u$ p8 Q' l$ i+ U( n
2 x! _8 E+ I( n! a, V. {- l! P7 }' T& M! G
, T! S) q+ q) j$ ]* T: h8 B: l+ H0 Z
$ `: B0 h7 I, S; n
8 d: A& K; a! P8 j
|