I think this should help you:
Suppose, M[i,j,a] represents the number of ways to parenthesize the
sub-array from i to j so as to produce the result a.
Similarly, M[i,j,b] and M[i,j,c] . I think you can implement this using
three dimensional array with the third dimension
of constant size i.e 3, in this case.
Now, you can observe that a is obtained by three ways i.e ac = ca = bc = a.
Refer to the multiplication table.
So, M[i,j,a] = SUMMATION over k varying from i to j-1 of(
M[i,k,a]*M[k+1,j,c] + M[i,k,c]*M[k+1,j,a] + M[i,k,b]*M[k+1,j,c] )
Similarly, you can compute M[i,j,b] and M[i,j,c]. You have to be very
careful of the order in which you would compute these
quantities. This order is same as that given in the matrix multiplication
parenthesis problem.
I hope this mail is of some use.
On 8/31/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>
>
> we define a multiplication on alpha table S={a,b,c} as follows:
> | a b c
> -------------
> a | b b a
> b | c b a
> c | a c c
> -------------
> For any string S, we can add some parentheses into it.For example,
> for
> x=bbbba, we add parentheses like this (b(bb))(ba), according to the
> table, the result is a.Now, for any string S=x1x2x3x4...xn，calcuate
> how many ways we can add parentheses into it, and the result is a
>
> It is a question after dyanmic programming chapter in my algorithm
> book, but I really don't know how to
> solve it.I think first define a matrix M,so M[i][j] is the result for
> how many ways to add parentheses to produce any character, fianlly
> the M[1][n] is the result for the problem above,but it will be very
> meomry cosumption, because M[i][j] has to record many kinds of
> situation,
> So are there other ways to solve it ? thanks!
>
>
> >
>
--
Mukesh Agrawal
Final Year UG CSE
IIT KGP
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
