100个经典的动态规划方程( E0 t; o8 u( B+ @' o( ]
详细资源请下载附件
3 i) B* w; V- ^* c9 C, D1 d I7 V3 @/ K$ K- ^' Q
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]);
( A+ x0 u( _& ~+ N3 R# w: m9 A. ~3.线性动态规划1-----朴素最长非降子序列
F = max{f[j]+1}
* G+ F# ^# S( n: J
4.剖分问题1-----石子合并
F[i,j] = min(f[i,k]+f[k+1,j]+sum[i,j]);
! s0 w* h/ C3 R/ F$ `- q
5.剖分问题2-----多边形剖分
F[I,j] = min(f[i,k]+f[k,j]+a[k]*a[j]*a);
) Q3 ^3 `. \7 g: m0 e5 U6.剖分问题3------乘积最大
f[i,j] = max(f[k,j-1]*mult[k,i]);
( j- M+ {9 n. j+ f: ]/ E7.资源问题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}
8 L/ ~% C% ~7 L6 }2 K4 z {* v9. 贪心的动态规划2----过河
f=min{{f(i-k)} (not stone)
{f(i-k)}+1} (stone); +贪心压缩状态
& N+ W9 m, \8 U: z0 ` X1 D
