Matrix multiplication

Given a set of matrices and find the most efficient way to multiply matrix. Write an efficient way to multiply matrix using Dynamic programming.

source Code

package com.dsacode.Algorithm.dynamic;
 
import java.util.Arrays;
 
public class MatrixMultiplication {
     public static final long INFINITY = Long.MAX_VALUE;
 
     public static void optMatrix( int [ ] c, long [ ][ ] m, int [ ][ ] lastChange )
        {
            int n = c.length - 1;
 
            for( int left = 1; left <= n; left++ )
                m[ left ][ left ] = 0;
            for( int k = 1; k < n; k++ )  
                for( int left = 1; left <= n - k; left++ ) {
                    int right = left + k;
                    m[ left ][ right ] = INFINITY;
                    for( int i = left; i < right; i++ )
                    {
                        long thisCost = m[ left ][  i ] + m[ i + 1 ][ right ]
                             + c[ left - 1 ] * c[ i ] * c[ right ];
                        if( thisCost < m[ left ][ right ] ) {
                            m[ left ][ right ] = thisCost;
                            lastChange[ left ][ right ] = i;
                        }
                    }
                }
        }
 
        public static void main( String [ ] args ) {
            int [ ] c = { 2, 1, 4, 3, 5 };
            long [ ][ ] m = new long [ 5 ][ 5 ];
            int lastChange[ ][ ] = new int [ 5 ][ 5 ];
            System.out.println("Array c values: "+ Arrays.toString(c));
            optMatrix( c, m, lastChange );
            System.out.println("Matrix m values: "+ Arrays.deepToString(m));
            System.out.println("Matrix last change values: "+ Arrays.deepToString(lastChange));
        }
} 

Output

Array c values: [2, 1, 4, 3, 5]
Matrix m values: [[0, 0, 0, 0, 0], [0, 0, 8, 18, 37], [0, 0, 0, 12, 27], [0, 0, 0, 0, 60], [0, 0, 0, 0, 0]]
Matrix last change values: [[0, 0, 0, 0, 0], [0, 0, 1, 1, 1], [0, 0, 0, 2, 3], [0, 0, 0, 0, 3], [0, 0, 0, 0, 0]]

Algorithm Explanation

	Take the sequence of matrices and separate into two subsequences.
	Find the minimum cost of multiplying out each subsequence.
	Add these costs together, and add in the cost of multiplying the two result matrices.
	Do this for each possible position at which the sequence of matrices can be split, and take the minimum over all of them.
	Return the matrix multiplication and display the values.

Time Complexity

Reference

1. https://en.wikipedia.org/wiki/Matrix_chain_multiplication
2. https://www.cse.ust.hk/~dekai/271/notes/L12/L12.pdf
3. http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/chainMatrixMult.htm