C++题解 | #最长回文子串#

>首先，当子串长度超过2时，若欲使其为回文子串，其两端字母必须相等，且除去两端字母后的子串依旧为回文子串，即当s[i + 1 : j - 1]为回文子串且s[i] == s[j] 时，s[i : j]子串为回文子串。
则可得其状态转换方程为：（dp[i][j]表示s[i : j]是否为回文子串。）
dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j];
此处设置变量保留最长回文子串长度，以备之后输出

class Solution {
public:
     int getLongestPalindrome(string s, int n) {
        if (n < 2) {
            return n;
        }
         int maxLen = 1;
         bool dp[n][n];
         memset(dp, false, sizeof(dp));
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= n; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < n; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= n) {
                    break;
                }
                if (s[i] != s[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                }
            }
        }
        return maxLen;
    }
};