[数据结构与算法]Java 实现矩阵连乘，构造最优解

Java 实现矩阵连乘，构造最优解

package test;
public class algorithm {
    public static void main(String[] args) {
    	int[] p={30,35,15,5,10,20,25};
    	int n=p.length;
    	int[][] m=new int[n][n];
    	int[][] s=new int[n][n];
    	matrixChain(p,m,s);
    	 System.out.println("");
     traceback(s,1,n-1);
     System.out.println("");
     op(s,1,n-1);
    }
    public static void matrixChain(int []p,int [][]m,int [][]s){
    	int n=p.length-1;
    	for(int i=1;i<=n;i++) m[i][i]=0;
    	for(int r=2;r<=n;r++)
    		for(int i=1;i<=n-r+1;i++){
    			int j=i+r-1;
    			m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
    			s[i][j]=i;
    			for(int k=i+1;k<j;k++){
    				int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
    				if(t<m[i][j]){
    					m[i][j]=t;
    					s[i][j]=k;
    				}
    			}
    		}
    }
    public static void traceback(int [][]s,int i,int j){ //构造最优解额
    	if(i==j) return;
    	traceback(s,i,s[i][j]);
    	traceback(s,s[i][j]+1,j);
    	System.out.println("Multiply A"+i+","+s[i][j]+"and A"+(s[i][j]+1)+","+j);
    }
    public static void op(int[][] s,int i,int j){
    	if(i==j){
    		System.out.print("A"+i);
    	}else {
    		System.out.print("(");
    		op(s,i,s[i][j]);
    		op(s,s[i][j]+1,j);
    		System.out.print(")");
    	}
    }
    }