title: Algorithm-parenthesize of string from Dynamic Programming by Vazirani et. al
body: <blockquote>
    <p>Consider the problem of examining a string x = x1x2 ...xn from an
    alphabet of k symbols, and a multiplication table over this alphabet.
    Decide whether or not it is possible to parenthesize x in such a way
    that the value of the resulting expression is a, where a belongs to
    the alphabet. The multiplication table is neither commutative or
    associative, so the order of multiplication matters.</p>
  </blockquote>
  
  <p>Write the below in matrix table form for understanding : a,b,c along x and y axis.</p>
  
  <blockquote>
    <p>(a,a)=a;
     (a,b)=c (a,c)=c</p>
    
    <p>(b,a)=a (b,b)=a (b,c)=b</p>
    
    <p>(c,a)=c (c,b)=c (c,c)=c</p>
    
    <p>For example, consider the above multiplication table and the
    string bbbba. Parenthesizing it (b(bb))(ba) gives a, but ((((bb)b)b)a)
    gives c. Give an algorithm, with time polynomial in n and k, to decide
    whether such a parenthesization exists for a given string,
    multiplication table, and goal element.</p>
  </blockquote>
  
  <p>I unserstood the ques but i donot understand how to start with this.</p>
  
  <p>i am required to solve the following in C, C++ . Python etc are not allowed.
  Iam guessing a boolean approach might work.</p>