查找Python中最长回文子序列长度的程序

假设我们有一个小写的字符串s；我们必须找到最长回文子序列的长度，以s为单位。

因此，如果输入类似于s =“ aolpeuvekyl”，则输出将为5，因为回文为“级别”。

范例(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