动态规划解最长回文子串

首先我们需要了解一下回文串的定义是什么？回文串就是从左往右读和从右往左读的结果是一样的，
例如aba、abcba、bbbb等等。

判断是不是回文串很容易，依次判断第一个字符和倒数第一个字符、第二个字符和倒数第二个字符…是否相等就行，还有其他方法都可以。
然后找最长回文子串就是把所有的子串列出来，每个判断是否是回文串，最后找出一个最长的，这是最暴力也是最耗时的方法。当然我们也可以优化一下，
从最长的子串开始判断，依次往短的子串开始找，这样找到的第一条回文子串就是最长的。

但是这两个方法始终不够巧妙，从回文串的对称性我们就可以找到一个规律，如果一个长度为n的回文串，那么它的第2个字符到n-1个字符也是回文串，
比如abcba，子串bcb也是回文串，然后c我们也可以认为是回文串，这样我们就可以用动态规划来解决这个问题了。

首先，我们肯定要从最短的子串开始判断，然后长的子串基于短的子串的结果上再判断短的子串前一个字符和后一个字符是否相等就行。
（1）对于长度为1的子串，我们认为都是回文串。
（2）对于长度为2的子串，两个字符相等就是回文串 str[i] == str[i+1]。
（3）对于长度大于2的子串，满足str[0] == str[n-1] && dp[1][n-2] == 1 就是回文串。

str数组就是字符串，dp[x][y] == 1 表示str数组从x坐标到y坐标的字符组成的字符串是回文串。

然后我们用代码实现：

class Solution {
public String longestPalindrome(String s) {
    char[] str = s.toCharArray();
    String result = "";
    char[][] dp = new char[str.length][str.length];
    for (int i = 1; i <= str.length; i++) {  //子串长度
        for (int u = 0; u + i <= str.length; u++) {  //u为子串起始位置
            if (i <= 2) {
                if (str[u] == str[u + i - 1]) {
                    dp[u][u + i - 1] = 1;
                    if (i>result.length()){
                        result = s.substring(u,u+i);
                    }
                }
            }else {
                if (dp[u+1][u+i-2]==1 && str[u] == str[u + i - 1]){
                    dp[u][u + i - 1] = 1;
                    if (i>result.length()){
                        result = s.substring(u,u+i);
                    }
                }
            }
        }
    }
    return result;
  }
}