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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---