子序列解題模闆：最長回文子序列

子序列問題是常見的算法問題，而且并不好解決。

首先，子序列問題本身就相對子串、子數組更困難一些，因為前者是不連續的序列，而後兩者是連續的，就算窮舉都不容易，更别說求解相關的算法問題了。

而且，子序列問題很可能涉及到兩個字元串，比如讓你求兩個字元串的 最長公共子序列，如果沒有一定的處理經驗，真的不容易想出來。是以本文就來扒一扒子序列問題的套路，其實就有兩種模闆，相關問題隻要往這兩種思路上想，十拿九穩。

一般來說，這類問題都是讓你求一個最長子序列，因為最短子序列就是一個字元嘛，沒啥可問的。一旦涉及到子序列和最值，那幾乎可以肯定，考察的是動态規劃技巧，時間複雜度一般都是 O(n^2)。

原因很簡單，你想想一個字元串，它的子序列有多少種可能？起碼是指數級的吧，這種情況下，不用動态規劃技巧，還想怎麼着呢？

既然要用動态規劃，那就要定義 dp 數組，找狀态轉移關系。我們說的兩種思路模闆，就是 dp 數組的定義思路。不同的問題可能需要不同的 dp 數組定義來解決。

1、第一種思路模闆是一個一維的 dp 數組：

舉個我們寫過的例子 最長遞增子序列，在這個思路中 dp 數組的定義是：

在子數組<code>array[0..i]</code>中，以<code>array[i]</code>結尾的目标子序列（最長遞增子序列）的長度是<code>dp[i]</code>。

為啥最長遞增子序列需要這種思路呢？前文說得很清楚了，因為這樣符合歸納法，可以找到狀态轉移的關系，這裡就不具體展開了。

2、第二種思路模闆是一個二維的 dp 數組：

這種思路運用相對更多一些，尤其是涉及兩個字元串/數組的子序列。本思路中 dp 數組含義又分為「隻涉及一個字元串」和「涉及兩個字元串」兩種情況。

2.1 涉及兩個字元串/數組時（比如最長公共子序列），dp 數組的含義如下：

在子數組<code>arr1[0..i]</code>和子數組<code>arr2[0..j]</code>中，我們要求的子序列（最長公共子序列）長度為<code>dp[i][j]</code>。

2.2 隻涉及一個字元串/數組時（比如本文要講的最長回文子序列），dp 數組的含義如下：

在子數組<code>array[i..j]</code>中，我們要求的子序列（最長回文子序列）的長度為<code>dp[i][j]</code>。

第一種情況可以參考這兩篇舊文：詳解編輯距離 和 最長公共子序列。

下面就借最長回文子序列這個問題，詳解一下第二種情況下如何使用動态規劃。

之前解決了 最長回文子串 的問題，這次提升難度，求最長回文子序列的長度：

我們說這個問題對 dp 數組的定義是：在子串<code>s[i..j]</code>中，最長回文子序列的長度為<code>dp[i][j]</code>。一定要記住這個定義才能了解算法。

為啥這個問題要這樣定義二維的 dp 數組呢？我們前文多次提到，找狀态轉移需要歸納思維，說白了就是如何從已知的結果推出未知的部分，這樣定義容易歸納，容易發現狀态轉移關系。

具體來說，如果我們想求<code>dp[i][j]</code>，假設你知道了子問題<code>dp[i+1][j-1]</code>的結果（<code>s[i+1..j-1]</code>中最長回文子序列的長度），你是否能想辦法算出<code>dp[i][j]</code>的值（<code>s[i..j]</code>中，最長回文子序列的長度）呢？

可以！這取決于<code>s[i]</code>和<code>s[j]</code>的字元：

如果它倆相等，那麼它倆加上<code>s[i+1..j-1]</code>中的最長回文子序列就是<code>s[i..j]</code>的最長回文子序列：

如果它倆不相等，說明它倆不可能同時出現在<code>s[i..j]</code>的最長回文子序列中，那麼把它倆分别加入<code>s[i+1..j-1]</code>中，看看哪個子串産生的回文子序列更長即可：

以上兩種情況寫成代碼就是這樣：

至此，狀态轉移方程就寫出來了，根據 dp 數組的定義，我們要求的就是<code>dp[0][n - 1]</code>，也就是整個<code>s</code>的最長回文子序列的長度。

首先明确一下 base case，如果隻有一個字元，顯然最長回文子序列長度是 1，也就是<code>dp[i][j] = 1,(i == j)</code>。

因為<code>i</code>肯定小于等于<code>j</code>，是以對于那些<code>i &gt; j</code>的位置，根本不存在什麼子序列，應該初始化為 0。

另外，看看剛才寫的狀态轉移方程，想求<code>dp[i][j]</code>需要知道<code>dp[i+1][j-1]</code>，<code>dp[i+1][j]</code>，<code>dp[i][j-1]</code>這三個位置；再看看我們确定的 base case，填入 dp 數組之後是這樣：

為了保證每次計算<code>dp[i][j]</code>，左、下、左下三個方向的位置已經被計算出來，隻能斜着周遊或者反着周遊：

我選擇反着周遊，代碼如下：

至此，最長回文子序列的問題就解決了。

主要還是正确定義 dp 數組的含義，遇到子序列問題，首先想到兩種動态規劃思路，然後根據實際問題看看哪種思路容易找到狀态轉移關系。

另外，找到狀态轉移和 base case 之後，一定要觀察 DP table，看看怎麼周遊才能保證通過已計算出來的結果解決新的問題

有了以上思路方向，子序列問題也不過如此嘛。