package matrixchain;

/*
 * Optimal Matrix Chain Multiplication
 * Burton Rosenberg
 * 5 June 2002
 *
 * from Intro. to Alg., CLR
 *
 * note: arrays are 1 ... n, to agree w/ notation of CLR.
 *
 */

public class MatrixChain {


  // m[i][j] is A_i A_{i+1} ... A_{j} counting from A_1 ...

  public static void main(String[] args) {
      //int [] p = { 10, 100, 5, 50 } ; // A_1 is 10x100, A_2 is 100x5, etc.
      int [] p = { 30, 35, 15, 5, 10, 20, 25 } ;
      int n = p.length - 1 ; // number of matrices
      int [][] m = new int[n+1][n+1] ;
      matrixChain(m,p) ;
      System.out.println("\nOptimal number of multi: "+ m[1][n] ) ;

  }

  static
  int minimum( int i, int j, int [][] m, int [] p ) {
     int mind = -1 ;
     for ( int k=i; k<=(j-1); k++ ) {
        // #A_i^k, #A_{k+1}^j, p[i-1]*p[k]*p[j]
        int d = m[i][k] + m[k+1][j] +  p[i-1]*p[k]*p[j] ;
        if ( mind==-1 || d < mind ) mind = d ;
     }
     return mind ;
  }

  static
  void matrixChain(int [][] m, int [] p) {

     int n = p.length - 1 ;

     for ( int l=1; l<=n; l++ ) m[l][l] = 0 ;

     for ( int d=1; d<=n-1; d++ ) {
        for ( int i=1; i<=n-d; i++ ) {
          int j = i + d ;
          m[i][j] = minimum(i,j, m, p) ;
printArray(m) ;
        }
     }
  }

  static
  void printArray( int [][] a ) {
     System.out.println() ;
     for ( int i=1; i<a.length; i++ ) {
        for ( int j=1; j<a[i].length; j++ ) {
           System.out.print( a[i][j] + ", " ) ;
        }
        System.out.println() ;
     }
  }

}