fac3_1.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 65 页，例
//矩阵连乘问题动态规划解法
public class Fac3_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 main(String args[])
  {
    int []a={30,35,15,5,10,20,25};
    int n=a.length;
    int [][]b;int [][]c;
    b=new int[n][n];
    c=new int[n][n];
    matrixChain(a,b,c);
    traceback(c,1,n-1);
  }
}