leetcode [5. 最长回文子串](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/) 给你一个字符串 s,找到 s 中最长的回文子串。 动态规划法求解最大回文串。 cl
leetcode [5. 最长回文子串](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/)
给你一个字符串 s,找到 s 中最长的回文子串。
动态规划法求解最大回文串。
class Solution {public:
string longestPalindrome(string s) {
bool dp[1005][1005]; //存储状态
int len = s.length(),ans = 1,from = 0;
for(int i = 0;i < len;++i) //状态初始化
dp[i][i] = true;
for(int i = 0,j = len - 1;i < j;++i)
if(s[i] == s[i + 1])
dp[i][i + 1] = true,ans = 2,from = i;
else
dp[i][i + 1] = false;
for(int i = 2,j = len;i < j;++i) //状态方程
for(int p = 0,q = len - i;p < q;++p)
if(s[p] == s[p + i]){
if(dp[p + 1][p + i - 1])
dp[p][p + i] = true,ans = i + 1,from = p;
else
dp[p][p + i] = false;
}
else
dp[p][p + i] = false;
return s.substr(from,ans);
}
};