首先，确定这个问题可以用DP来做。
-
求最值：这个问题求最长回文子串，满足
-
最优子结构（原问题的解可以通过求解子问题得到，并且子问题之间相互独立）。原问题是求解字符串s的最长回文子串，那我只需遍历所有以字符s[i]结尾的最长回文子串，然后找最大的即可（转换问题)。原问题以字符$s[i]$结尾的最长回文子串可以利用子问题以字符$s[i-1]$结尾的最长回文子串以及字符$s[i]$来求解。以字符$s[i-1]$结尾的最长回文子串与字符$s[i]$相互独立。
-
重叠子问题：要求$(s[0]...s[i])$的最长回文子串，必然要知道$(s[0]...s[i-1])$的最长回文子串，要求$(s[0]...s[i-1])$必然要先找到$(s[0]...s[i-2])$，所以存在重叠子问题
然后，按一般套路base case -> 状态 -> 选择 -> 确定dp函数或者dp数组定义
-
base case: 以$s[0]$结尾的最长回文子串是$s[0]$， 长度为1；
-
状态：以谁结尾
-
选择，其实和第四步耦合在一起
-
确定状态转移方程：
也就是已知$dp[n-1]$，如何求$dp[n]$？
比如$"****abbac"$，已知$dp[n-1] = 4$,即以$s[n-1]$结尾的最长回文子串为$"abba"$,如何判断以$s[n] = c$结尾的最长回文子串。
在这里，为了下面叙述的方便，不妨记$P(s[i])$为以s[i]字符结尾的最长回文子串，
$isPalindrome(a, b)$ 为判断字符串s[a...b]是否为回文子串的函数。那么首先看穷举如何来算，那必然是依次判断$isPalindrome(0, n)$， 如果不行，再$isPalindrome(1, n)$, ..., 一直到判断$isPalindrome(n-1, n)$。
显然由于$dp[n-1]$（即$P(s[n-1])$）的限制，我们无需从头开始搜索，只需包含$P(s[n-1])$再加上字符$s[n]$，看看这个子串是不是回文子串，最多呢再比以$s[n-1]$结尾的最长回文子串再往前一个，因为可能存在这种情况（cabbac)，然后依次往后搜索，只要找到一个，那必然是对s[n]而言最大的，因为我们是从大往小搜。
那么状态转移方程就可以写出来:
$dp[n] = max(PS("s[i-1]...s[n]"), PS("s[i]...s[n]"), ... , PS("s[n-1]s[n]"))$ $其中 P(s[n-1]) = "s[i]...s[n-1]"$ $PS("s[i]...s[j]")$ 表示字符串$"s[i]...s[j]"$的最长回文子串
最后框架套起来：
# base case
dp[0][...] = base case
for 状态1 in 所有取值:
for 状态2 in 所有取值:
...
dp[状态1][状态2][...] = 取最值（选择1， 选择2，...选择n）class Solution {
public String longestPalindrome(String s) {
int n = s.length();
int[] dp = new int[n];
int start = 0, maxLen = 1;
dp[0] = 1;
for (int i = 1; i < n; i++) {
int begin = Math.max(i-1 - dp[i-1], 0);
for (int j = begin; j <= i; j++)
if (isPalindrome(s, j, i)) {
dp[i] = i - j + 1; break;
}
if (maxLen < dp[i]) {
start = i - dp[i] + 1;
maxLen = dp[i];
}
}
return s.substring(start, start+maxLen);
}
public static boolean isPalindrome(String s, int start, int end) {
int left = start, right = end;
while (left <= right) {
if (s.charAt(left) != s.charAt(right))
return false;
left++;
right--;
}
return true;
}
}