//矩阵相乘，非递归
 
//矩阵相乘
package wkx;
 
import java.io.IOException;
 
public class Test {
	
	private static void MatrixChain(int[] p,int[][] m,int [][] s,int len){
		for(int i=1;i<len;i++)
			m[i][i]=0;
		for(int r=2;r<len;r++){
			for(int i=1;i<=len-r;i++){
				int j=i+r-1;
				int min=Integer.MAX_VALUE;
				for(int k=i;k<j;k++){
					int d=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
					if(d<min){
						min=d;
						s[i][j]=k;
					}
				}
				m[i][j]=min;
			}
		}
	}
	
	private static void TraceBack(int i,int j,int[][] s){
		if(i==j)
			return;
		TraceBack(i,s[i][j],s);
		TraceBack(s[i][j]+1,j,s);
		System.out.println("A["+i+"]["+s[i][j]+"] * "+"A["+(s[i][j]+1)+"]["+j+"]");
	}
	
	public static void main(String[] args) throws IOException {
		int[][] m=new int[100][100];
		int[][] s=new int[100][100];
		int[] p=new int[]{30,35,15,5,10,20,25};
		int len=p.length;
		MatrixChain(p,m,s,len);
		TraceBack(1,len-1,s);
	}
}
 
 
//矩阵相乘 递归解法
 
//矩阵相乘
package wkx;
 
import java.io.IOException;
 
public class Test {
	
	private static int MatrixChain(int[] p,int[][] m,int [][] s,int i,int j){
		if(i==j){
			m[i][j]=0;
			return 0;
		}
		if(m[i][j]!=0)
			return m[i][j];
		int min=Integer.MAX_VALUE;
		for(int k=i;k<j;k++){
			int d=MatrixChain(p,m,s,i,k)+MatrixChain(p,m,s,k+1,j)+p[i-1]*p[k]*p[j];
			if(d<min){
				m[i][j]=min=d;
				s[i][j]=k;
			}
		}
		return min;
	}
	
	private static void TraceBack(int i,int j,int[][] s){
		if(i==j)
			return;
		TraceBack(i,s[i][j],s);
		TraceBack(s[i][j]+1,j,s);
		System.out.println("A["+i+"]["+s[i][j]+"] * "+"A["+(s[i][j]+1)+"]["+j+"]");
	}
	
	public static void main(String[] args) throws IOException {
		int[][] m=new int[100][100];
		int[][] s=new int[100][100];
		int[] p=new int[]{30,35,15,5,10,20,25};
		int len=p.length;
		System.out.println("Total : "+MatrixChain(p,m,s,1,len-1));
		TraceBack(1,len-1,s);
	}
}