难度中等6097
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd"
输出："bb"提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
动态规划
这道题暴力解法肯定是不行的，因为时间复杂度高达 O(n^3)，测试用例肯定是过不了，所以我们可以利用动态规划的思想：用空间换时间！
下面是动态规划的五部曲：
- 找到 dp 的含义，也就是定义状态
- 找出递推公式，也就是确定状态转移方程
- 初始化 dp
- 分析遍历 dp 的顺序
- 开始遍历
接下来分每一步来分析：
一、定义状态
一般来说我们 dp 数组都是用一维数组或者二维数组，我们先来考虑一下一维数组的情况，如果我们让 dp[i] 表示字符串第 i 的位置是一个回文串，但是我们可以发现无论是 i-1 还是 i+1，都很难找到对应的递推关系！
所以我们就得考虑用二维数组 dp[i][j] ，接下来我们先考虑一个问题，我们去求一个回文串 str，那么我们可以先求 str[i+1] 到 str[j - 1] 是否为回文串（其中 i 和 j 是对称的），依次类推，为了更好说明，下面给出图片：
我们就能得到这种递推的关系，也就是 判断 s[i, j] 是否为回文串 转化为 求 s[i+1, j - 1] 是否为回文串以及 s[i] 和 s[j] 是否相同！
而且我们让 dp[i][j] 就表示 i 到 j 这段字符串是否回文串！
二、状态转移方程
通过上述解释，我们能很快得到方程：dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1] == true) ? true : false
三、考虑初始化dp
因为我们让 dp[i][j] 就表示 i 到 j 这段字符串是否回文串，所以我们可以用 bool 值来初始化 dp，默认 dp 的初始值都为 false，这样子也有一个好处，就是等会方便我们在遍历的时候就不用判断 dp[i + 1][j - 1] 是否是 false，只需要判断它是否为 true即可！
四、考虑遍历顺序
这道题和其它动态规划题有点不同的就是这个遍历顺序，我们仔细想一下我们的推导公式，也就是 s[i][j] 是通过 s[i + 1][j - 1] 来获得的，也就是如下图所示的相对位置：
看到它们的相对位置，我们就能知道遍历的时候不可能从上到下遍历，因为这样子的话 dp[i][j] 就拿不到 i+1 行的递推信息，那么就错了，所以我们必须从下至上、从左往右遍历！
五、特殊情况
我们需要考虑一下遍历的时候一些不同的情况
- 如果 i == j ，此时说明指向了同一个元素，那么这也算是回文串
- 如果 i 和 j 相差一个元素，此时 s[i] == s[j] 的话，那么也是回文串
- 如果 i 和 j 的距离大于一个元素，那么就到运用我们的递推公式进行判断！
class Solution {
public:
string longestPalindrome(string s) {
int MaxStart = 0; // 最长子串的起始下标
int MaxNum = 1; // 最长子串的个数
vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false)); // dp二维数组，初始化为false
// i从下往上遍历，j从左到右遍历，注意j每次都从i大小处开始遍历
for(int i = s.size() - 1; i >= 0; --i)
{
for(int j = i; j < s.size(); ++j)
{
// 只需判断相同的情况，不同的话默认元素也是false，不需要更改
if(s[i] == s[j])
{
// 小于等于1个元素距离则直接true
if(j - i <= 1)
dp[i][j] = true;
else
if(dp[i+1][j-1] == true) // 大于1个元素距离则用递推公式判断
dp[i][j] = true;
}
// 若dp[i][j]是回文串，那么判断是否需要更新最值
if(dp[i][j] && j - i + 1 > MaxNum)
{
MaxNum = j - i + 1;
MaxStart = i;
}
}
}
return s.substr(MaxStart, MaxNum);
}
};