CareerCup

This question relates to dynamic programming where in we reduce the number of multiplications by constructing a table(remember lowest common subsequence)
if matrices are of sizes compatible for multiplication
m(i,j)=0 if i==k(diagnol elements)
(Not sure butcheck dynamic programming)
m(i,j)=min(summation(i<=k<j)m(i,k)+m(k+1,j)+pi-1pkpj-1)

i don't quite get you...for product of n matrices you got to have n-1 multiplications, no matter how you group the matrices (is there a shortcut formula to multiply three or more matrices simultaneously?).

Wikipedia article:
en.wikipedia.org/wiki/Matrix_chain_multiplication

It's about dynamic programming.
My idea is to split the Matrices into two sub Matrix[]. Then recursively calculating the result for each sub-Matrix, since there may be more than one way to split, we need to compare each kind of split and update the result that was supposed to be handed in to the upper level.
Here is my intact code, I tested with ABCD: A[10X30] B[30X5] C[5X60] D[60X4]

public class exercise {
	static Matrix[] m = new Matrix[4];
	public static void main( String[] args ){
		m[0] = new Matrix( 10, 30 );
		m[1] = new Matrix( 30, 5 );
		m[2] = new Matrix( 5, 60 );
		m[3] = new Matrix( 60, 4 );
		exercise e = new exercise();
		Result r = e.findMin(m);
		System.out.println(r.s + " " + r.ct);
	}
	
	public Result findMin( Matrix[] m ) {
		Result result = new Result();
		int len = m.length;
		int count = Integer.MAX_VALUE;
		if( len == 1 ) {
			String s = "("+m[0]+")";
			result = new Result( s, 0, m[0].r, m[0].c );
			return result;
		}
		if( len == 2 ) {
			String s = "(" + m[0]+m[1]+")";
			result = new Result( s, m[0].r * m[0].c * m[1].c, m[0].r, m[1].c );
			return result;
		}
		//split the m[]	
		for( int i = 0; i < len - 1; i++ ) {
			ArrayList<Matrix> sub1 = new ArrayList<Matrix>();
			ArrayList<Matrix> sub2 = new ArrayList<Matrix>();
			for( int j = 0; j <= i; j++ ) {
				sub1.add(m[j]);
			}
			for( int j = i + 1; j < len; j++ ) {
				sub2.add(m[j]);
			}
			Result s1 = findMin( sub1.toArray( new Matrix[sub1.size()]) );
			Result s2 = findMin( sub2.toArray( new Matrix[sub2.size()]) );
			int newCount = s1.ct + s2.ct + s1.start * s2.start * s2.end;
			
			String newStr = "(" + s1.s + ")(" +s2.s + ")";
			//result = new Result( newStr, newCount, s1.start, s2.end );
			
			if ( newCount < count ) {
				count = newCount;
				result = new Result( newStr, newCount, s1.start, s2.end );	
			}
		
		//int[] sMerge = { newCount, s1[0], s2[2] };
		
		//System.out.println(sub1.toString());
		//System.out.println(sub2.toString());
		
		}
		return result;		
	}
	
	class Result {
		int ct;
		String s;
		int start;
		int end;
		public Result() {}
		public Result( String str, int i, int st, int e ) {
			ct = i;
			s = str;
			start = st;
			end = e;
		}
	}
}
class Matrix {
	int r;
	int c;
	public Matrix( int Row, int Col ) {
		r = Row;
		c = Col;
		
	}
	public String toString() {
		return "[ " + r + " * " + c + " ] ";
	}
}