class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        N = len(s)
        dp = [[0] * N for _ in range(N)]
        # 对角线必为1，i < j为0
        for i in range(N):
            dp[i][i] = 1
        # 从下往上遍历
        for i in range(N - 1, -1, -1):
            for j in range(i + 1, N, 1):
                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])
        return dp[0][N - 1]

动态规划 中等

https://leetcode-cn.com/problems/longest-palindromic-subsequence/

题解：https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/516-zui-chang-hui-wen-zi-xu-lie-dong-tai-hap0/