image.png
    解题思路：由于题目要求的是最长的回文子串，这需要我们去构建子串，但是基于暴力法的搜索时间复杂度太高
    O(n3)。因此利用动态规划降低这一搜索时间。
    同516题，回文类型的状态方程的定义类似，即 dp[i][j]表示s[i, ..., j]是否为回文子串。
    状态转移方程（子串长度>=3），有如下两种情况：

    • case1：s[i]==s[j]，有dp[i][j]=dp[i+1][j-1]
    • case2：s[i]!=s[j]，有dp[i][j]=false

    考虑初始化情况，当子串长度为1时，有dp[i][i]=true。同时我们也考虑到上面的状态转移方程中要求子串长度>=3，那么当子串长度为2时，我们需要单独处理，即j - i < 3 && s[i]==s[j]时，dp[i][j]=true，否则为fasle。
    在上述的基础上，我们仍然要进行子串的枚举（只不过我们利用了DP减少了判断的次数）。
    我们在第一维上枚举子串长度L，在第二维上枚举子串左侧起点i，根据这两个条件，我们可以得到子串最右侧的下标j=L+i-1。然后在此基础上判断s[i]与s[j]的情况。
    每当我们枚举了一种子串可能，如果当前子串为回文子串，那么计算其长度j-i+1，与历史最长长度比较，如果更大，则需要更新历史最长长度maxLen 和 子串左侧起点下标 start。

    • 时间复杂度：O(n * n)
    • 空间复杂度：O(n * n)
      1. class Solution {
      2.   public String longestPalindrome(String s) {
      3.       int n = s.length();
      4.       if(n < 2){
      5.           return s;
      6.       }
      7.       Boolean[][] dp = new Boolean[n][n];
      8.       //dp[i][j]表示 s[i,..,j]是否为回文子串
      9.       int maxLen = 1;
      10.       int start = 0;
      11.       for(int L = 2; L <= n; L++){
      12.           for(int i = 0; i < n; i++){
      13.               dp[i][i] = true;
      14.               int j = L + i - 1;
      15.               if(j >= n){
      16.                   break;
      17.               }
      18.               if(s.charAt(i) != s.charAt(j)){
      19.                   dp[i][j] = false;
      20.               }else{
      21.                   if(j - i < 3){
      22.                       dp[i][j] = true;
      23.                   }else{
      24.                       dp[i][j] = dp[i+1][j-1];
      25.                   }
      26.               }
      27.               if(dp[i][j] && j - i + 1 > maxLen){
      28.                   start = i;
      29.                   maxLen = j - i + 1;
      30.               }
      31.           }
      32.       }
      33.       return s.substring(start, start + maxLen);
      34.   }
      35. }