题解 | #最长回文子串#

题目

题解：动态规划，以i为起点,j为终点的字符串是否为回文

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        //动态规划：以某个字符结尾的前面最大回文长度，dp[i][j]
        vector<vector<bool>>dp(n,vector<bool>(n,false));
        int res=0;
        for(int j=0;j<n;j++)//终点
        {
            for(int i=0;i<=j;i++)//起点
            {
                if(A[i]!=A[j])continue;
                else
                {
                    dp[i][j]=j-i>=2?dp[i+1][j-1]:true;//若起点终点两字符相同，则判断里面一层是否是回文
                    if(dp[i][j])res=max(res,j-i+1);//若是回文，更新最大长度
                }
            }
        }
        return res;
    }
};