题目描述

给定一个字符串，请你求出其中的最长回文子串的长度。

例如，给定字符串 Is PAT&TAP symmetric?，最长回文子串为 s PAT&TAP s，其长度是 11。

输出格式

输出一个整数，表示给定字符串的最长回文子串的长度。

样例

输入样例：
Is PAT&TAP symmetric?
输出样例：
11

算法1

分析：dp[i][j]表示s[i]到s[j]所表示的字串是否是回⽂字串。只有0和1，递推⽅程为：
1 当s[i] == s[j] : dp[i][j] = dp[i+1][j-1]
2 当s[i] != s[j] : dp[i][j] =0
3 边界：dp[i][i] = 1, dp[i][i+1] = (s[i] == s[i+1]) ? 1 : 0
⾸先初始化dp[i][i] = 1, dp[i][i+1]，把⻓度为1和2的都初始化好，然后从L = 3开始⼀直到 L <= len 根据动
态规划的递归⽅程来判断

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int dp[1010][1010];
int main()
{
    string s;
 getline(cin, s);
 int len = s.length(), ans = 1;
 for(int i = 0; i < len; i++) {
 dp[i][i] = 1;
 if(i < len - 1 && s[i] == s[i+1]) {
 dp[i][i+1] = 1;
 ans = 2;
    }
 }
 for(int L = 3; L <= len; L++) {
 for(int i = 0; i + L - 1 < len; i++) {
 int j = i + L -1;
 if(s[i] == s[j] && dp[i+1][j-1] == 1) {
 dp[i][j] = 1;
 ans = L;
       }
    }
 }
 printf("%d", ans);
    return 0;
}