题干：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
最开始看到这道题的时候，第一反应：不动脑子直接暴力，但算了算……工程量好像有点大，突然不想敲了，辗转反侧了一会，还是动脑吧！
首先，按照我的常识，我们直观上推断一个字串是不是回文字，一般是从中间往两边延伸或从两端向中间推，当然，如果有人是像计算机一样从第一个字母逐渐判断，那我无话可说，默默发出小草的声音……
由这个想法，我们可以得出式子对于s[i]~s[j](记为 m[i,j])可由s[i+1]~s[j-1]的情况判定（即若m[i+1,j-1]不是回文字的话，m[i,j]便用不着看了，这里要注意i <= j的问题），有递归的思想了哈！
但虽然我菜，但我的直觉递归貌似都捡不到便宜，既然貌似可以递归，那应该就可以递推（本人还是至今没分清动态规划与递推这两个的关系，对懂的兄弟求救！！！！）
然后是常规操作，画个二维a[n][n]的表格找关系！由于 i < j ，所以需要判断的都集中在右上角，嗯，这样的缺点矩阵就只能用到一半，浪费得有点心疼，但暂时先把这个问题撂一边，过了再想优化……
| 0,0 | 0,1 | 0,2 | 0,3 | 0,4 | 0,5 |
| 1,1 | 1,2 | 1,3 | 1,4 | 1,5 | |
| 2,2 | 2,3 | 2,4 | 2,5 | ||
| 3,3 | 3,4 | 3,5 | |||
| 4,4 | 4,5 | ||||
| 5,5 |
现在我们需要做的就是怎样无重复地将所有有数字的格子的情况判断了，由刚才的思想我们很容易得知，如已经涂色的两块，a[0,2]的情况可由a[1,1]的情况作为先决判断，若a[1][1]是回文字，再判断a[0][2],若不是，则不再判断
涂红棕色的部分是回文字为奇数的情况，绿色部分为偶数情况，相同方法将所有格子全部判断完成，代码1.0版本如下：
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size() ;
if(n == 0)
return "";
int **a = new int*[n];
for(int i = 0;i < n;i++){
a[i] = new int[n];
}
// for(int i = 0;i < n;i++)
// for(int j = 0;j < n;j++){ //试了下不手动初始化也过了
// a[i][j] = 0;
// }
for(int j = 0;j < n;j++){ //回文字为奇数项
for(int i= j;i >= 0;i--){
if(s[i] == s[2*j - i])
a[i][2*j-i] = 1;
else{
break;
}
}
}
for(int j = 1;j < n;j++){ //回文字为偶数项
for(int i = j-1;i >= 0;i--){
if(s[i] == s[2*j-1-i])
a[i][2*j-1-i] = 1;
else break;
}
}
for(int i = n-1;i >= 0;i--){
int k = i;
for(int j = 0; k < n;j++,k++){
if(a[j][k] == 1){
string m;
for(int l = j;l <= k;l++){
m.push_back(s[l]);
}
return m;
}
}
}
return " ";//没啥用，但不写它不给我编译过
}
};
很显然，这空间利用率，真是没谁了……所以，虽然过了，但……
这代码烂成这样，由于良心实在过意不去，还是改改吧，我瞅了我的代码一会，就发现了一个很致命的问题，我这申请的空间，貌似，不用也可以啊！我只要留一个记录（j-i）最长的情况就可以了啊！突然想打死自己
然后改了的代码如下：
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size() ;
int maxi = 0,maxj = -1;
for(int j = 0;j < n;j++){ //回文字为奇数项
for(int i= j;i >= 0;i--){
if(s[i] == s[2*j - i]){
if(2*j-2*i > maxj - maxi){
maxj = 2*j-i;
maxi = i;
}
}
break;
}
}
for(int j = 1;j < n;j++){ //回文字为偶数项
for(int i = j-1;i >= 0;i--){
if(s[i] == s[2*j-1-i]){
if(2*j-2*i-1 > maxj - maxi){
maxj = 2*j-i-1;
maxi = i;
}
}
else break;
}
}
string m;
for(int i = maxi;i <= maxj;i++){
m.push_back(s[i]);
}
return m;
}
};
呵呵，这时间和空间的锐减度我怕了，继续修炼吧，争取以后少干点这种傻事
原文：https://www.cnblogs.com/LISIYUWANG/p/13222131.html