Pythonで最長のパリンドロームサブシーケンスの長さを見つけるプログラム

小文字の文字列sがあるとします。 sで最も長いパリンドロームサブシーケンスの長さを見つける必要があります。

したがって、入力がs ="aolpeuvekyl"のような場合、回文は「レベル」であるため、出力は5になります。

これを解決するには、次の手順に従います-

• n：=sのサイズ
• 関数dp（）を定義します。これにはi、jが必要です
• iがjと同じ場合、
  • 1を返す
• それ以外の場合、i> jの場合、
  • 0を返す
• それ以外の場合、
  • s[i]がs[j]と同じ場合、
    • return 2 + dp（i + 1、j-1）
  • それ以外の場合、
    • dp（i + 1、j）およびdp（i、j-1）の最大値を返します
• return 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