题解 | #最长回文子串#

#include <stdio.h>
#include <string.h>


//动态规划解法
int main(void)
{
    char s[1000];
    
    while(scanf("%s",&s) != EOF)
    {
        int i, j;
        int len = strlen(s);
        //dp[i][j]表示s[i]到s[j]是不是回文串，是等于1，不是等于0；
        int dp[len][len];
        int maxlen = 1;
        // 特殊情况处理
        if(len<2)
        {
            printf("1\n");
        }
        // 边界条件处理,
        for(i=0;i<len; i++)
        {
            dp[i][i] = 1;
        }
        
        for(j=1; j<len; j++)
        {
            for(i=0; i<j; i++)
            {
                if(s[i] != s[j])
                {
                    dp[i][j] = 0;
                }
                else
                {
                    if(j-i < 3)
                    {
                        dp[i][j] = 1;
                    }
                    else
                    {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j] && j-i+1>maxlen)
                {
                    maxlen = j-i+1;                   
                }
            }
        }
        printf("%d\n",maxlen);
    }
    
    return 0;
}