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

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

ดังนั้น หากอินพุตเป็น s ="aolpeuvekyl" เอาต์พุตจะเป็น 5 เนื่องจาก palindrome เป็น "ระดับ"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ s
• กำหนดฟังก์ชัน dp() นี่จะใช้เวลา i, j
• ถ้าฉันเหมือนกับ j แล้ว
  • คืน 1
• มิฉะนั้น เมื่อ i> j แล้ว
  • คืน 0
• มิฉะนั้น
  • ถ้า s[i] เหมือนกับ s[j] แล้ว
    • ส่งกลับ 2 + dp(i + 1, j - 1)
  • มิฉะนั้น
    • ส่งกลับสูงสุดของ dp(i + 1, j) และ dp(i, j - 1)
• ผลตอบแทน dp(0, n - 1)

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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