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.
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.