fac3_1_2.java

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

//本程序取自王晓东编著“算法分析与设计”第 70 页，例
//矩阵连乘问题备忘录解法
public class Fac3_1_2{
    static int p[];
    static int s[][];
    static int m[][];
    public Fac3_1_2(int a[],int b[][],int c[][])
  {
    p=a;
    m=b;
    s=c;
  }
   public static int memoizedMatrixChain(int n)
   {
         for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
            m[i][j]=0;   
         return lookupChain(1,n);
   } 
   private static int lookupChain(int i, int j)
   {
      if (m[i][j] > 0) return m[i][j];
      if (i == j) return 0;
      int u = lookupChain(i+1,j) + p[i-1]*p[i]*p[j];
      s[i][j] = i;
      for (int k = i+1; k < j; k++) {
        int t = lookupChain(i,k) + lookupChain(k+1,j) + p[i-1]*p[k]*p[j];
        if (t < u) {
          u = t; s[i][j] = k;}
        }
      m[i][j] = u;
      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 [][]b=new int[n][n];
     int [][]c=new int[n][n];
     Fac3_1_2 abc=new Fac3_1_2(a,b,c);
     memoizedMatrixChain(n-1);
     traceback(c,1,n-1);
  }
}