Type：medium
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:"babad"Output:"bab"Note:"aba" is also a valid answer.
Example 2:
Input:"cbbd"Output:"bb"
这道题有很多更简便的解法，但我想练一练动态规划，因此用了动态规划去做。
本题题意为输入一个字符串，让你找里面最长的回文子字符串。基本想法是建立一个倒过来的string ss，两者取最长公共子字符串。
若使用动态规划，则建立一个temp[][]布尔型数组，temp[i][j]用来记录s[i]到s[j]之间的子字符串是否为回文。
首先给单个字符以及长度为2的字符串赋初始值。单个字符容易，用i值遍历s，从0到s.length()的temp[i][i]都赋为true；双字符同理，若temp[i] == temp[i+1]，则赋为true。
接下来应用到整个字符串，对于长度为3及以上的字符串，首先匹配头尾字符s[i]、s[j]是否相同，若不同直接赋为false，若相同则判断temp[s[i+1]][s[j-1]]是否为真，若为真则该字符串为回文，若为假则该字符串不是回文，返回false。在遍历的过程中记录最长的回文字符串即可。
此题有两个坑：
一是在class中的变量并不是全局变量，temp[][]没有初始的false值，因此在每一步判断中都要给temp赋值。
二是temp数组开的大小，我最开始赋temp[n][n]会报错，因此要开得足够大。
附代码：
class Solution {
public:
string longestPalindrome(string s) {
int n = s.length();
if(n<2) return s;
bool temp[2000][2000];
int maxLen = 1;
int start = 0;
int end = 0;
for(int i=0; i<n; i++){
temp[i][i] = true;
}
for(int i=0; i<n-1; i++){
if(s[i] == s[i+1]){
temp[i][i+1] = true;
maxLen = 2;
start = i;
end = i+1;
}
else temp[i][i+1] = false;
}
for(int len=3; len<=n; len++){
for(int i=0; i<=n-len; i++){
if(s[i] != s[i+len-1]) temp[i][i+len-1] = false;
else if(!temp[i+1][i+len-2]) temp[i][i+len-1] = false;
else if(temp[i+1][i+len-2]){
temp[i][i+len-1] = true;
if(len>=maxLen){
start = i;
end = i+len-1;
maxLen = len;
}
}
}
}
return s.substr(start, maxLen);
}
};
