输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

输入: "cbbd"
输出: "bb"

解析:动态规划三步骤。1定义数组，dp[i]j为i到j是否是回文子符串。2初始化，dp[i][i]都是True，默认都是True。3递推公式，dp[i][j]=(charAt(i)==charAt(j))&&dp[i+1][j-1]。终点是dp[0][n-1]。所以从右下角开始。

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String ans = "";
        boolean[][] dp = new boolean[n+1][n+1];
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){//acda,不光需要a==a,还要dp[i+1][j-1]。如果j-i<2说明如aa形式，则不需要这步。
                dp[i][j]=(s.charAt(i)==s.charAt(j)&&(j-i<2||dp[i+1][j-1]));
                //如果i~j是回文的，且长度大于0，则更新。最后得到新的字符串
                if(dp[i][j]&&j-i>=0){
                    ans = s.substring(i,j+1);//substring函数的特性
                }
            }
        }
        return ans;

    }
}