418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 5

ให้ $OPT(i,j,k)\,$ มีค่าเป็น yes ถ้า เราสามารถจัดวงเล็บในการคูณ $x_{i}x_{i+1}...x_{j}\,$ ให้มีค่าเท่ากับ $k\,$ ได้ และมีค่าเป็น no ถ้าเราไม่สามารถจัดวงเล็บในการคูณ $x_{i}x_{i+1}...x_{j}\,$ ให้มีค่าเท่ากับ $k\,$ ได้ หมายเหตุ $k\,$ นี้จะมีค่าเป็น $a,b,c\,$ ถึงแม้ผลสุดท้ายต้องการให้เป็น $a\,$ ก็ตาม แต่เนื่องจากว่า ก่อนที่จะได้เป็น $a\,$ อาจได้เป็นตัวอื่น ๆ ที่มากระทำกันจนกระทั่งได้ผลสุดท้ายเป็น $a\,$ ก็ได้

เขียนเป็น pseudocode ได้ดังนี้

<geshi lang="c"> PARENTHESIZATION

   for i = 1 to n do
       for k = a to c do
           if x[i] = k then
               M[i,j,k] = true
           else
               M[i,j,k] = false
   for l = 2 to n do
       for i = 1 to n-l+1 do
           j = i+l-1
           for k = i to j -1 do
               for alpha = a to c do
                   M[i,j,alpha] = false
               for alpha = a to c do
                   for beta = a to c do
                       if M[i,k,alpha] and M[k+1,j,beta] then
                           M[i,j,alpha * beta] = true
   return M[1,n,a]

</geshi>