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

假设我们有一个小写字符串s，我们需要在s中查找最长回文子序列的长度。

所以，如果输入是s =“aolpeuvekyl”，那么输出将是5，因为回文是“level”。

要解决这个问题，我们将按照以下步骤进行 –

n：= s的大小
定义一个函数dp()。这将采取i、j
if i等于j, then
- 返回1
否则，当i>j, then
- 返回0
否则，
- if s[i]等于s[j], then
  - 返回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))