寻找最长回文子串的五种方法（暴力、中点扩散、DP、哈希+分叉、马纳赫尔） - 动态编程 O ( n 2 ) O(n^2) O(n2)

用动态规划来做上面的那个例题，dp[N][N]来存状态，dp[ i] [ j ]=1,表示字符串从i到j为回文串。 （1）当str[ i ]==str[ j ]时，dp[i+1][j-1]=1,则dp[ i ][ j ]=1 ( [i+1,j-1]为回文串，且str[ i ]==str[ j ]则[i,j]为回文串 ),否则dp[ i ][ j ]=0。

（2）当str[ i ]!=str[ j ]时,dp[ i ][ j ]=0。

可以得到状态转移方程

$dp[i][j]=\{\begin{array}{ll}dp[i+1][j-1]& str[i]==str[j]\\ 0& str[i]!=str[j]\end{array}$

在遍历方面也要注意，如果按照i和j从小到大的顺序来枚举子串的两个端点,然后更新dp[i]lj],会无法保证dp[i + 1][ - 1]已经被计算过,从而无法得到正确的dp[i][i]。我们可以遍历长度，长度从小到达依次增加，每次判断出左右端点即可。

代码如下：

//动态规划
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
bool dp[N][N];
int main()
{
    string str;
    getline(cin,str);//读入字符串
    int res=1;
    int n=str.length();
    for(int i=0;i<n;i++)
    {
        
        dp[i][i]=true;
        if(i<n-1&&str[i]==str[i+1])//判断边界条件
        {
            res=2;
            dp[i][i+1]=true;
        }
    }
    for(int l=3;l<=n;l++)//遍历字符串长度，最小从3开始（最小为1，加上左右两边）
    {
        for(int i=0;i+l-1<n;i++)//左边界
        {
            int j=i+l-1;//右边界
            if(str[i]==str[j]&&dp[i+1][j-1])
            {
                dp[i][j]=1;
                res=l;//更新时，一定l>=res
            }
                
        }
    }
    cout<<res<<endl;
    return 0;
}