The Dynamic Programming technique is for the program who will use recursive function and there are many redundant computations. As such, use a table to record the computed data. Every time the program want to do the recursion, it will first check the table. If the table has the answer, them just use it but not computes again. On the other hand, if there is no answer in the table, then the program starts to do the recursion and save the result in the table for use in next time.
The Main program is as following described.
// Main Matrix Chain Code
for(int l = 2; l <= Count ; l++)
{
for(int i = 1; i <= (Count-l+1); i++)
{
int j = i+l-1 ;
Multi[i][j] = INT_MAX;
for (int k = i; k <= (j-1); k++)
{
MultiplyCount = Multi[i][k] + Multi[k+1][j] + (Input[i-1] * Input[k] * Input[j]);
if (MultiplyCount < Multi[i][j] )
{
Multi[i][j] = MultiplyCount ;
Cut [i][j] = k ;
}
}
}
}
The source code can be download from here: Source Code of Matrix Chain