查詢 Python 中最長迴文子序列長度的程式

假設我們有一個小寫字串 s；我們需要找出 s 中最長迴文子序列的長度。

因此，如果輸入如下 s = “aolpeuvekyl”，則輸出將為 5，因為迴文是 “level”。

為了解決此問題，我們將按照以下步驟操作 -

  • n := s 的大小
  • 定義函式 dp()。它將獲取 i、j
  • 如果 i 等於 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

更新時間：2020 年 12 月 12 日

724 次瀏覽

開啟你的職業生涯

完成本課程獲取認證

開始
廣告