MATRIX CHAIN MULTIPLICATION !!! (go to the link post here for the source code)

DYNAMIC PROGRAMMING:

Problem:

Given
dimensions:

p0,p1,p2,... pn

determine the “multiplication sequence” that minimizes
the number of scalar multiplications in computing
A1,A2,A3..An . where Ai has a dimension p(i-1) X p(i)

That is, determine how to parenthisize
the multiplications.



SOURCE CODE FOR THE SOLUTION TO THIS PROBLEM


/* I HAVE ALLOCATED MEMORY STATICALLY FOR TESTING PURPOSES.

P[ ]={5,4,6,2,7}

means:

matrices of order 5 X 4 , 4 X 6 , 6 X 2 , 2 X 7

check http://www.cs.ust.hk/~dekai/271/notes/L12/L12.pdf

for the dry run and the detailed algorithm.

the Cpp program for the above problem is posted here

*/