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));
}
}