这道题常规做法，从任意位置向两边扫描，http://www.programcreek.com/2013/12/leetcode-solution-of-longest-palindromic-substring-java/
的解释非常容易懂。
public class Solution {
public String longestPalindrome(String s) {
if (s.length() == 0) return null;
int maxLength = 1;
String longestPalindrome = s.substring(0, 1);
for (int i = 0; i < s.length(); i++) {
String temp = helper(s, i, i);
if (temp.length() > longestPalindrome.length()) {
longestPalindrome = temp;
}
}
for (int i = 0; i < s.length(); i++) {
String temp = helper(s, i, i + 1);
if (temp.length() > longestPalindrome.length()) {
longestPalindrome = temp;
}
}
return longestPalindrome;
}
private String helper(String s, int begin, int end) {
while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
begin--;
end++;
}
//注意substring的用法，"babad"的substring(0,2)是"ba"，所以这里end不用-1
return s.substring(begin+1, end);
}
}
第二种做法DP，思维难度也不大，状态转移方程：
if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
但是做起来花了很多时间，首先要知道，这里只需要管上三角矩阵的值，因为j>=i的。我甚至连上三角矩阵的判断方法都想不明白。。思维迟钝。有点失望。其次，i要从后往前扫，否则会出现一种情况，aaaa，从0到4的过程中要用到从2到3，如果i从0开始，内层的就还没有检查过。
DP的复杂度也是O(n*n)。
好fin，这题搞了三小时，我真觉得不可思议，就坐在这电脑前3小时。。看这dp。。第一种方法做出来之后注意力不集中了。
