【区间DP】最长回文子串

题意

给你一个字符串$s$，求$s$的最长回文子串
例如s="babad",ans=bab或者ans=aba都是答案
长度小于等于1000

思路

这个题完全可以暴力，但是为了突出区间DP，还是来考虑一下如何区间DP。
转移方程跟前一篇区间DP很像，f[i][j]需要从f[i+1][j-1]转移而来。
起始:
f[i][i]=1;因为所有的单个也是子串，当然回文
f[i][i+1]=1;如果相邻的两个是相同的，这个也是回文
然后转移:
f[i][j]=f[i+1][j-1];如果f[i+1][j-1]在区间[i+1,j-1]是true并且此时s[i]==s[j]，那么区间[i,j]也是回文(true)

代码

bool f[1010][1010];
string longestPalindrome(string s)
{
    int n=s.size();
    if (n==1) return s;
    for (int i=0;i<n;i++)
        f[i][i]=true;
    for (int i=0;i<n-1;i++)
        if (s[i]==s[i+1])
            f[i][i+1]=true;
    for (int i=2;i<n;i++) //模拟长度
        for (int l=0;l+i<n;l++)
        {
            int r=l+i;
            if (s[l]==s[r]&&f[l+1][r-1])//转移
                f[l][r]=true;
        }
    //统计最长回文子串，取max
    int l=0,x=0,y=0;
    for (int i=0;i<n;i++)
        for (int j=i;j<n;j++)
            if (f[i][j] && j-i+1>l)//一直更新最大的l
                l=j-i+1,x=i,y=j;
    string ans="";
    for (int i=x;i<=y;i++)
        ans+=s[i];
    return ans;
}