0516：最长回文子序列（★）

1
2
3
4
5
6
7
8
9

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        f = [[0]*n for _ in range(n)]
        for i in range(n-1,-1,-1):
            f[i][i] = 1
            for j in range(i+1,n):
                f[i][j] = 2+f[i+1][j-1] if s[i]==s[j] else max(f[i+1][j],f[i][j-1])
        return f[0][-1]