最长回文子序列

最长回文子序列（递归||动态规划）

问题：给定一个字符串，找出最长的回文子序列。列如序列“CCABCBCAC”，它的最长回文子序列是“CABCBAC”(最长回文字符串)。
最直接解决问题的方法是：找出给定字符串的所有子序列，取出最大的子序列。这个方法的复杂度是指数级的，下面来分析怎么解决。

假设 A[0…n-1] 是给定的序列，长度为n。用 B[0,n-1] 表示 序列 A[0 … n-1] 的最长回文子序列的长度。

• 如果X的最后一个元素和第一个元素是相同的，这时：B[0,n−1]=B[1,n−2]+2B[0,n−1]=B[1,n−2]+2 , 还以 “BBABCBCAB” 为例，第一个和最后一个相同，因此 B[1,n-2] 就表示加粗的部分。

• 如果不相同：B[0, n-1)]= MAX ( B[1, n-1] , B[0, n-2] )。 以”BABCBCA” 为例，B[1,n-1]即为去掉第一个元素的子序列，B[0, n-2]为去掉最后一个元素。
  有了上面的公式，可以写出下面的程序：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int lps(char *str,int m,int n)
{
	//一个元素为 1 
	if(m==n)return 1;
	
	//因为只计算序列str[m....n] 
	if(m>n)return 0;
	
	//首尾相同 
	if(str[m]==str[n])
	return lps(str,m+1,n-1)+2;
	
	// 首尾不同 
	return max(lps(str,m+1,n),lps(str,m,n-1));
}
int main()
{
	char str[]="acmerandacm";
	int n=strlen(str);
	cout<<"The length of the LPS is "<<lps(str,0,n-1);
	return 0;
}

Output ：The length of the LPS is 5 (amama)

下面通过动态规划的方法解决，通过自上而下的方式打表，存储子问题最优解。

int lpsdp(char *str,int n)
{
	int dp[n][n],t;
	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++)
	{
		t=0;
		for(int j=0;j+i<n;j++)
		{
			//如果有首尾相同
			if(str[j]==str[j+i])
			{
				t=dp[j+1][j+i-1]+2;
			} 
			else
			{
				t=max(dp[j+1][j+i],dp[j][j+i-1]);
			}
			dp[j][j+i]=t;
		}
	} 
	//返回str[0][n-1] de结果
	return dp[0][n-1]; 
}