Chương trình tìm độ dài dãy con đối xứng dài nhất (Longest Palindromic Subsequence) trong Python

Cho một chuỗi chữ thường s, tìm độ dài của dãy con đối xứng (palindromic subsequence) dài nhất. Dãy con không cần các ký tự liên tiếp.

Ví dụ: s = "aolpeuvekyl" → dãy con đối xứng dài nhất là "level" (độ dài 5).

Giải thuật (Đệ quy + Memoization / DP Bottom-up)

Định nghĩa dp(i, j) là độ dài LPS trong đoạn s[i..j].

• Nếu i == j: trả về 1 (một ký tự).
• Nếu i > j: trả về 0.
• Nếu s[i] == s[j]: return 2 + dp(i+1, j-1).
• Ngược lại: return max(dp(i+1, j), dp(i, j-1)).

Kết quả là dp(0, n-1).

Mã nguồn Python

class Solution:
    def solve(self, s):
        n = len(s)
        from functools import lru_cache
        @lru_cache(None)
        def dp(i, j):
            if i == j:
                return 1
            if i > j:
                return 0
            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))  # Output: 5

Đầu vào

"aolpeuvekyl"

Đầu ra

5