解法要点题目链接：力扣https://leetcode-cn.com/problems/longest-palindromic-substring/
给你一个字符串 s，找到 s 中最长的回文子串。
这题是 hot100 题库中出现频率最高的动态规划了。下面我列举一下这题要记住的要点：
1.采用动态规划的技巧，这里得用个二维数组，dp[ j ][ i ] 表示从下表 j 开始，到 i 结束的字符串是否回文；
2.初始化动归数组，每个单独的字符肯定回文，所以循环字符串，所有的 dp[ i ][ i ] 都是 true；
3.两层循环，先定下子字符串的尾部，尾部从 1 开始，循环到 s.length()-1；头部始终从 0 开始，循环到尾部减一的位置；
4.只有当头尾字符串都一样，才有可能是回文子串，如果头尾中间没有字符，或者就一个字符，我们可以直接判断它就是回文子串；如果中间有两个以上字符，那么看看它头尾都缩进去一位的子字符串是否回文，这俩要么都回文，要么都不回文；
5.很多人可能有疑问，在判断 j 开头 i 结尾的子字符串时，我咋知道 j+1 开头 i-1 结尾的字符串是不是回文呢？其实很简单，尾部为 i-1 的所有子串是否回文的结果 dp[ x ][ i-1 ] (0<=x 结尾提一点吧，所有的 hot100 题库的中等难度的题，大家最好都能形成肌肉记忆。 最开始你大部分看不懂，就抄答案，看懂思路，然后自己写，要默写，边写边想，如此来个三五遍，三遍最少，达到什么程度呢？看到这个题，你脑海中能以 N(1) 的时间复杂度调出这题的解题思路，然后顺着思路行云流水地写完代码。 做不到这种程度，你面试碰到这题都是有风险的，而且因为你见过这题，如果面试没写出来，肯定更是悔恨交加。所以，怎么说呢，反复训练，最好形成肌肉记忆，不要等到面试时给自己留下遗憾。 现在，关于最长回文子串这道题，你已经知道得和我一样多了~ 本专栏定期更新力扣算法讲解，希望以最容易记忆的方式帮你搞定面试算法题。class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if(len == 1){
return s;
}
// 动态规划数组表示两个下标（闭区间）之间的子字符串是否为回文子串
boolean[][] dp = new boolean[len][len];
// 先初始化dp数组，单个的字符，肯定是回文子串
for(int i = 0; i < len; i++){
dp[i][i] = true;
}
// l 和 r 记录最长回文子串的头尾下标，碰到比当前更长的就会更新
int l = 0;
int r = 0;
// i从1开始，内层从0开始，逐步计算出dp[j][i]是否为回文子串
for(int i = 1; i < len; i ++){
for(int j = 0; j < i; j ++){
// 回文子串肯定两头的字符是一样的
if(s.charAt(i) == s.charAt(j)){
// 如果头尾相邻（aa），或者头尾之间只隔了一个字符（aXa），那么这个肯定是个回文子串
if(i-j <= 2){
dp[j][i] = true;
} else {
// 如果不能直接判断是回文子串，那么就要依赖上一轮外层循环的计算结果了
// 反正以 i-1 结尾的所有子串是否回文，我们都算过，所以这里dp[j][i]我们肯定能知道
dp[j][i] = dp[j+1][i-1];
}
// 如果当前以下标 j 开头，i 结尾的字符串是回文子串，看看它是不是比之前的长
if(dp[j][i] && r-l < i-j){
l = j;
r = i;
}
}
}
}
// 注意 substring 是左闭右开区间，所以r得加1
return s.substring(l, r+1);
}
}
