5.10 최장 회문 부분 수열의 길이 - 재귀

5.5에서 구했던 문자열 수열과 비슷하게
이번에는 가장 긴 회문(pelindrome) 부분 수열의 길이를 구하는 문제를 풀어본다.
회문 : 정방향으로 읽거나 역방향으로 읽거나 같은 문자열을 의미. 예를 들어 abba는 회문이고 abc는 회문이 아님.

재귀 호출을 이용하기 위해서는 최적의 하위 구조가 존재해야 한다.

이 문제도 최적의 하위 구조가 존재하는데,
예를 들어 aabbccbbaa라는 문자열이 있다고 한다면
양쪽 끝에 a가 존재하므로 제거하고 abbccbba에 대한 최장 회문 부분 수열의 길이를 구하면 된다. (+2를 해주면 됨)
그러나 양쪽 끝의 문자가 다를 경우 앞에서 n-1개를 제외한 문자열의 부분 수열에서 구하고, 뒤에서 n-1개를 제외한 문자열의 부분 수열을 구해서 이 두 값의 최댓값을 구하면 된다.

종료 조건은 start index가 end index보다 크거나 같은 경우다.(크면 0, 같으면 1 반환)
(start는 앞에서부터 탐색하는 index, end는 뒤에서부터 탐색하는 index)
위의 조건을 코드로 옮기면 다음과 같다.

import sys

sys.setrecursionlimit(10 ** 5)


def solve(s, start, end):
    if start > end:
        return 0
    if start == end:
        return 1

    if s[start] == s[end]:
        return solve(s, start + 1, end - 1) + 2
    else:
        left = solve(s, start, end - 1)
        right = solve(s, start + 1, end)
        return left if left > right else right


if __name__ == '__main__':
    s = input()
    print(solve(s, 0, len(s) - 1))