[Algorithm] Dynamic Programming - Matrix Chain in C++ (矩陣相乘)

    Matrix Chain is a common example for demonstrating Dynamic Programming technique in algorithm. This article shows the implementation of using Dynamic Programming to solve the matrix chain problem. In the end, you can download the source code for more detail (source code is based on Visual Studio 2010 project).


     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