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

เนื่องจากพาลินโดรมคือสตริงที่อ่านจากซ้ายไปขวาหรือจากขวาไปซ้ายแล้วจะเหมือนกัน ดังนั้นการตรวจสอบว่าสตริงเป็นพาลินโดรมหรือไม่ เราก็ควรตรวจสอบว่าตัวอักษรตัวแรกของทางซ้ายกับตัวอักษรตัวสุดท้ายของทางขวาเหมือนกันหรือไม่ ถ้าเหมือนแล้วจะทำอะไร และถ้าไม่เหมือนจะทำอะไร

ให้ $OPT(i,j)\,$ คือความยาวของลำดับย่อยที่เป็นพาลินโดรมที่ยาวที่สุดของสตริง $s[i,i+1,...,j]\,$

พิจารณากรณีที่ $i>j\,$ จะได้ว่า $OPT(i,j)=0\,$

กรณีที่ $i=j\,$ จะได้ว่า $OPT(1,1)=1\,$

ส่วนกรณีที่เหลือจะได้ว่า $OPT(i,j)=max(OPT(i+1,j),OPT(i,j-1))\,$ ถ้า $s[i]!=s[j]\,$

หรือ $OPT(i,j)=max(OPT(i+1,j),OPT(i,j-1),OPT(i+1,j-1))\,$ ถ้า $s[i]=s[j]\,$

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

<geshi lang="c"> PALINDROMIC(s,n)

   for i = 1 to n do
       for j = n downto 1 do
           if i < j then
               M[i,j] = 0
           else if i = j then
               M[i,j] = 1
           else
               if s[i] != s[j] then
                   M[i,j] = max(M[i+1,j],M[i,j-1])
               else
                   M[i,j] = max(M[i+1,j],M[i,j-1],2+M[i+1,j-1])
   return M[1,n]

</geshi>