一、思路

• 当前操作：计算长度为len的子串A[i...j]是否为回文；
• 子问题：已知更短的子串A[i+1...j-1]是否为回文，推导A[i...j]是否为回文；
• 下一个子问题：若A[i] == A[j]且内部子串是回文，则当前子串是回文；否则不是。

二、状态转移方程

• 定义dp[i][j]：子串A[i...j]是否为回文；
• 初始化：dp[i][i] = true（长度为 1 的子串是回文）；
• 状态转移：
• 若A[i] != A[j]：dp[i][j] = false；
• 若A[i] == A[j]：
• 若j - i + 1 == 2（长度为 2）：dp[i][j] = true；
• 否则：dp[i][j] = dp[i+1][j-1]。

三、代码

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    int getLongestPalindrome(string A) {
        int n = A.size();
        if (n == 0) return 0;
        vector<vector<bool>> dp(n, vector<bool>(n, false)); // 修正为bool类型
        int maxLen = 1; // ***** 单个字符长度至少为1
        
        // 初始化长度为1的子串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        
        // 按子串长度从2到n遍历
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len <= n; i++) {
                int j = i + len - 1; // 子串结束位置
                if (A[i] != A[j]) {
                    dp[i][j] = false;
                } else {
                    // 长度为2时，直接判定为回文
                    if (len == 2) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                // 更新最长回文子串长度
                if (dp[i][j] && len > maxLen) {
                    maxLen = len;
                }
            }
        }
        return maxLen;
    }
};