题目

顺便说一下啊，现在的我进步很明显，这道题只用了两个小时就做出来了(哭)

题目解析

动态规划的思路，就是面对一个需要求的未知量，我们通过一个已知量，将它推算出来。

现在假如有一个a字符串，它一定是回文的。
如果是ac，那么它一定不是，因为新加上的这个‘c’导致了ac不再回文。
而如果我们已知的是abb，它的下一个是‘a’，那么它就又成了回文了。

很关键的一个点，就是我们对于一个已知是否回文的字符串，判断它新增了一个之后，还是不是回文的，并且如果新增了一个回文的导致回文的字符之后，我们的最长回文子串长度会变化，我们完成对整个输入字符串s的判断。

判断回文条件

有下面几点条件

1. 对于单个字符，它一定是回文的。
2. 对于间隔小于2的字符，只要它们相等，那么一定是回文的,例如aa，或者aaa,或者aba。因为这种情况，要么是两个或三个连续一样的，要么是两个一样的中间夹了一个不同的。
3. 两个位于i,j位置的字符，如果它们相等，并且从i+1到j-1的子串是回文的，那么从i到j的字串，一定是回文的。例如abssba，两侧的a相等，并且中间的字串是回文的，那么一定是回文的。并且长度是bssb的长度+2。

状态转移

对于前面回文条件的第一和第二种情况，都是可以直接判断的。
条件很简单
对于以i为起点，j为终点的字串，如果位于i的字符等于位于j的字符，并且j和i的差不超过2，那么就可以直到它是否回文。

对于条件3，对于如果j和i的差超过2，那么就可以通过i+1,j-1是否回文，推算出来。
现在用一个二维bool数组bp记录以i为起点，j为终点的字串，是否回文。

每当我们完成对一个字串的判断的时候，我们就将这个数组更新，老套路了。

下面上代码

代码实现

public String longestPalindrome(String s) {
        if ("".equals(s)) return s;
        boolean[][] dp = new boolean[s.length()][s.length()];
	//只要不是空字符串，至少为1
        int max = 1;
	//记录最终的最长字串的起点终点
        int start = 0, end = s.length() - 1;
	//以0，1为起点开始遍历。
        for (int i = 1; i < s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i - j <= 2) {
			//更新dp数组
                        dp[j][i] = true;
			//更新结果的起点终点
                        if (i - j + 1 > max) {
                            max = i - j + 1;
                            start = j;
                            end = i;
                        }
		     //遍历字符串顺序是从左往右，所以j+1和i-1一定是已知的
                    } else if (dp[j + 1][i - 1]) {
                        dp[j][i] = true;
                        if (max < i - j + 1) {
                            max = i - j + 1;
                            start = j;
                            end = i;
                        }
                    }
                }

            }
        }
        return max != 1 ? s.substring(start, end + 1) : String.valueOf(s.charAt(0));
    }

这个动态规划解法的空间复杂度其实还可以再优化，等我理解了再更新吧