In the question Matrix Chain Multiplication you are given a chain of Matrices and is required to find the optimal way to multiply the matrices together. Normally this is solved using Dynamic Programming but I have found a greedy approach to this problem.
For example a chain of Matrices of the size of:
A B C D 40 * 20 20 * 30 30 * 10 10 * 30
First list all of the possible consecutive pairs, and the 2 different dimensions of the pair:
X AB: 40 * 30 BC: 20 * 10 <---- CD: 30 * 30
Then multiply the pair that has the lowest product in the X column and the list will turn into:
A BC D 40 * 20 20 * 10 10 * 30
Repeat the first 2 steps until all of the matrices are multiplied together:
X A(BC): 40 * 10 <---- (BC)D: 20 * 30 ABC D 40 * 10 10 * 30 X (A(BC))D: 40 * 30 <----
This have a time complexity of $O(2n^2 + 2n\log n)$.
I have tested a Java implementation on smaller test cases and it runs fine.
Does this method work, or is there a something I have overlooked?