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) </geshi>