I have sequences of brackets like this [ > ) ]. I have to add brackets to the sequence that result would appear in this way [<> ()] because this is an optimal solution to the sequence. The approach to this problem is matrix chain multiplication and dynamic programming.
Explanation:
Sequence of brackets [ > ) ] equates to M1 M2 M3 M4 matrices. How should I match the brackets and matrices dimensions?
Matrices multiplication can be done if their inner dimensions are equal. So make one set of dimensions for all cases would be wrong.
[ - M1(2x3)
] - M2(3x4)
( - M3(4x5)
) - M4(5x6)
< - M5(6x7)
> - M6(7x8)
Then the sequence of brackets we could interpret like this:
[ > ) ] = (2x3 * 7x8 * 5x6 * 3x4). Obviously this is a wrong approach.
Please I would appreciate any ideas how to solve this.