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!
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
