题解 | #最长回文子串#

dp[i][j]表示从i到j是否为回文。如果是回文，那么字符串的两端一定相等，并且除开首尾两个字符剩下的子串也一定是回文。用i表示最左端，d表示字符串长度，则最右端为j=i+d-1。
则有：

   if(A[i] == A[j] && dp[i+1][j-1] == true)
   {
       dp[i][j] = true;
   }

递推问题可以通过不断测试子串长度为1、2、3...n来求解。在更新dp[i][j]时更新最大长度即可，每次的回文长度就是子串长度d;

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        //dp[i][j]表示从i到j是回文;
        int max_len = 1;

        vector<vector<bool> > dp(n+1, vector<bool>(n+1, false));

        //统计子串长度为1和2的情况;
        for(int i=0;i<n;i++)
        {
            //长度为1肯定是回文;
            dp[i][i] = true;
            //前后两个字符相同也是回文,长度为2;
            if(A[i] == A[i+1])
           ｛
                max_len = 2;
                dp[i][i+1] = true;
            ｝
        }

        //统计子串长度为3到n的情况;
        for(int d=3;d<=n;d++)
        {
            //从字符头部开始到尾部结束;
            for(int i=0;i<n;i++)
            {
                int j = i + d - 1;
                //子串最两边的字符相同并且中间的是回文;
                if(A[i] == A[j] && dp[i+1][j-1] == true)
                {
                    dp[i][j] = true;
                    max_len = max(max_len, d);
                }
            }
        }
        return max_len;
    }
};