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:

- Analysis and Design – analyze the problem and deduce a solution.
- Implementation – implement the algorithm to find the minimum number of operations.
**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 ** k **(we define this from the previous post). We do this by storing it in another 2D array of the same size as

*, which we call*

**DP***:*

**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

**= 6. This cell**

*j**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 multiplies with a suffix from a chain .*

**splits[1][6]**Let us now consider just the prefix. How then is prefix multiplied? We find that from * splits[1][3], *which in this case is 1. Therefore the it is formed by multiplying a prefix and a suffix . In this prefix we hit a base case where

*=*

**i***. Should this happen we return the matrix . The suffix is split from from*

**j***, which is 2. This in turns hits 2 base cases and returns the matrix and .*

**splits[2][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:

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.

## Reference

- Algorithms – Lecture 10: Dynamic Programming, Matrix Chain Multiplication and Typesetting (video lecture by Abhi Shelat of the University of Virginia)
- Matrix-chain Multiplication Problem (www.personal.kent.edu/)