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

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

思路：

判断s[i..j]是否是回文字符串，依赖于s[i+1...j-1]，这种一个问题的结果依赖于另个子集问题的结果，自然必须想到是动态规划了（上一次计算的结果，可以被下一次计算使用到，减少不必要的重复计算）。

java代码

 /**
     * 题目3：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
     * e.g.: 1. 输入: "babad" 输出: "bab"
     * 2. 输入: "cbbd"  输出: "bb"
     * 此解法还是效率太低，看官方解法前再优化优化
     *
     * @param s
     * @return
     */
    private static String solution04(String s) {
        char[] input = s.toCharArray();
        int length = input.length;
        int[][] dp = new int[length][length];
        int max = 0, ri = 0;
        for (int i = 0; i < length; i++) {
            for (int j = length - 1; j >= i; j--) {
                // 后面优化加进去的
                if (max > j - i + 1) {
                    continue;
                }
                if (1 == isAlindrome(input, dp, i, j)) {
                    if (j - i + 1 > max) {
                        max = j - i + 1;
                        ri = i;
                    }
                }
            }
        }

        return String.valueOf(input, ri, max);
    }

    /**
     * 输入要求 end >= start
     * dp[input.length][input.length]
     *
     * @param input
     * @param dp
     * @param start
     * @param end
     * @return int
     */
    private static int isAlindrome(char[] input, int[][] dp, int start, int end) {
        int length = input.length;
        if (start > end || start < -1 || end >= length) {
            return -1;
        }
        if (0 != dp[start][end]) {
            return dp[start][end];
        }
        if (start == end) {
            return 1;
        } else if (1 == end - start || 2 == end - start) {
            if (input[start] == input[end]) {
                return 1;
            } else {
                return -1;
            }
        } else {
            if (isAlindrome(input, dp, start + 1, end - 1) == 1) {
                if (input[start] == input[end]) {
                    return 1;
                } else {
                    return -1;
                }
            } else {
                return -1;
            }
        }

    }

算法时间复杂度：emmm....应该是要大于O(n^2)，这个不太会分析了...（囧）

已经看到这里了，帮忙点个喜欢❤️呗，谢谢啦！！