以两个矩阵为例,第一个矩阵A1为p*q,第二个矩阵A2为q*r,只有当第一个矩阵的列等于第二个矩阵的行时,两个矩阵才能相乘,这时我们称这两个矩阵是相容的,
对于两个矩阵相乘,一旦矩阵的大小确定下来之后,那么所需执行的乘法次数就确定下来了,
对于两个矩阵相乘，一旦矩阵的大小确定下来了，那么所需执行的乘法次数就确定下来了。那么对于两个以上的矩阵呢？是不是也是这样呢。实际上，对于多个矩阵相乘，乘法执行的次数与“划分”有关。例如：
以矩阵链<A1,A2,A3>为例，假设三个矩阵的规模分别为10X100，100X5和5X50。
①以((A1*A2)*A3)方式划分，乘法执行次数为：10*100*5+10*5*50=5000+2500=7500次
②以(A1*(A2*A3))方式划分，乘法执行次数为：100*5*50+10*100*50=25000+50000=75000次
我们可以发现，对于同样的矩阵链<A1,A2,A3>相乘而言，不同的划分，乘法次数居然相差10倍。
矩阵链乘法问题:给定n个矩阵链<A1,A2,A3.......An>,矩阵Ai的规模为p(i1)*p(i) (1<=i<=n),求完全括号化方案,使得计算乘积A1*A2*A3......*An所需标量的乘法次数最少
我们假设n=6,一共有6个矩阵,
矩阵 A1 A2 A3 A4 A5 A6 规模 30*35 35*15 15*5 5*10 10*20 20*25
那么就一共有7个数字:{30,35,15,5,10,20,25};
另m[i][j]来表示矩阵A1....n所需的最低代价.
另s[i][j]来表示矩阵括号的位置
需要注意的一点是当i=j时，m[i][j]=m[i][i]=0，因为一个矩阵不需要任何乘法。
假设矩阵链从Ai到Aj，有j-i+1个矩阵，我们从k处分开，将矩阵链分为Ai~Ak和Ak+1到Aj两块，那么我们可以比较容易的给出m[i][j]从k处分隔的公式：
m[i][j]=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]；
在一组确定的i和j值的情况下，要使m[i][j]的值最小，我们只要在所有的k取值中，i<=k<j，寻找一个让m[i][j]最小的值即可。
假设L为矩阵链的长度，那么L=j-i+1。当L=1时，只有一个矩阵，不需要计算。那么我们可以从L=2到n进行循环，对每个合理的i和j值的组合，遍历所有k值对应的m[i][j]值，将最小的一个记录下来，存储到m[i][j]中，并将对应的k存储到s[i][j]中，就得到了我们想要的结果。
package practice; import java.util.Scanner; public class juzhenlianchengfa { private static int n; private static int[][] m=new int[100][100]; private static int[][] s=new int[100][100]; private static int[] p=new int[105]; private static final int max=Integer.MAX_VALUE; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); for(int i=0;i<=n;i++) { p[i]=sc.nextInt(); m[i][i]=0; } for(int l=2;l<=n;l++) { for(int i=1;i<=n-l+1;i++) { int j=i+l-1; m[i][j]=max; for(int k=i;k<=j-1;k++) { int q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(q<m[i][j]) { m[i][j]=q; s[i][j]=k; } } } } System.out.print(m[1][n]); print(1,n); } public static void print(int i,int j) { if(i==j) System.out.print("A"+i); else { System.out.print("("); print(i,s[i][j]); print(s[i][j]+1,j); System.out.print(")"); } } } 输入:6
30,35,15,5,10,20,25
输出为:
((A1(A2A3))((A4A5)A6) 15125
