3.5　最长回文子序列

和上面的题目类似，只是这道题从回文子串变成了回文子序列。力扣（LeetCode）上有很多题目都是这样的，只是将子串改成子序列就变成了另一道题。下面通过这两道题来看一下回文子串和回文子序列的不同。

题目描述（第516题）

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

示例1

输入："bbbab"

输出：4

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

示例2

输入："cbbd"

输出：2

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

思路

如果还是采取最长回文子串的思路，问题会比较复杂，因为子序列的数量会很多，我们考虑换一种思路。绝大多数字符串子序列的题目都可以使用动态规划来解决，从而避免让算法达到指数级复杂度。

假设字符串中间部分的最长回文子序列长度已经算出，下面比较两侧的字符。

●　如果两侧字符相同，那么新的最长回文子序列就加2。

●　如果两侧字符不同，那么新的最长回文子序列不变。

具体如下。

●　初始化一个n行n列的dp数组，其中n表示字符串的长度，dp[i][j]表示字符串s[i:j+1]中的最大回文子序列的长度。

●　使用两层循环找出所有的子串。

●　对每一个子串，我们考虑如下3种情况。

1．如果子串长度为1，那么dp[i][j]=1。

2．如果s[i]==s[j]，那么可以进行扩展 dp[i+1][j-1]+2。

3．如果s[i]!=s[j]，则无法进行扩展，我们取dp[i+1][j]和dp[i][j-1]较大者即可。

●　最后返回dp[0][n-1]即可。

由于dp[i][…]依赖于dp[i+1][…]，因此外层循环需要从后往前进行遍历。

代码

复杂度分析

●　时间复杂度：O(n2)，其中n为字符串长度。

●　空间复杂度：这里使用了O(n2)的二维dp数组来存储中间状态，因此空间复杂度为O(n2)，其中n为字符串长度。

由于dp[i][j]仅依赖dp[i+1][j]和dp[i][j-1]，因此可以使用滚动数组技巧使空间复杂度降低到O(n)，这个技巧将在动态规划章节进行讲解。

复杂度分析

●　时间复杂度：O(n2)，其中n为字符串长度。

●　空间复杂度：我们使用了两个长度为n的数组来存储中间状态，因此空间复杂度为O(n)，其中n为字符串长度。

实际上，我们可以只使用一个数组和一个pre变量来解决这个题目，这次pre不再是数组而是一个数，具体解法留给读者来思考。