最长回文子串——动态规划

动态规划思路

首先确定状态转移方程：数组S用来存储输入的字符串， 令dp[ i ] [ j ] 表示 S[ i ] 至 S[ j ] 所表示的子串是否是回文子串，是则为1，不是为0。这样根据S[ i ]是否等于S[ j ]，可以把转移情况分为两类： ①若S[i]=S[j],那么只要S[i+1]和S[j-1]是回文子串，S[i+1]至S[j-1]就是回文子串；如果S[i+1]至S[j-1]不是回文子串，则S[i]至S[j]一定不是回文子串。 ②若S[i]!=S[j]，那S[i]至S[j]一定不是回文子串。

状态转移方程

如果按照i和j从小到大的顺序来枚举子串的两个端点,然后更新dp[i]lj],会无法保证dp[i + 1][ j - 1]已经被计算过,从而无法得到正确的dp[i][i]。

如图11-4所示，先固定i=0,然后枚举j从2开始。当求解dp[0][2]时，将会转换为dp[1][],而dp[1][1]是在初始化中得到的;当求解dp[0][3]时,将会转换为dp[1][2], 而dp[1][2]也是在初始化中得到的;当求解dp[0][4]时，将会转换为dp[1][3], 但是dp[1][3]并不是已经计算过的值，因此无法状态转移。事实上，无论对ij和j的枚举顺序做何调整，都无法调和这个矛盾，因此必须想办法寻找新的枚举方式。 根据递推写法从边界出发的原理，注意到边界表示的是长度为1和2的子串，且每次转移时都对子串的长度减了1,因此不妨考虑按子串的长度和子串的初始位置进行枚举，即第一遍将长度为3的子串的dp值全部求出，第二遍通过第一遍结果计算出长度为4的子串的dp值…这样就可以避免状态无法转移的问题。如图11-5所示，可以先枚举子串长度L (注意: L是可以取到整个字符串的长度S.len()的)，再枚举左端点i,这样右端点i+ L- 1也可以直接得到。

代码示例：

#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1000;
char S[maxn];//A存序列，dp[i]存以i为结尾的连续序列的最大和
int dp[maxn][maxn];
int main()
{
	//由于版本问题，VS2019不支持使用gets();
	gets_s(S);//从下标为1开始读入
	int len = strlen(S), ans = 1;
	memset(dp, 0, sizeof(dp)); 
	for (int i = 0; i < len; i++)
	{
		dp[i][i] = 1;
		if (i < len - 1)
		{
			if (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++)//枚举子串起始端点 起始端点加上子串长度(子串长度包括他
			//本身，所以要 - 1）必须小于总长,
		{
			int j = i + L - 1;//子串右端点
			if (S[i] == S[j] && dp[i + 1][j - 1] == 1)
			{
				dp[i][j] = 1;
				ans = L;//更新最长回文子串长度;
			}
		}
	cout << ans << endl;
}