Chain Matrix Multiplication

Given a sequence of n matrices A₁, A₂, ... A_n, and their dimensions p₀, p₁, p₂, ..., p_n, where where i = 1, 2, ..., n, matrix A_i has dimension p_{i − 1} × p_i, determine the order of multiplication that minimizes the the number of scalar multiplications.

For 1 ≤ i ≤ j ≤ n, let m[i, j] be the minimum number of scalar multiplications needed to compute the A_i..j. The optimum cost can be described by the following recursive formulation.

Basis: Observe that if i = j then the problem is trivial; the sequence contains only one matrix, and so the cost is 0. (In other words, there is nothing to multiply.) Thus,

m[i, i] = 0 for i = 1, 2, ..., n.

Step: If i ≠ j, then we are asking about the product of the subchain A_i..j and we take advantage of the structure of an optimal solution. We assume that the optimal parenthesization splits the product, A_i..j into for each value of k, 1 ≤  k ≤  n − 1 as A_i..k . A_k+1..j.

The optimum time to compute is m[i, k], and the optimum time to compute is m[k + 1, j]. We may assume that these values have been computed previously and stored in our array. Since A_i..k is a matrix, and A_k+1..j is a matrix, the time to multiply them is p_i − 1 . p_k . p_j. This suggests the following recursive rule for computing m[i, j].

To keep track of optimal subsolutions, we store the value of k in a table s[i, j]. Recall, k is the place at which we split the product A_i..j to get an optimal parenthesization. 

From: http://mytestpjt.googlecode.com/svn/trunk/ASAssembly/src/com/mhhe/clrs2e/MatrixChainMultiply.java

    private void matrixChainOrder(int[] p)
    {
 // Initial the cost for the empty subproblems.
 for (int i = 1; i <= n; i++)
     m[i][i] = 0;

 // Solve for chains of increasing length l.
 for (int l = 2; l <= n; l++) {
     for (int i = 1; i <= n-l+1; i++) {
  int j = i + l - 1;
  m[i][j] = Integer.MAX_VALUE;

  // Check each possible split to see if it's better
  // than all seen so far.
  for (int k = i; k < j; k++) {
      int q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
      if (q < m[i][j]) {
   // q is the best split for this subproblem so far.
   m[i][j] = q;
   s[i][j] = k;
      }
  }
     }
 }
    }

Also refer to http://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/
Read full article from Chain Matrix Multiplication