package dynamic_programming;

 public class matrix_chain_order { //input is a sequence p = p0,p1..pn,where p.length = n+1  (matrix n is pn-1pn)

     int[] p;

     int[][] cost;

      public matrix_chain_order(int[] a){

          p = a;

      }

      public int order(){

         int q = 0;

         int n = p.length -1;

         cost = new int[n][n];

         for(int i = 0;i<= n-1;i++){

             cost[i][i] = 0;

         }

         for(int l = 2;l<n;l++){  //the chain length,like merge sort

             for(int i=0;i<n-l;i++){

                 int j = i+l -1;

                 cost[i][j] =Integer.MAX_VALUE;

                 for(int k = i;k <=j -1;k++){

                     q = cost[i][k] + cost[k+1][j] + p[i-1]*p[k]*p[j];

                     if(q < cost[i][j]){

                         cost[i][j] = q; //remeber the best step of i to j

                     }

                 }

             }

         }

         return cost[n-1][n-1];

      }

 }