Python에서 가장 긴 회문 부분 시퀀스의 길이를 찾는 프로그램

<시간/>

소문자 문자열 s가 있다고 가정합니다. 우리는 s에서 가장 긴 회문 부분 수열의 길이를 찾아야 합니다.

따라서 입력이 s ="aolpeuvekyl"과 같으면 회문이 "레벨"이므로 출력은 5가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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)를 반환

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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"