题解 | #最长回文子串#

动态规划:dp[i][j] 表示字符串第i个字符到第j个字符长度的子串，是否是回文（1 or 0）

如果A[i]==A[j]  and dp[i+1][j-1]==1  则 dp[i][j]=1

否则dp[i][j]=0

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */

    int getLongestPalindrome(string A) {
        // write code here
        int dp[1001][1001]={0};
        int lens=A.size();
        int max_len=1;
        for(int i=0;i<lens-1;i++)
        {
            dp[i][i]=1;
            if(A[i]==A[i+1])
            {
                dp[i][i+1]=1;
                max_len=2;
            }
        }
        dp[lens-1][lens-1]=1;
        
        for(int ll=2;ll<lens;ll++)
        {
            for(int j=0;j<lens-ll;j++)
            {
                if(A[j]==A[j+ll]&&dp[j+1][j+ll-1]==1)
                {
                    dp[j][j+ll]=1;
                    max_len=max(max_len,ll+1);
                }else{
                    dp[j][j+ll]=0;
                }
            }
        }
        return max_len;
    }
};