问题：
给出字符串s，求出s的最长回文部分列的长度。 样品
字符串' PATZJUJZTACCBCC '的最长回文子串为' ATZJUJZTA '，长度为9。 还是看暴力解法：列举部分列的两端点I和j，判断[i，j]区间内的部分列是否回文。 从复杂度方面来看，列举端点需要0(n2 )，判断回文需要0 ) n )，因此总复杂度为o ) n3 )。 终于遇到了暴力复杂性不是指数化的问题！ 但是，o(n )的复杂度n大时仍然不够。
将此问题转换为最长公共子串(LCS )问题，将：字符串s反转为字符串t，然后对s和t进行LCS建模求解，可能会得到所需的答案。 实际上，这种做法是错误的。 为什么这么说呢，是因为如果s中同时存在子字符串及其逆序的话，答案就会错误。 例如，如果将字符串S=“ABCDZJUDCBA”反转，则T=“ABCDUJZDCBA”，由此得到的最长公共子串为' ABCD '，长度为4，但实际上s的最长回文子串长度为1。 所以这样的做法是不行的。
动态规划解决
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]必须不是回文子串。
由此，能够写状态转移方程式
边界dp[i][i]=1，dp[i][i 1]=(S[i]==S[i 1] )？ 1:0。 还有一个问题没有解决到这里。 这意味着，如果按从小到大的顺序列出子串的两端，并更新dp[i]lj]，则不能保证计算出dp[i 1][ - 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(3360L是字符串整体的长度S.len ) )，也可以列举左端的点I，以使右端的点i L- 1也原样得到。
代码：
# include iostream # include string # include cstdio # includealgorithmusingnamespacestd； 常数上限=1000； char S[maxn]； //A包含数组，dp[i]包含以I结尾的连续数组的最大值和int dp[maxn][maxn]； int main () ) gets )； //下标从1开始读取intlen=strlen(s )，ans=1； 短信(DP，0，sizeof ) DP )； for(intI=0； ilen； I ) {dp[i][i]=1； if(Ilen-1 ) if ) s[I]==s[I1] ) {dp[i][i 1]=1； ans=2； //初始化时注意当前最长回文子串的长度}//状态转移方程for(intL=3； L=len； L//枚举子串的长度for(intI=0； i L-1len； I )//在列举子串的起点终点加上子串的长度(子串的长度包括他自己，所以必须小于-1)全长，({int j=i L-1； //子串右端点if(s[I]==s[j]DP[I1][j-1]==1) {dp[i][j]=1； ans=L； //更新最长回文子串的长度}}coutansendl； }