题目
 
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 
示例 ：
 输入: “babad”
 输出: “bab”
 注意: “aba” 也是一个有效答案。
 
注意点
 
1、确定动态规划方程：dp[j][k] - 表示以下标为 j 为开始，以下标为 k 为结束的字符串是否为回文串；
 2、确定状态转移方程：
 
当字符串长度为0时，返回空字符串“”；
当字符串长度为1时，都是回文串；
当字符串长度为2时，当两个字符相同时为回文串；
当字符串长度大于2时，当头尾两字符相等，且dp[j + 1][k - 1]为回文串时，当前字符串为回文串。（当字符串长度大于2时，一个字符串要为回文串，则首尾一定相同，且除去首位的字符串一定为回文串；比如abba，头尾都为a，且bb为回文串，所以abba也为回文串）
 
实现
 
class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        // 定义动态规划方程
        boolean[][] dp = new boolean[length][length];
        // 最长回文自创默认为空字符串
        String reslut = "";

		/* 动态规划过程
			i：表示判断字符串的长度；
			j：表示判断字符串开始下标；
			k：表示判断字符串结束下标
		*/
		// 按字符串长度从1（0代表长度为1）开始遍历
        for (int i = 0; i < length; i ++) {
        	// 根据字符串长度从头开始遍历（确定开始下标）
            for (int j = 0; j + i < length; j ++) {
            	// 确定结束下标
                int k = j + i;
                
                // 字符串长度为1的情况
                if (i == 0) {
                	// 都是回文串
                    dp[j][k] = true;
                    
                // 字符串长度为2的情况
                } else if (i == 1) {
                    // 当两字符相等时为回文串
                    dp[j][k] = (s.charAt(j) == s.charAt(k));
                    
                // 字符串长度大于2的情况    
                } else {
                	// 头尾两字符相等，且dp[j + 1][k - 1]为回文串时，当前字符串为回文串
                    dp[j][k] = (s.charAt(j) == s.charAt(k)) && dp[j + 1][k - 1];
                }

				// 更新最长回文子串
                if (dp[j][k] && i + 1 > reslut.length()) {
                    reslut = s.substring(j, k + 1);
                }
            }
        }
		
		// 返回结果
        return reslut;
    }
}

给你一个字符串 s，找到 s 中最长的回文子串。
 
示例 1：
 
输入：s = “babad”
 输出：“bab”
 解释：“aba” 同样是符合题意的答案。
 示例 2：
 
输入：s = “cbbd”
 输出：“bb”
 示例 3：
 
输入：s = “a”
 输出：“a”
 示例 4：
 
输入：s = “ac”
 输出：“a”
 
这是自己第一次做出来动态规划的问题，感觉还是挺有成就感的。
 我们用i来指向字符串的开头，用j来指向字符串的结尾。判断字符串为回文串的其中一个条件为s[i]==s[j]。
 另一个条件为s[i+1]==s[j-1]。即两边相等之后，中间的内容也要相等。
 根据以上两个条件，我们就可以写出状态转移方程
 dp[i][j]=dp[i+1][j-1]^s[i]==s[j]
 
对于长度为1的字符串，他显然是一个回文串。而长度为2的字符串，当两个字母相等时为回文串。于是我们可以写出动态规划的边界条件
 dp(i,i)=true;
 dp(i,i+1)=(s[i]==s[j])
 这样我们就可以完成动态规划了，最终的答案就是所有dp[i][j]=true中j-i+1(即字符串长度)的最大值
 注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。
 
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    //dp[i][j]=dp[i+1][j-1]&&s1[i]===s1[j]
    //初始化二维数组
    const s1=s.split('')
    const len = s.length
    let maxLen=1
    let start=0
    let dp = new Array(len)
    for(let i =0; i<len;i++) {
        dp[i]=new Array(len);
        for(let j=0;j<len;j++) {
            dp[i][j]=0;
        }
        dp[i][i]=1
    }
    //先枚举答案字串长度，从长度最小的子问题开始
    for(let L=2;L<=len;L++) {
        //枚举左边界
        for(let i=0;i<len;i++) {
            let j = L+i-1
            if(j>=len) break//右边界越界
            if(s1[i]!==s1[j]) {
                dp[i][j]=0
            }
            else {
                if(j-i<3) { //如果长度为2，符合题意的条件是s1[i]===s1[j]
                    dp[i][j]=1
                }
                else {
                    dp[i][j]=dp[i+1][j-1]
                }
            }

            if(dp[i][j]&&j-i+1>maxLen) {
                maxLen = j-i+1
                start = i
            }
        }
    }
    return(s1.slice(start,start+maxLen).join(''))
};

半对
 
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 
示例 1：
 
输入: "babad"
 输出: "bab"
 注意: "aba" 也是一个有效答案。
 示例 2：
 
输入: "cbbd"
 输出: "bb"
 
思路一：翻转字符串法。
 
1.将整个字符串反转，然后判断原始的字符串是否在反转的字符串中出现。
 
2.只是出现还不够，还要验证该字符串是否是回文的。
 
class Solution {
public:
    string longestPalindrome(string s) {
        if (s.length()==1) return s;
        string rev=s;
        std::reverse(rev.begin(),rev.end());  //reverse函数，将字符串反转
        string res;
        if (rev==s) return s;
        int len=0;
        for (int i=0; i<s.length(); i++)
        {
            string tmp;
            for (int j=i; j<s.length(); j++)
            {
                tmp=tmp+s[j];
                if(len>tmp.length())
                    continue;
                else if (rev.find(tmp)!=-1)
                {
                    string q=tmp;
                    std::reverse(q.begin(),q.end());
                    if(q==tmp)
                    {
                        len=q.length();
                        res=tmp;
                    }
                }
                else
                    break;
            }
        }
        return res;

    }
};
 
思路二：动态规划法.
 
1.定义一个（len, len）的二维数组，数组的(i,i)是1，因为单个字符是回文字符。
 
2.如果s[i]==s[i+1],则是两个连续的字符，也构成回文。
 
3.从长度为三开始扫描，如果s[i]==s[j]&&d[i+1][j-1]==1,则构成一个新的回文字符串。
 
class Solution {
public:
    string longestPalindrome(string s) {
        int len= s.length();
        if (len==0||len==1) return s;
        int start=0;
        int max=1;
        vector<vector<int>> dp(len, vector<int>(len)); //注意vector<vector<int>>的初始化。
        for (int i=0; i<len; i++)
        {
            dp[i][i]=1;
            if (i<len-1&&s[i]==s[i+1])
                {
                    dp[i][i+1]=1;
                    max=2;
                    start=i;
                }
        }
        for (int l=3; l<=len; l++)
        {
            for (int i=0;i+l-1<len;i++)
            {
                int j= i+l-1;
                if (s[i]==s[j]&&dp[i+1][j-1]==1)
                    {
                        dp[i][j]=1;
                        max=l;
                        start=i;
                    }
            }
        }
        return s.substr(start,max);

    }
};
 
 

问题：
 
给出一个字符串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 。
 
        到这里还有一个问题没有解决,那就是如果按照i和j从小到大的顺序来枚举子串的两个端点,然后更新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 (注意: 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()
{
	gets(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;
}