注意情况：s="" 则ans=""

 

基本思想：一个子串[i,j] 如果s[i]=s[j] 且子串[i+1,j-1]是回文子串，那么[i,j]是回文子串

 

使用数组记录状态，而非递归

dp[maxn][maxn] -> 若子串[i,j]是回文子串，则dp[i][j]表示它的长度，否则为0

逻辑上是使用数组，但是实际操作中使用了vector<vector<int>> dp(len,vector<int>(len))

(因为我不知道为什么使用数组时提交就会出错，虽然自己执行代码的话答案是正确的)

 

开始时的已知状态：s.size=1   => dp[i][i]=1

　　　s.size=2　=> (1) s[i]=s[i+1] dp[i][i+1]=2

　　　　　　　　　(2) s[i]!=s[i+1] 不做操作

根据已知状态推测状态：状态转移方程：若dp[i+1][j-1]!=0 则dp[i][j]=dp[i+1][j-1]+2，否则不做操作

状态的计算，是根据子串长度从小到大依次计算的

class Solution {public:    string longestPalindrome(string s) {        if (s.size() == 0)return "";        int len = s.size();        vector
     
      
       > dp(len, vector
       
        (len));        int maxlen = 1, rei = 0;        for (int i = 0;i
        
          2) {            for (int le = 3;le <= len;le++) {                for (int i =0;i <=len-le;i++) {                    int j =i+le-1;                    if (dp[i + 1][j - 1] != 0 && s[i] == s[j]) {                        maxlen = le;                        dp[i][j] = maxlen;                        rei = i;                    }                }            }        }        string ans = s.substr(rei, maxlen);        return ans;    }};