### help needed: matrix chain multiplication (reversed!)

Posted:

**Tue Oct 22, 2002 4:31 pm**To calculate an optimal solution for matrix chain multiplication we have to make two tables : one for the cost ('m' table) and other one to take the point where to break ('s' table).

Now given a sequence of matrix we can easily calculate an optimal solution.

Now the question is that:

If we are given an optimal solution can we calculate the 's' table fully?

What i mean is that if I have an optimal solution :

((A1A2)((A3A4)(A5A6)))

will i be able to fill up all the entries of the 's' table?

I can construct some parts of the table e.g.:

- | 1 | 2 | 3 | 4 | 5 | 6

-----------------------------------------------------

1 | - | 1 |? | ? |? | 2

2 | - | - |2 | ? |? | ?

3 | - | - | - | 3 | ? | 4

4 | - | - | - | - | 4 | ?

5 | - | - | - | - | - | 5

Now will i be able to find out the '?' marked entries in the following manner:

If i disregard A6 then the soluton becomes:

((A1A2)((A3A4)(A5)))

then we can say that in [1][5] there will be : 2

can we do it in this way? why ??

Imran

Now given a sequence of matrix we can easily calculate an optimal solution.

Now the question is that:

If we are given an optimal solution can we calculate the 's' table fully?

What i mean is that if I have an optimal solution :

((A1A2)((A3A4)(A5A6)))

will i be able to fill up all the entries of the 's' table?

I can construct some parts of the table e.g.:

- | 1 | 2 | 3 | 4 | 5 | 6

-----------------------------------------------------

1 | - | 1 |? | ? |? | 2

2 | - | - |2 | ? |? | ?

3 | - | - | - | 3 | ? | 4

4 | - | - | - | - | 4 | ?

5 | - | - | - | - | - | 5

Now will i be able to find out the '?' marked entries in the following manner:

If i disregard A6 then the soluton becomes:

((A1A2)((A3A4)(A5)))

then we can say that in [1][5] there will be : 2

can we do it in this way? why ??

Imran