最长回文子串

问题描述：

给你一个字符串 s，找到 s 中最长的回文子串。

示例1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例2：

输入：s = "cbbd"
输出："bb"

示例3：

输入：s = "a"
输出："a"

示例4：

输入：s = "ac"
输出："a"

思路：

• 既然是动态规划专场，这里就只介绍动态规划的思路。

回文串有先天性的转移特性，如果一个字符串是回文串，那么它去掉首位的子串也是一个回文串，当然需要这个回文串长度严格大于2才成立。

这样我们就可以用来定义回文串的转移方程。如果 i 和 j 位置上的字符相同的话，那么[ i j ]是否为回文串就取决于[ i + 1 j + 1]是否是回文串。这样我们就找到了转移方程。

当然还需要一些细节需要处理，比如边界和初始值。

易知，单个字符是回文串，所以长度为1的子串一定是回文串。至于边界，我们遍历到从0到n-1的所有值即可。

当 i 和 j 对应的字符相等的时候，如果 i 和 j 之间没有字符，或者只有一个字符，那么直接判定为回文串，也就是当j-i<3的时候

Java代码

/**
    * @Description: 动态规划专项第一题 力扣第五题 中等
    * @return: 返回结果
    * @Author: Mr.Gao
    * @Date: 2021/7/31
    */
    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        if(n<2){
            return s;
        }

        int start=0;
        int maxLength=1;

        //dp[i][j]表示chars[i]~char[j]是否为回文串
        boolean[][] dp = new boolean[n][n];
        for(int i=0;i<n;i++){
            dp[i][i] = true;
        }
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (chars[i] != chars[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && j - i + 1 > maxLength) {
                    maxLength = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substring(start,start+maxLength);
    }