回文子串（区间动态规划）_回文子串动态规划

题目链接：22算法设计与分析-动态规划 - Virtual Judge

分析：这道题目是一道比较简单的区间动态规划，但是有一个坑点卡了我挺长时间所以我想在这分析一下

设f[i][j]表示从i到j的最长回文子串长度

我一开始想的是当s[i]==s[j]时就有f[i][j]=f[i+1][j-1]+2,若s[i]!=s[j]则有f[i][j]=0，但是这样想是错误的，因为i~j是回文子串不仅需要s[i]==s[j]，还需要i+1~j-1也是回文子串才行，所以说我们知道s[i]==s[j]时不能直接使f[i][j]=f[i+1][j-1]+2，还应该判断一下i+1~j-1是不是回文子串，我一开始就是因为忘记判这个条件导致wa了两次，还有一点需要注意的就是空串也算是长度为1的回文子串，所以我们可以先把长度为2的回文字串预处理出来。

下面是代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1e3+10;
int f[N][N];
char s[N];
int main()
{
	scanf("%s",s+1);
	int l=strlen(s+1),ans=1;
	for(int i=1;i<=l;i++) f[i][i]=1;
	for(int i=1;i<l;i++)
		if(s[i]==s[i+1]) f[i][i+1]=2,ans=2;
	for(int len=3;len<=l;len++)
	for(int i=1;i+len-1<=l;i++)
	{
		int j=i+len-1;
		if((s[j]==s[i])&&(f[i+1][j-1])) f[i][j]=f[i+1][j-1]+2;
		ans=max(ans,f[i][j]);
	}
	cout<<ans;
	return 0;
}