动态规划：求最长回文子串

求最长回文子串

给定一个字符串s，找出s中最长的回文子串

回文字符串：如果一个字符串的逆序和原始字符串相同，则称该字符串为回文字符串。

input：s= "mnbalevelabst";
output：balevelab
reason：

算法思路：

定义状态数组dp，其中dp【i】【j】表示s[i]到s[j]的字符串是否是回文字符串，如果是回文字符串，则令dp【i】【j】=1，如果不是回文字符串，则令dp【i】【j】=0；

如果，s[i]=s[j],那么只要s[i+1]=s[j-1]的字符串是回文字符串，那么s[i]=s[j]的字符串就是回文字符串。反之，s[i+1]=s[j-1]的字符串不是回文字符串，那么s[i]=s[j]的字符串就不是回文字符串。

如果，s[i]！=s[j],那么只要s[i]=s[j]的字符串就一定不是回文字符串。因此，状态转移方程为：

dp【i】【j】=dp【i+1】【j-1】，s【i】=s【j】

		0                                ，s【i】！=s【j】

代码如下：

//求最长回文字符串
string maxHuiwen(string s)
{int len = s.size();int start = 0;//最长的回文子串的起始位置int max_length_huiwen = 1;//定义状态数组dp ，其中dp[i][j]表示s[i]到s[j]的字符串是否是回文字符串，//如果是回文字符串，则令dp【i】【j】=1，//如果不是回文字符串，则令dp【i】【j】=0；int dp[50][50] = { 0 };for (int j = 1; j < len; j++){for (int i = 0; i < j; i++){if (s[i] == s[j]){if (j - i < 3){dp[i][j] = 1;}else{dp[i][j] = dp[i + 1][j - 1];//状态转移方程}}if (dp[i][j] == 1&& (j-i+1)>max_length_huiwen){max_length_huiwen = j - i + 1;start = i;}}}return s.substr(start, max_length_huiwen);
}void test_maxhuiwen()
{string str = "mnbalevelabst";cout << "最长的回文子串为：" << maxHuiwen(str) << endl;
}

代码详解：
j=1，i=0；不满足s[i] == s[j]，结束当j=2;

j=2，i=0；
不满足s[i] == s[j]，i++;

j=2，i=1；
不满足s[i] == s[j]，结束当前循环，j++;

j=3，i=0；
不满足s[i] == s[j]，i++;

一直循环，直到如下：
j=7，i=5；
满足s[i] == s[j]，记录在案，记录回文子数组长度max_length_huiwen = j - i + 1=3;start = 5;

继续循环到下面如下步骤：
一直循环，直到如下：
j=10，i=2；
满足s[i] == s[j]，记录在案，记录回文子数组长度max_length_huiwen = j - i + 1=8;start = 2;

如此，一直到循环结束，该记录的所需数据不会再发生改变。
ps：今天的内容到这里就结束了，谢谢观看！！！

上嘉路