#include <algorithm>
//还看到了dp的做法，dp做法主要是要想出来如何将大问题分解小问题，这道题就是一个二维dp。
//用dp[i][j]表示以i开始，以j结束的字符串是否是回文串。
//当i=j时，dp[i][j] = (s[i] == s[i]) = true;
//当j = i +　1 时，dp[i][j] = (s[i] == s[i+1])；
//其他，dp[i][j] = (dp[i-1][j+1] && s[i]==s[j])
//动态规划
class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        vector<vector<int> > dp(len+1,vector<int>(len+1,0));
        //dp[i][j]代表从i到j-1中是否是回文串，1代表是，0代表不是
        //循环的时候i从大到小循环，j从小到大循环
        int maxLen = 0;
        int start = 0;
        int end = 0;
        for(int i=len-1;i>=0;i--)
        {
            for(int j=1;j<=len;j++)
            {
                if(i==j-1)
                    dp[i][j]=1;
                else if((i+1==j-1)&&(s[i]==s[j-1]))
                    dp[i][j]=1;
                else
                    dp[i][j]=((dp[i+1][j-1])&&(s[i]==s[j-1]));  
                if(dp[i][j]==1)
                {
                    if(j-i>maxLen)
                    {
                        start = i;
                        end = j-1;
                        maxLen = j-i;
                    }                    
                }
            }
        }
        return s.substr(start,end-start+1);
    }
};