最长回文字符串------动态规划

Manacher‘s Algorithm 能达到0(n)的时间复杂度，但是比较繁琐，实际用起来也是先查，所以使用更常用的动态规划算法，时间复杂度能到0（n^2）,比暴力算法0(n^3)要强

动态规划算法中两个重要概念是边界以及状态转移方程；
dp[i][j]是一个bool类型的变量数组，如果dp[i][j]==true,那么他表示字符串str从str[i]到str[j]是回文串

边界是：dp[i][i]=true,dp[i][i+1]=(str[i]==str[i+1])?true,false

状态转移方程：dp[i][j]=true if(dp[i+1][j-1]&&str[i]==str[j])
dp[i][j]=false if(str[i]!=str[j]
根据递推算法从边界出发的原理，注意到边界表示的是长度为 1 和 2 的子串，且每次转移时都对子串的长度减了 1，因此考虑按子串的长度和子串的初始位置进行枚举，即第一遍将长度为 3 的子串的 dp 值全部求出，第二遍通过第一遍结果计算出长度为 4 的子串的 dp 值 ……
代码如下：
class Palindrome {
public:
int getLongestPalindrome(string A, int n) {
// write code here
int ans;
bool* dp=new bool[n];
for(int i=0;i<n;i++)dp[i]=new bool[n];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)dp[i][j]=false;
if(n==1)return 1;
for(int i=0;i<n;i++)//遍历找出长度为2的回文
{
dp[i][i]=true;
if(i<n-1&&A[i]==A[i+1])
{
dp[i][i+1]=true;
ans=2;
}
}
for(int i=3;i<=n;i++)//从3开始遍历所有可能是回文串的子串长度
{
for(int j=0;j+i-1<n;j++)
{
if(dp[j+1][j+i-2]&&A[j]==A[j+i-1])
{
dp[j][j+i-1]=true;
ans=i;
}
}
}
return ans;
}

};