最长回文子串

动态规划典型题目
思考
1、字符串相关知识
2、遍历回文子串的方法
3、可以求逆串，然后找最长公共子串

lc 5

之前记长度和首坐标，最后再截取 不然会超时

class Solution {
public:
    string longestPalindrome(string s) {
        //动态规划
        //两种做法
        
        int len=s.length();
        if(len==0)
            return "";
        else if(len==1){
            return s;}
        string tmp=s.substr(0,1);
        int dp[len][len];
        memset(dp,0,sizeof(dp));//一定要初始化动态规划数组，否则提交结果和执行结果会不一样
        int ans=0;
        int index=0;
        for(int i=0;i<len;i++){
            dp[i][i]=1;
            if(i<len-1){
                if(s[i]==s[i+1]){
                    dp[i][i+1]=1;//初始化长度为2的
                    ans=2;
                    index=i;
                    // tmp=s.substr(i,2);
                }       
            }
        }
        

        for(int l=3;l<=len;l++){//枚举子串长度 求子串长为3/4/5的
            for(int i=0;i+l-1<len;i++){
                int j=i+l-1;//子串的右端点
                if(s[i]==s[j]&&dp[i+1][j-1]==1){
                    dp[i][j]=1;
                    ans=l;//当前长度
                    index=i;
                    
                }
            }

        }
        if(ans>1)
            tmp=s.substr(index,ans);
        return tmp;
    }
};