L5 最长回文子串

字符串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"

解1:
解2：
解3：背包
解4：马拉车

string longestPalindrome(string s) {
        if(s.empty()) return "";
        int dp[s.size()][s.size()] = {0},left=0,right=0,len=0;
        //dp[i,j]=1 j=i;
        //dp[i,j]=s[i]==s[j] j=i+1; 
        //dp[i,j]=s[i]==s[j]&&dp[i+1,j-1] if j>i+1
        //注意 用int dp[][]
        for(int i=0;i<s.size();i++){
            dp[i][i]=1;
            for(int j=0;j<i;j++){
                dp[j][i]= s[i]==s[j] && (i-j<2 || dp[j+1][i-1]);
                          if(dp[j][i] && len <i-j+1){
                              len = i-j+1;
                              left = j;
                              right =i;
                          }
            }
        }
        return s.substr(left,right-left+1);
    }

string longestPalindrome(string s) {
      int len = s.length();
        //int **dp = new int*[len+1];
        vector<vector<int> > dp(len+1,vector<int>(len+1));
        //for(int i = 0; i < len+1; i++)
        //    dp[i] = new int[len+1];
        // for(int i = 0; i < len+1; i++){
        //     for(int j = 0; j < len+1; j++){
        //         dp[i][j] = 0;
        //     }
        // }
        for(int j = 0; j < len; j++){
            dp[j][j] = 1;
            dp[j+1][j] = 1;//这里也就是说的要手动初始话的这种情况
        }
        int l = 0, r = 0;
        for(int i = 1; i < len; i++){
            for(int j = 0; j+i < len; j++){
                if(s[j] == s[i+j] && dp[j+1][i+j-1]){
                    //为了保证j+1 <= i+j-1, i >= 2那么将i也就是长度为1的手动初始化
                    l = j;
                    r = j + i;
                    dp[l][r] = 1;
                }
            }
        }
        string str = "";
        for(int i = l; i <= r; i++)
            str += s[i];
        return str;
        //delete dp;
    }