题解 | #密码截取#

思路：动态规划方法
1、dp[j][i]=1表示从 j 到 i 满足回文子串的要求
2、状态转移方程

1、当 i==j 时，dp[j][i] == 1表示其本身
2、当 i - j == 1 时， 表示两元素相邻，若 str[i] == str[j] 则为回文子串，否则不是
3、其余状态转移方程：dp[j][i] = (str[i] == str[j] && dp[j+1][i-1]);
两元素不相邻，判断中间的子串是否为回文子串

第一种情况是看以这个位置为中心的奇数长度的回文子串，
第二种情况是以这两个位置为中心的偶数长度回文子串，
第三种情况是这是边界，看中间是否是回文子串。最后找到最大的 i 与 j 的距离即可。

#include <stdio.h>

#define MAX(a,b) ((a>b)?(a):(b))

static int find_pass(char *str)
{
    if(!str)
    {
        return -1;
    }
    int len = strlen(str);
    char dp[len][len];
    int maxlen = 1;
    for(int i = 0; i < len; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            if(i == j)    //相同置1
            {
                dp[j][i] = 1;
            }
            else if(i - j == 1)    //两元素相邻，判断是否为回文子串
            {
                dp[j][i] = (str[i] == str[j]);
            }
            else
            {
                //两元素不相邻，判断中间的子串是否为回文子串
                dp[j][i] = (str[i] == str[j] && dp[j+1][i-1]);
            }
            if(dp[j][i] && i-j+1 > maxlen)    //是回文子串，去最大值
            {
                maxlen = i - j + 1;
            }
        }
    }
    return maxlen;
}

int main()
{
    char str[2500] = {0};
    gets(str);
    int max = find_pass(str);
    printf("%d\n", max);
    return 0;
}