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不再是數組而是一個數，具體解法留給讀者來思考。