100个经典的动态规划方程' S( y' d& F/ k3 }2 M% l4 P1 G
详细资源请下载附件 6 f, W q( b0 `# R
. d U4 J/ Z& D6 u9 H0 x
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]);
7 ?% b6 H# X! G2 V" P3.线性动态规划1-----朴素最长非降子序列 F = max{f[j]+1} # F$ N3 t% x% \3 ?6 O
4.剖分问题1-----石子合并 F[i,j] = min(f[i,k]+f[k+1,j]+sum[i,j]); $ Y% y2 n0 z! q# g% f) m6 Q$ `
5.剖分问题2-----多边形剖分 F[I,j] = min(f[i,k]+f[k,j]+a[k]*a[j]*a); J- Q5 U( r, v8 X& Y7 T7 @
6.剖分问题3------乘积最大 f[i,j] = max(f[k,j-1]*mult[k,i]); 3 c, w" l" u) a, A
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}
" |9 D6 J' J. S+ |1 s9. 贪心的动态规划2----过河 f=min{{f(i-k)} (not stone) {f(i-k)}+1} (stone); +贪心压缩状态 . a) E, a+ d8 ~5 j" K* h8 s
; w7 f9 a3 x ~8 y. o$ f
0 Z* e( ?/ C$ J6 \* N" z
4 Y, a: y6 q' e L" M. {
7 A" V! h9 l* D4 ~$ h
' N0 P5 H. y6 J; I1 f4 F: {7 P" c! g3 j
: _1 S2 {$ d Y# D& N
|