四时宝库

最长回文子序列是我们上机考都应该学会的题型，意思大概是：给定一个字符串，我们要找到顺着读和反着读一样的最长序列，比如ABAC，这个最长序列就是ABA。

下面小编就给大家介绍一个DP算法：

DP

我们对于字符串S，定义一个dp[][]二维数组，dp[i][j] = 1表示S[i.....j]是回文子串。那么，对于它的子串S[i+1.....j-1]也就肯定是回文子串了。

另外，dp[i][i]也肯定算一个回文子串。

算法大概就是如此，理解也很容易。

好了，废话不多说，直接上代码，代码里面有注释，大家直接看就行。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 1010;
char S[maxn];//定义字符数组 
int dp[maxn][maxn];
int main()
{
	gets(S);//输入字符数组 
	int len = strlen(S), ans = 1;
	memset(dp, 0, sizeof(dp));//dp数组初始化 为0
	//边界
	for(int i = 0; i < len; i++)
	{
		dp[i][i] = 1;
		if(i < len - 1)
		{
			if(S[i] == S[i + 1])//判断相邻两个字符是否相等 
			{
				dp[i][i+1] = 1;
				ans = 2;//初始化时注意当前最长回文子串的长度 
			}
		}
	} 
	
	//状态转移方程
	for(int L = 3; L <= len; L++)
	{
		for(int i = 0; i + L - 1 < len; i++)
		{
			//i是字符串的左端点,j是字符串的右端点 
			int j = i + L - 1;//子串的右端点
			if(S[i] == S[j] && dp[i + 1][j - 1] == 1)
			{
				dp[i][j] = 1;
				ans = L;//更新最长回文子串长度 
			} 
		}
	} 
	
	cout << ans;
	system("pause");
	return 0;
}