# Matrix Chain Multiplication with C++ code – PART 3: Extracting the Sequence

In my previous post, I wrote about finding the minimum cost of multiplying a matrix chain using dynamic programming. In this post I build on top of what we have covered to extract the sequence of multiplying the chain itself.

This is part of a 3 part series:

1. Analysis and Design – analyze the problem and deduce a solution.
2. Implementation – implement the algorithm to find the minimum number of operations.
3. Extracting the Sequence – extract the sequence in which the chain is multiplied.

## Extract the Sequence

To do this we keep track of the point at which we split up the chain as prefix and suffix: the point (we define this from the previous post). We do this by storing it in another 2D array of the same size as DP, which we call splits:

int ops = DP[i][k] + DP[k + 1][j] + rc[i] * rc[k + 1] * rc[j + 1];
if (ops < DP[i][j]) {
DP[i][j] = ops;
splits[i][j] = k;
}


Now let us print out the elements of splits in dark blue. I will be reusing the example input from the previous post:

How do we interpret this? Let us start from where we got the main solution; where i = 1 and j = 6. This cell splits[1][6] signifies the last operation of multiplying the matrix chain – in the above table this maps to 3. This means in the last operation, a prefix from a chain $A_1 \ldots A_3$ multiplies with a suffix from a chain $A_{4} \ldots A_6$.

Let us now consider just the prefix. How then is prefix $A_1 \ldots A_3$ multiplied? We find that from splits[1][3], which in this case is 1. Therefore the it is formed by multiplying a prefix $A_1 \ldots A_1$ and a suffix $A_2 \ldots A_3$. In this prefix $A_1 \ldots A_1$ we hit a base case where i = j. Should this happen we return the matrix $A_1$. The suffix $A_2 \ldots A_3$ is split from from splits[2][3], which is 2. This in turns hits 2 base cases and returns the matrix $A_2$ and $A_3$.

If you repeat this recursive process with the top level suffix, you parenthesize the chain as such:

We can generalize a function mult that returns the resultant matrix that has been multiplied in the most optimal way from the matrix chain:

$mult(i, j)=\begin{cases}A_i \text{ if } i = j\\mult(i, k) \cdot mult(k+1, j)\text{ where } k = splits[i][j]\end{cases}$

The main solution is therefore mult(1, 6).

## Implementation

Below is an implementation of this:

Because we don’t have the contents of the matrices, I have the program output the parenthesis instead, along with the order in which it parenthesize them:

./mat-chain-mult-dp-trace < input.txt
multiply 2 and 3
multiply 1 and (2*3)
multiply 4 and 5
multiply (4*5) and 6
multiply (1*(2*3)) and ((4*5)*6)
((1*(2*3))*((4*5)*6))

Note that the numbers here are not integers but indices that map to its respective matrix in the matrix chain.

It is not that hard to convert the above code to multiply matrices. I will leave it as an exercise, should you be interested.

## Application

Why is this matrix chain multiplication problem so important that most computer science undergraduate programs must include it in their syllabus? The same reason applies for most algorithms you learn: some problems are just slight variations of another problem. Understanding one solution to a problem in the marrow of its bones may help you solve another similar problem.

Therefore, I encourage you to challenge yourself on these 2 problems to help solidify your understanding:

You can find my solutions to these problems in my github SPOJ repository.