I have an algorithm that supposedly solves the matrix chain multiplication problem in $O(n^2)$ time. I have tested it only on trivial cases and they turned out to be correct.
By no means, am I a genius, but I was wondering if you guys could point out where this algorithm lacks.
The algorithm:
Base case:
MCM(A) = 0;
MCM(AB) = nrow(A) * ncol(A) * ncol(B)
Otherwise:
MCM(AB....JK) = min(MCM(B...K) + cost_of_mul(A, B...K),
MCM(A...J) + cost_of_mul(A...J, K),
MCM(AB) + MCM(C...K) + cost_of_mul(AB, C...K),
MCM(A...I) + MCM(JK) + cost_of_mul(A...I, JK));
where MCM is a nxn matrix that stores the minimum number of scalar products needed for the sequence from i to j (MCM[i][j])
The rationale behind this is that each grouping takes care of at least two matrices, and that is being handled when considering the minimum.