题解 | #最长回文子串#

区间DP解法

class Solution {
public:

    int getLongestPalindrome(string s, int n) {
        // write code here
        if(n < 2) return n; 
        int ans = 1;

        bool f[1000][1000] = {0};
        for(int i = 1; i <= n; i ++) f[i][i] = 1;

        for(int len = 2; len <= n; len ++) // 枚举长度
        {
            for(int l = 0; l + len - 1 < n; l ++) // 枚举左端点
            {
                int r = l + len - 1;// 枚举右端点
                if(s[l] == s[r] && (l+1 == r || f[l+1][r-1]))
                {
                    f[l][r] = 1;
                    ans = max(ans, r-l+1);
                }
            } 
        }
        return ans;
    }
};