dp[i][j]代表s[i]到s[j]是否为回文串
若s[i] == s[j] && dp[i + 1][j - 1] == 1 那dp[i][j] = 1;
初始化要将考虑到类似 aba 的回文串 所以要初始化dp[i][i] = 1;
先枚举回文子串的长度 再考虑是否为回文串 这是因为在状态转移方程是由短字符串推向长字符串的
#include <bits/stdc++.h>
using namespace std;
string s;
int dp[1010][1010];
int main()
{
getline(cin, s);
int n = s.size();
int res = 1;
for(int i = 0; i < n; i++)
{
dp[i][i] = 1;
if(i + 1 < n && s[i] == s[i + 1]) res = 2, dp[i][i + 1] = 1;
}
for(int len = 3; len <= n; len++)
for(int i = 0; i + len - 1 < n; i++)
{
int j = i + len - 1;
if(s[i] == s[j] && dp[i + 1][j - 1]) dp[i][j] = 1, res = len;
}
cout << res << endl;
return 0;
}