共计 861 个字符，预计需要花费 3 分钟才能阅读完成。
这道题是动态规划几大问题的其中一种，为最长回文子串问题；
动态规划个人来说，觉得最重要的就是建立状态转移方程。对于方程变量，我认为最重要的是有几个构成的关键变量；
对于这道题，我们着手于 i~j 个字符，所以关注点在于 i 和 j，所以我们建立一个二维矩阵来保存动态规划途中的计算值。对于 dpi，其值为 1 时，意为 i - j 的字串是回文子串，为其他值则不是；
对于状态转移方程，我们可以这样想：对于一个回文子串，其子串也是回文子串，所以就有方程转移的定律：dpi=dpi+1
接下来就是如何遍历；对于遍历，我们一定要保证从边界开始，并且现有计算状态必须建立在已有建立状态之上。由于转换方程的特殊性，i,j 两个坐标都像两边扩散，所以我们可以根据 L，也就是子串的长度来进行计算；先将单个字符相应的值置为 1，然后 L =2….. 至 L =n; 在途中记录子串的长度；
代码如下所示：
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
#include<string>
using namespace std;
const int maxn=1010;
string data;
int matrix[maxn][maxn];
int main(){
getline(cin,data);
int len=data.size();
for(int i=0;i<len;i++){
matrix[i][i]=1;
}
int ans=1;
for(int i=1;i<len;i++){
if(data[i-1]==data[i]){
matrix[i-1][i]=1;
ans=2;
}
}
for(int L=3;L<=len;L++){
for(int i=0;i+L-1<len;i++){
int j=i+L-1;
if(data[i]==data[j]&&matrix[i+1][j-1]==1){
matrix[i][j]=1;
ans=L;
}
}
}
printf(“%d\n”,ans);
system(“pause”);
return 0;
}
