这题是让找出字符串 s 的最长回文子串，
最简单的一种解决方式就是截取字符串 s 的所有子串
，然后判断它的所有子串哪些是回文串，保存最长的回文串即可，这种解法虽然简单，但时间复杂度比较高。
还一种解决方式就是中心扩散法
，我们需要以每一个字符为中心往两边扩散，查找并记录最长的回文子串。查找完之后下一步我们还要以下一个字符为中心往两边扩散进行查找，这样效率也不是很高。这个时候我们可以对他进行优化，使用马拉车算法。
所以这题的最经典解法还是
马拉车算法
，关于马拉车算法大家可以看下
《算法秘籍》
中第 13 章的13.2 马拉车算法，这里就不在介绍。我们这里主要讲另外一种解决方式，动态规划。
我们定义二维数组dp[][]，如果dp[left][right]为true，则表示子串s[left,right]是回文子串，如果dp[left][right]为false，则表示子串s[left,right]不是回文子串。
如果
dp[left][right]是回文子串，首先
dp[left+1][right-1]必须是回文子串，并且
s[
left]和s[right]也必须相等，如下图所示。
1，如果s
[
left
]!
=s[
right]
，子串s[left,right]不可能是回文子串。
2，
如果
s
[
left
]=
=s[
right]
，
子串s[left,right
]
能不能构成回文子串还需要进一步判断：
2.1，如果left==right，也就是说只有一个字符，我们认为它是回文子串。即dp[left][right]=true（left==right）
2.2，如果right-left<=2，类似于"aa"，或者"aba"，中间最多只有一个字符，我们也认为它是回文子串，即dp[left][right]=true（right-left<=2）
2.3，如果right-left>2，需要判断dp[left+1][right-1]是否是回文子串，才能确定dp[left][right]是否为true还是false。
即dp[left][right]=dp[left+1][right-1]
所以我们可以找出递推公式如下：
dp[left][right]=s[left]==s.[right]&&dp[left+1][right-1]
这里要注意，因为
dp[left][right]的值要依赖
dp[l
e
ft+1][right-1]的值，所以不能从上到下一行一行的遍历。因为在二维网格中
dp[l
e
ft+1][right-1]是在
dp[lef
t][right]的下一行，所以必须先计算
dp[l
e
ft+1][right-1]
的值，才能计算
dp[lef
t][right]。
遍历方式有多种，可以从左到右一列一列的遍历，也可以从下到上一行一行的遍历，还可以从对角线往右上角一行一行的遍历，
无论哪种方式，都要保证在计算dp[left][right]的时候，dp[left+1][right-1]的值一定是计算过的
。
public String longestPalindrome(String s) {
// start表示最长回文子串开始的位置，为了后面截取。
// maxLen表示最长回文子串的长度
int start = 0, maxLen = 1;
int length = s.length();
boolean[][] dp = new boolean[length][length];
for (int right = 1; right for (int left = 0; left // 如果两种字符不相同，肯定不能构成回文子串。
if (s.charAt(left) != s.charAt(right))
continue;
// 下面是s[left]和s[right]两个字符相同情况下的判断。
if (right - left <= 2) {
// 类似于"a"，"aa"和"aba"，也是回文子串。
dp[left][right] = true;
} else {
// 类似于"a******a"，要判断他是否是回文子串，只需要
// 判断"******"是否是回文子串即可。
dp[left][right] = dp[left + 1][right - 1];
}
// 如果字符串从left到right是回文子串，保存最长的回文子串。
