该问题区别于最长回文子串，子串必须是连续的，而子序列则可以跳跃，例如AABCAA的最长回文子串为AA，但是它的最长回文子序列为AABAA和AACAA.
下面给出两种解法，递归版和动态规划版：
- 递归版
递推公式：
递归出口：长度为1的字符串，最长回文子序列长度为1
如果S的最后一个元素和第一个元素是相同的，这时：LPS(0, n-1) = LPS(1, n-2) + 2 , 以AABCAA 为例，第一个和最后一个相同，因此计算 L(1,n-2) （绿色部分）。
-
如果不相同：LPS(0, n-1) = MAX ( LPS(1, n-1) , LPS(0, n-2) )。 以AABCAB为例，LPS(1,n-1)即为去掉第一个元素的子序列，LPS(0, n-2)为去掉最后一个元素
int lps(char *str, int i, int j)
{
//递归出口
if(i == j) // 一个元素的最长回文子序列为1
return 1;
if(i > j) // 因为只计算序列 str[i ... j]
return 0;if (str[i] == str[j]) return lps(str, i+1, j-1) + 2; else return max(lps(str, i, j-1), lps(str, i+1, j)); }
-
动态规划版
和递归的逻辑相反，自底向上，先解决子问题，再解决当前问题，递推公式和递归版相同。
int lpsDP(char *str, int n){
int dp[n][n];
memset(dp, 0, sizeof(dp));for(int i=0; i<n; i++) dp[i][i] = 1; //i 表示当前长度为 i+1 的子序列 for(int i=1; i<n; i++){ //考虑所有连续的长度为 i+1 的子串. 该串为str[j, j+i] for(int j=0; j+i<n; j++){ if(str[j] == str[j+i]) //首尾相同 dp[j][j+i] = dp[j+1][j+i-1] + 2; else dp[j][j+i] = max(dp[j+1][j+i], dp[j][j+i-1]); } } return dp[0][n-1];}
动态规划版需要注意的一个细节是，当j+1 <= j+i-1 (i >= 2)成立时，dp[j+1][j+i-1]才有意义，当 i=1 时，会出现dp[j+1][j]的情形，因此在最开始用memset(dp, 0, sizeof(dp));置0.
<div>
<img src="http://img.my.csdn.net/uploads/201604/13/1460521891_5670.png"/>
</div>
