Matrix Chain Multiplication

A Matrix Chain Multiplier is perhaps the quintessential example of dynamic programming, a technique that nearly every data structures and algorithms book explores. My implementation is no different from the rest, using <i>Introduction to Algorithms</i> by Cormen, Leiserson, and Rivest as the basis for its design. The problem can be stated as follows: given a chain <A<sub>1</sub>, A<sub>2</sub>,..., A<sub>n</sub>> of n matrices, where for i = 1, 2,...,n, matrix A<sub>i</sub> has dimension p<sub>i-1</sub> x p<sub>i</sub>, fully parenthesize the product A<sub>1</sub>A<sub>2</sub><sup>...</sup>A<sub>n</sub> in a way that minimizes the number of scalar multiplications. This program does exactly that, for a chain of up to 26 matrices. You may input your own dimensions for a matrix chain or have the computer generate them for you. If you choose to specify your own dimensions, you also have the option to input integer values for the matrix entries, since this program is capable of performing the multiplication.