โปรแกรมหาความยาวของลำดับย่อยพาลินโดรมที่ยาวที่สุดใน Python

สมมติว่าเรามีสตริงตัวพิมพ์เล็ก s เราต้องการหาความยาวของลำดับย่อย (subsequence) แบบพาลินโดรมที่ยาวที่สุดใน s

เช่น ถ้าข้อมูลนำเข้าคือ s = "aolpeuvekyl" ผลลัพธ์จะเป็น 5 เนื่องจากพาลินโดรมคือ "level"

ขั้นตอนการแก้ปัญหา (Dynamic Programming แบบ Top-down)

• n := len(s)
• ฟังก์ชัน dp(i, j):
  • ถ้า i == j คืน 1
  • ถ้า i > j คืน 0
  • มิฉะนั้น:
    • ถ้า s[i] == s[j] คืน 2 + dp(i+1, j-1)
    • มิฉะนั้น คืน max(dp(i+1, j), dp(i, j-1))
• คืน dp(0, n-1)

ตัวอย่างโค้ด

class Solution:
    def solve(self, s):
        n = len(s)
        def dp(i, j):
            if i == j:
                return 1
            elif i > j:
                return 0
            else:
                if s[i] == s[j]:
                    return 2 + dp(i + 1, j - 1)
                else:
                    return max(dp(i + 1, j), dp(i, j - 1))
        return dp(0, n - 1)

ob = Solution()
s = "aolpeuvekyl"
print(ob.solve(s))

ข้อมูลนำเข้า

"aolpeuvekyl"

ผลลัพธ์

5