题解 | #最长回文子串#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    
    int getLongestPalindrome(string A) {
        // write code here
        int max_len = 0;
        //1. dp[i][j] [i,j]区间内是否为回文子串
        vector<vector<bool>>dp(A.size(),vector<bool>(A.size(),false));
        //2.初始化 全部为false
        
        //3. 递推公式
        for(int i=A.size()-1;i>=0;i--){
            for(int j = i;j<A.size();j++){
                if(A[i] == A[j]){
                    if(j-i<=1){//两种类型 a aa
                        dp[i][j] = true;
                        max_len = max(max_len,j-i+1);
                    }else if(dp[i+1][j-1]){
                        dp[i][j] = true;// c aba c
                        max_len = max(j - i +1,max_len);
                    }
                }
            }
        }
        return max_len;
    }
};

1. 确定动态数组含义 dp[i][j]：[i,j]区间内是否为回文串
2. 初始化：全部为false
3. 递推公式
1. if(A[i] == A[i])
1. j-i <= 1：即aa，a这种情形
1. dp[i][j]=true
2. dp[i+1][j-1]==true
1. dp[i][j]=true
4. 遍历顺序：从递推公式可以看出，从右下开始遍历