题解 | 最长回文子序列

s = input()
n = len(s)
dp = [[0 for _ in range(n)] for _ in range(n)]
#dp[i][j]表示i，j区间内容最长回文子串
for i in range(n-1,-1,-1):
    dp[i][i] =1
    for j in range(i+1,n):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j-1] +2
        else:
            dp[i][j] = max(dp[i+1][j],dp[i][j-1])


print(dp[0][n-1])