矩阵连乘 备忘录

public class MatrixNote {

	int matrixNote(int[] p, int i, int j, int[][] s,int[][] m) {
		int k, minValue, tempValue;
		
		if(m[i][j]>0)
			return m[i][j];
		
		if(i == j) {
			minValue=0;
		} else {
			minValue = matrixNote(p, i+1, j, s, m) + p[i-1]*p[i]*p[j];  //A1 | A2 A3 A4 A5 A6初始为最优解； 
			s[i][j]=i;           //记录最优解的轨迹； 
		
			for(k=i+1;k<j;k++){
		 		tempValue = matrixNote(p,i,k,s,m) + matrixNote(p,k+1,j,s,m) + p[i-1]*p[k]*p[j];   // A1 A2 | A3 A4 A5 A6 开始检查； 
		 		if(tempValue < minValue){
		 			minValue = tempValue;     //更新数据； 
		 			s[i][j]=k;
		 			m[i][j]=minValue;
			 	}
			 
			 }
		 }
		 return minValue;
	} 
	void trace(int i,int j,int[][]s){
		if(i==j)
		return;
		trace(i,s[i][j],s);     //以k为分割的位置打印两边的轨迹； 
		trace(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) {
	
		MatrixNote mn = new MatrixNote();

		int[] p = {30, 35, 15, 5, 10, 20, 25}; 
		int[][]s = new int[7][];                 //声明二维数组，记录最优解的位置下标； 
		int[][]m = new int[7][];     
		for(int i = 0; i < 7; i++) {
			s[i]=new int[7];
			m[i]=new int[7];
		}
		for(int i = 1; i < 7; i++)  
			for(int j = 1; j < 7; j++)  
	    			m[i][j]=0;  		
		System.out.println(mn.matrixNote(p, 1, 6, s, m));
		mn.trace(1,6,s);
	}
}