418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 6
รุ่นแก้ไขเมื่อ 08:22, 6 ตุลาคม 2552 โดย Aoy (คุย | มีส่วนร่วม)
เนื่องจากพาลินโดรมคือสตริงที่อ่านจากซ้ายไปขวาหรือจากขวาไปซ้ายแล้วจะเหมือนกัน ดังนั้นการตรวจสอบว่าสตริงเป็นพาลินโดรมหรือไม่ เราก็ควรตรวจสอบว่าตัวอักษรตัวแรกของทางซ้ายกับตัวอักษรตัวสุดท้ายของทางขวาเหมือนกันหรือไม่ ถ้าเหมือนแล้วจะทำอะไร และถ้าไม่เหมือนจะทำอะไร
ให้ คือความยาวของลำดับย่อยที่เป็นพาลินโดรมที่ยาวที่สุดของสตริง
พิจารณากรณีที่ จะได้ว่า
กรณีที่ จะได้ว่า
ส่วนกรณีที่เหลือจะได้ว่า ถ้า
หรือ ถ้า
![{\displaystyle s[i]=s[j]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c50adf0ac4f834f911db164bfeecc496cc2ae249)
เขียนเป็น pseudocode ได้ดังนี้
<geshi lang="c"> PALINDROMIC(s,n)
for i = 1 to n do
M[i,i] = 1
for i = 2 to n do
for j = i-1 downto 1
M[i,j] = 0
for i = n-1 downto 1 do
for j = i+1 to n-1 do
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])
retrun M[1,n]
</geshi>
