最长回文子串c 动态规划

最长回文子串是指在一个字符串中最长的回文子序列。回文是指正着读和倒着读都一样的字符串。动态规划是解决最长回文子串问题的一种常用方法。动态规划的思想是将问题分解成子问题，通过求解子问题的最优解来得到原问题的最优解。在最长回文子串问题中，我们可以使用一个二维数组dp[i][j]来表示从i到j的子串是否为回文子串。如果dp[i][j]为true，则表示从i到j的子串是回文子串，否则不是。我们可以通过以下步骤来求解最长回文子串：
1. 初始化dp数组，将所有dp[i][i]都设置为true，表示单个字符是回文子串。
2. 遍历字符串s，从长度为2的子串开始，依次判断每个子串是否为回文子串。如果是，则将dp[i][j]设置为true。
3. 在遍历的过程中，记录最长回文子串的长度和起始位置。
4. 最后，通过起始位置和长度来截取最长回文子串。

下面是一个示例代码，可以帮助你更好地理解动态规划求解最长回文子串的过程：

class Solution {
public:
string longestPalindrome(string s) {
int len=s.size();
if(len<2) return s;
bool dp[len][len];//布尔型，dp[i][j]表示从i到j是否构成回文
int max_count=1;//最大字串的长度
int start=0;//最长字串的起始位置
for(int j=0;j<len;j++) {
for(int i=0;i<j;i++) {
if(s[i]!=s[j]) dp[i][j]=false;
else if((j-i)<3)//(j-1)-(i+1)+1<2表示dp[i][j]的最大字串长度为1
dp[i][j]=true;
else {
dp[i][j]=dp[i+1][j-1];
}
if((j-i+1)>max_count&&dp[i][j]) {
max_count=j-i+1;
start=i;
}
}
}
return s.substr(start,max_count);//截取字符串
}
};