【问题】给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 ：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 ：
输入: "cbbd"
输出: "bb"
【思路】前两天我们讲解了"中心拓展法"来解这道题目，今天我们使用动态规划的方法来写这道题目，首先我们要寻找一个递推式如下：
我们将f[i][j]表述为从j到i的子串为回文串，j <= i，此时dp的矩阵为左下三角！
如果a[i]==a[j]且f[i-1][j+1]=true, 那么f[i][j]也为true。
需要注意一点：当i-j < 2时，如果s[i]=s[j]，那么f[i][j]必为true，即单个字符或者两个相邻相同字符为回文子串。
class Solution {
public:
string longestPalindrome(string s) {
int slen = s.length();
if(slen == ) return "";
string res = "";
vector<vector<bool>> f(slen, vector<bool>(slen, false));
int maxlen = ;
int curlen = ;
for(int i = ;i < slen; i++){
for(int j = ;j <= i; j++){ // f[0][0]=true, 一定成立
if((s[i] == s[j]) && ((i-j < ) || (i > && f[i-][j+]))){
f[i][j] = true;
curlen = i - j + ;
if(curlen > maxlen){
maxlen = curlen;
res = s.substr(j, curlen);
}
}
}
}
return res;
}
};