5. 最长回文子串动态规划java版

题目来自：
https://leetcode-cn.com/problems/longest-palindromic-substring/
这道回文题对我理解动态规划起到了很大的帮助，值得一做，虽然这道题动态规划的时间复杂度是O（N的平方）显然不是最优解，但是用来理解动态规划我觉得很合适。

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：

输入: “cbbd”
输出: “bb”

思路：
何为回文字符串：从前读和从后读的结果是一样的，举例：“aba”，“ccbbcc”。
注意：单个字符，如“a”也是回文字符串，还有“bb”这种连续的也是。

动态规划解决需要大问题转换成小问题，因此可以将求n…m是否为回文字符串，缩小成当n=m时n+1…m-1是否为回文串。（之前我一直以为动态只是将字符串s缩小成s-1考虑，反倒是偏离了动态的根本：大问题化小问题）
所以可以设置状态db[n][m] 值为1表示为回文，0为否。
转换公式：
db[n][m]=db[n+1][m-1],s[n]=s[m] else 0 ,s[n]!=s[m]

注意:定义初始化状态的时候先定义单个情况和两个情况的。
为什么？
因为字符串要考虑奇数和偶数，
如果是奇数:d[n+1][m-1]最后必定会缩小到单个字符组成的字符串
如果是偶数:d[n+1][m-1]最后必定缩小到两个字符组成的字符串
代码：

class Solution {
    public String longestPalindrome(String s) {
         if(\"\".equals(s)){
            return \"\";
        }
        int len = s.length();
        if(len==1){
            return s;
        }
        int sLength=1;
        int start = 0;
        int[][] db = new int[len][len];
        for(int i=0;i<len;i++){//定义初始化状态
            db[i][i]=1;
            if(i<len-1&&s.charAt(i)==s.charAt(i+1)){
                db[i][i+1] = 1;
                sLength=2;
                start = i;
            }
        }
        for(int i=3;i<=len;i++){
            for(int j=0;j+i-1<len;j++){
                int end = j+i-1;
                if(s.charAt(j)==s.charAt(end)){
                    db[j][end]=db[j+1][end-1];
                   if(db[j][end]==1){
                       start=j;
                       sLength = i;
                   }
                }
            }
        }
       return s.substring(start,start+sLength);
    }
}