题解 | #最长回文子串#

动态规划 注意：

• dp[i][j]更新取决于dp[i+1][j-1]，即左下方的值，所以要一列一列的更新
• 初始化len的值为1，因为一个字符也是回文

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    int getLongestPalindrome(string A) {
        // write code here
        int n = A.size();
        // dp[i][j] 表示从i到j的字符串是否是回文
        // dp[i][j] = dp[i+1][j-1] && (A[i+1] == A[j-1])
        vector<vector<bool>> dp(n, vector<bool>(n)); 
        for(int i = 0;i < n; i++){
            dp[i][i] = true;
        }
        
        int begin = 0, len = 1;
        // 填dp，一列一列填
        for(int j = 1; j < n; j++) {
            for(int i = 0; i < n; i++) {
                if(A[i] == A[j]) {
                    if(j - i < 3) {
                        // 中间只有一个字符 或没有字符，取决于两端是否相等
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                
                if(dp[i][j] && (j - i + 1) > len) {
                    begin = i;
                    len = j - i + 1;
                }
            }
        }
        return len;
    }
};