5. 最长回文子串 dp

给你一个字符串 s，找到 s 中最长的回文子串。

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) {
            return s;
        }

        int maxlen = 1;
        string ans = "";
        ans += s[0];

        int l, r;

        vector <vector<bool>> dp(n, vector<bool> (n, false));
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // 枚举字串长度
        for (int len = 2; len <= n; len++) {
            // 枚举左边界
            for (l = 0; l < n; l++) {
                // 确定右边界
                r = l + len - 1;
                if (r >= n) {
                    break;
                }

                if (s[l] == s[r]) {
                    if (len == 2) {
                        dp[l][r] = true;
                    }
                    else {
                        dp[l][r] = dp[l + 1][r - 1];
                    }
                }
                else {
                    dp[l][r] = false;
                }

                if (dp[l][r] && r - l + 1 > maxlen) {
                    maxlen = r - l + 1;
                    ans = s.substr(l, maxlen);
                }
            }
        }

        return ans;
    }
};