classSolution:# 解法1deflongestPalindromeSubseq(self, s:str)->int:
n =len(s)
dp =[[0]* n for _ inrange(n)]for i inreversed(range(n)):for j inrange(i, n):if i == j:
dp[i][j]=1elif s[i]== s[j]:
dp[i][j]= dp[i +1][j -1]+2else:
dp[i][j]=max(dp[i +1][j], dp[i][j -1])return dp[0][n -1]# 解法2deflongestPalindromeSubseq_2(self, s:str)->int:
n =len(s)
pre =[0]* n
cur =[0]* n
for i inreversed(range(n)):for j inrange(i, n):if i == j:
cur[j]=1elif s[i]== s[j]:
cur[j]= cur[j -1]+2else:
cur[j]=max(pre[j], cur[j -1])
pre = cur.copy()return pre[-1]