给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1:
输入:

"bbbab"

输出:

4

一个可能的最长回文子序列为 “bbbb”。

示例 2:
输入:

"cbbd"

输出:

2

一个可能的最长回文子序列为 “bb”。

提示：

• 1 <= s.length <= 1000
• s 只包含小写英文字母

Solution

参考思路：《算法小抄》2.7

• 只涉及一个字符串/数组时，dp 数组的含义如下：**在子数组 array[i..j] 中，要求的子序列（最长回文子序列）的长度为 dp[i][j]**。
• 对于回文子序列

if (s[i] == s[j])
    // 它俩一定在最长回文子序列中
    dp[i][j] = dp[i + 1][j - 1] + 2;
else
    // s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？
    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

dp table

# @lc code=start
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n=len(s)
        dp=[[0 for _ in range(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):
                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]
# @lc code=end

参考思路：《算法小抄》2.8

使用状态压缩

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