Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

这里给出一种AC的动态规划解法：时间和空间复杂度O(n2)

f(i,j)表示范围在(i,j)的串是否在回文串，同时记录最大回文串长度和起始位置

f(i,j)=(s[i]==s[j]and(i−j<2orf[i+1][j−1]))i−j>=2

f[i][i]=true;

class Solution {public:    string longestPalindrome(string s) {        const int n=s.size();        bool f[n][n];        fill_n(&f[0][0],n*n,false);        size_t max_len = 1,start =0;        for(size_t i =0;i