求取字符串最长的回文子串
题目：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
思路：
1.暴力解法：对每个字符而言，将其作为子串的第一个字符，然后从字符串的后面开始遍历，找到可以使当前起始字符为头的回文串，对字符串所有字符都进行上述的操作，即可求取最长的回文子串，但是这样时间复杂度很高
2.动态规划的思想：设定一个二维dp数组，长度是字符串的长度，dp[i][j]代表的含义是字符串的子数组从索引i到索引j是否可以构成回文串。其中主要有三种情况：一是，当i==j时，直接返回true；二是，当j-i == 1时，若s.charAt(i) == s.charAt(j)则返回true，否则返回false；三是，返回dp[i+1][j-1] && (s.charAt(i) == s.charAt(j))。还需要的遍历的时候，不是根据i，j直接来遍历，而是要外层根据子串的长度，内层根据子串的起始索引来遍历，否则当判断dp[i][j]时，dp[i+1][j-1]尚未进行判断。
代码：
// 求字符串中最长的回文子串
public String longestPalindrome(String s) {
/*
* 暴力解法
* 暴力解法就是依次判断s中的字符从前到后为作为子串的一个字符的时候最长的回文串长度
* 原子符 babad
* 什么时候可以使用动态规划 ？ 求最大 最小
*
* 2.使用dp来
*
* */
if(s.length() == 0 || s.length() == 1) return s;
boolean[][] dp = new boolean[s.length()][s.length()];
for (int i = 0; i < dp.length; i++) {
for (int j = i; j < dp.length; j++) {
if(i == j) dp[i][j] = true;
}
}
int maxLength = 0,maxIndex = 0;
// 最外层是子串的长度
for (int i = 1; i < s.length() + 1; i++) {
// j这一层是起始的索引
for (int j = 0; j + i - 1< s.length(); j++) {
int end = j + i - 1;
if(j == end) dp[j][end] = true;
else if(Math.abs(end-j) == 1) dp[j][end] = s.charAt(j) == s.charAt(end);
else dp[j][end] = dp[j+1][end -1] && (s.charAt(j) == s.charAt(end));
if(dp[j][end] && maxLength < i){
maxLength = i;
maxIndex = j;
}
}
}
return s.substring(maxIndex,maxIndex+maxLength);
}