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

최장 회문 부분 수열을 DP를 이용해 구하려면
길이가 1인 문자열의 최장 회문 부분 수열의 길이부터 찾아나가서
최종적으로 길이가 n인 문자열의 최장 회문 부분 수열의 길이까지 찾아 올라가면 됨.

1. 길이가 1인 문자열 : 1
2. 길이가 2인 문자열 :
 2-1. 앞뒤 두 글자가 같으면 : 2
 2-2. 앞뒤 글자가 다르면 : 1
3. 길이가 3 이상 :
 3-1. 앞뒤 글자가 같으면 : 두 글자를 제외한 나머지 문자열의 최장 회문 부분 수열의 길이에서 2만큼 증가
 3-2. 앞뒤 글자가 다르면 : 앞글자를 제외한 문자열과 뒤 글자를 제외한 문자열 두 개의 길이중 큰 값 가져옴

위의 로직을 코드로 옮기면 다음과 같다.

def solve_dp(s):
    n = len(s)

    if n == 0:
        return 0

    cache = [[0 for _ in range(n)] for __ in range(n)]
    for i in range(n):
        cache[i][i] = 1

    for k in range(2, n + 1):
        for i in range(n - k + 1):
            j = i + k - 1
            if s[i] == s[j] and k == 2:
                cache[i][j] = 2
            elif s[i] == s[j]:
                cache[i][j] = cache[i + 1][j - 1] + 2
            else:
                cache[i][j] = cache[i][j - 1] if cache[i][j - 1] > cache[i + 1][j] else cache[i + 1][j]

    return cache[0][n - 1]


if __name__ == '__main__':
    s = input()
    print(solve_dp(s))

책의 소스를 보고 참조해서 짜긴 했는데 아직 이해가 좀 안 되는 부분도 있다.
나중에 한 번 더 봐야 할 듯.