最长回文子串【动态规划】

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例 2：
输入: “cbbd”
输出: “bb”

思路与算法: 对于一个字串，如果它是回文子串，并且长度大于2，那么它将首尾的两个字母去除以后，其仍然是一个回文串。<br />    所以这里可以采用动态规划的方法解决问题。用P(i,j)表示字符串s的第i到j个字母组成的串(s[i:j])是否为回文串：P(i,j) = true if Si ... Sj为回文串 else false<br />    这里的其他情况包含两种可能性: s[i,j]本身不是一个回文串，i > j此时s[i,j]不合法<br />    状态转移方程: P(i,j) = P(i+1, j-1) && (Si == Sj)<br />    也就是说: s[i+1, j-1]是回文串，而且s的第i个和第j个字母相同，s[i:j]才是回文串。<br />    边界条件：字串的长度为1或2的情况：P(i:i) = true; P(i,i+1) = (Si == Si+1)<br />    答案：P(i,j) = true中j-i+1(子串长度)的最大值。<br />    注意：在状态转移过程中，从长度较短的字符串向长度较长的字符串进行转移，要注意动态规划的循环顺序

string longestPalindrome(string s) 
{
    int n = s.size();
    if (n==0 || n==1)
        return s;
    vector<vector<int>> dp(n, vector<int>(n));

    int start=0;   // 回文串起始位置
    int max_len=1; // 回文串最大长度
    // 状态初始化: 针对单个字符i和两个字符[i,i+1]
    for(int i=0; i<n; ++i)
    {
        dp[i][i]=1;
        if (i<n-1 && s[i]==s[i+1])
        {
            dp[i][i+1]=1;
            max_len=2;
            start=i;
        }
    }
    // 搜索子串的长度，从长度为3的开始，并验证是否为回文子字符串
    for(int l=3; l<=n; ++l)
    {
        for(int i=0; i+l-1<n; ++i) // 子字符串开始位置i
        {
            int j = l+i-1;         // 子字符位置终止位置j
            if (s[i]==s[j] && dp[i+1][j-1])
            {
                dp[i][j] = (dp[i+1][j-1] && (s[i]==s[j]));
                start = i;
                max_len = l;
            }
        }
    }
    return s.substr(start, max_len);
}

欢迎交流，批评指正！