题解 | #最长回文子序列# Python3

import sys

# dp[i][j] 为 从 i 到 j 的最长子序列

# dp[i][j] = max(dp[i+1][j-1] + 2*(s[i]==s[j]),dp[i][j-1], dp[i+1][j])

# 需要知道 dp[i+1][j-1]和dp[i][j-1]的值，说明填表方向是,第一维从n到i，第二维从0到j
# 这种填表方向可行

s = input().strip()

n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
    dp[i][i] = 1

for i in range(n-1,-1,-1):
    for j in range(i+1,n):
        dp[i][j] = max(dp[i+1][j-1]+ 2*int((s[i]==s[j])), dp[i][j-1], dp[i+1][j])

print(dp[0][-1])