1、f[I,j]表示第i个矩阵到第j个矩阵连乘的最少次数。
2、a.x a.y表示第i个矩阵的行号和列号
3、转移方程:
F[I,j]=min{F[I,k]+f[k+1,j]+ai.x*ai.y*aj.y}
首先是两两相乘
For i:=1 to n-1 do
F[i,i+1]:=a.x*a.y*a[i+1].y;
然后是更大规模的连乘
For len:=3 to n do
For i:=1 to n-len+1 do
Begin
j:=i+len-1;F[i,j]:=maxlongint;
For k:=i to j-1 do
If F[i,j]>F[i,k]+F[k+1,j]+a.x*a[k].y*a[j].y Then
Begin
F[i,j]:=F[i,k]+F[k+1,j]+a.x*a[k].y*a[j].y;
End;
End ;