//本程序取自王曉東編著“算法分析與設計”第 68 頁，例
//矩陣連乘問題遞歸直接計算法
public class Fac3_1_1{
    static int p[];
    static int s[][];
    public Fac3_1_1(int a[],int c[][])
  {
    p=a;
    s=c;
  }
   public static int recurMatrixChain(int i,int j)
   {
     if(i==j)return 0;
     int u=recurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];
         s[i][j]=i;
         for(int k=i+1;k<j;k++){
           int t=recurMatrixChain(i,k)+recurMatrixChain(k+1,j)+p[i-1]*p[k]*p[j];
           if(t<u){
            u=t;
            s[i][j]=k;}
         }
     return u;
   }
  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 main(String args[])
  {
     int []a={30,35,15,5,10,20,25};
     int n=a.length;
     int [][]c=new int[n][n];
     Fac3_1_1 abc=new Fac3_1_1(a,c);
     recurMatrixChain(1,n-1);
     traceback(c,1,n-1);
  }
}