题目描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
前言：在两三个月前，这道题练过，现在记忆上有点模糊，今天在把这道题刷一遍，巩固一下。
LeetCode上的记录。
解题思路：
1.首先，我们要解题，那么我们就要知道回文串的概念，回文串，我这里就简单的讲一下，就是类似于，ABA，AABB这种，具体的，大家可以自行百度，这个很好理解。再者呢，就是理解子串的概念，子串和子序列容易搞混，希望大家也可以自行百度，要是题都不懂，那么就别说解题了。
2.子串，想到子串，那么我们以前做过的算法题里面有，求出一个字符串的所有子串，然后再一个一个去对比，但是如果用的是这种解法的话，时间复杂度达到了O(n3)这是完全不能忍受的，所以我们要想想怎么优化。
3.优化，我们想一下，首先我们题目要求是要所有子串的，但是求所有子串据我了解的最低的时间复杂度就是O(n2)，所以我们把优化方向，放到求解回文串上，如果我们能将求出回文串只要O(1)的复杂度，那么整个题目就可以优化一个量级。
4.实现，我们可以用到动态规划来解，怎么解呢，我们判断一个字符串是不是回文串，那么我们首先要判断，首字母和尾字母是否相等，然后依次向前推。哪么如果我们已经记录了去掉收尾字母的子串是否是回文串，哪不就解决了吗。
代码实现：
public String longestPalindrome(String s) {
if(s.length()<2)return s;
int len = s.length();
char[] chars = s.toCharArray();
boolean[][] dp = new boolean[len][len];
//对于字符本身，它是回文串。
//初始化。
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
int begin = 0;
int res = 1;
//求所有子串
//这里面求所有子串的方法是有讲究的，间隔是逐渐增大的，为了DP好计算。
for (int i = 0; i < len; i++) {
for (int start = 0, end = i + 1; end < len; end++, start++) {
if (chars[start] == chars[end]) {
if (end - start + 1 <= 3) {
//子串长度小于3，直接设为True
dp[start][end] = true;
} else {
dp[start][end] = dp[start + 1][end - 1];
}
} else {
dp[start][end] = false;
}
if (dp[start][end]) {
int curLen = end - start + 1;
//记录最长的子串
if (curLen > res) {
res = curLen;
begin = start;
}
}
}
}
return s.substring(begin, res + begin);
}
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/