题解 | #最长回文子串#

动态规划

1. 边界条件：当只有一个数时，回文子串最大值为1
2. 从L即子串长度为2开始遍历
3. 当字符串首尾不相等时，f[i][j]不是回文子串
4. 当字符串首尾相等时
   4.1 当L==2时，f[i][j]是回文子串
   4.2 当L>2时，f[i][j] = f[i+1][j-1],即判断去掉首尾的字符串是否为回文子串，如果是，则f[i][j]是，否则不是

   class Solution {
   public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        int maxInt = 0;
        if(n < 2)
            return 1;
        bool f[n][n]; // 状态表示：f[i][j] 表示s[i,...,j]是否是回文子串
        for(int i = 0; i < n; i++)
            f[i][i] = true;
        // L为子串的长度
        for(int L = 2; L <= n; L++) {
            for(int i = 0; i < n; i++) { // 从左边界开始遍历，作为子串的左起始点
                int j = i + L -1; // j为子串右终止点
                if(j >= n)
                    break;
                if(A[i] != A[j])  // 如果最后一个字符和第一个不同
                    f[i][j] = false;
                else {
                    if(i + 1 > j - 1) // L == 2 
                        f[i][j] = true;
                    else
                        f[i][j] = f[i + 1][j - 1];
                }
            }
        }
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if(f[i][j])
                    maxInt = max(maxInt, j - i + 1);
        return maxInt;
    }
   };