动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
dp算法有两个要点，1是状态转移方程，2是中间结果的记录。
详细解释

q5_最长回文子串

优秀题解

思路1

暴力求解，遍历所有的子串，然后依次判断是不是回文，找到最长的回文。
复杂程度太高，效率极差，代码就不贴了。

思路2

动态规划
代码

public String longestPalindrome2(String s) {
        int len = s.length();
        if (len <= 1) {
            return s;
        }

        //pass[i][j] 表示s的子串 [i,j]是否是回文
        //状态转移方程 pass[i][j]= s[i]==s[j] && pass[i+1][j-1]
        boolean[][] pass = new boolean[len][len];
        char[] chars = s.toCharArray();
        int start = 0;
        int maxLen = 1;
        for (int i = 0; i < len; i++) {
            pass[i][i] = true;
        }

        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (chars[i] != chars[j]) {
                    pass[i][j] = false;
                } else {
                    if (j - i <= 2) {
                        pass[i][j] = true;
                    } else {
                        //外层循环是j++，所以在此之前，一定已经给pass[0到j][j-1]赋值了
                        pass[i][j] = pass[i + 1][j - 1];
                    }
                }

                if (pass[i][j] && j - i + 1 > maxLen) {
                    start = i;
                    maxLen = j - i + 1;
                }
            }
        }
        return s.substring(start, start + maxLen);
    }

思路3

中心扩散
代码

    public String longestPalindrome3(String s) {
        if (s.length() <= 1) {
            return s;
        }
        String ans = "";
        for (int i = 0; i < s.length() - 1; i++) {
            ans = maxStr(ans, spread(s, i, false));
            ans = maxStr(ans, spread(s, i, true));
        }
        return ans;

    }

    private String maxStr(String s1, String s2) {
        if (s1.length() >= s2.length()) {
            return s1;
        }
        return s2;
    }

    private String spread(String s, int center, boolean even) {
        int left = center;
        int right = center;
        if (even) {
            right = center + 1;
        }
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            } else {
                break;
            }
        }
        return s.substring(left + 1, right);
    }

实际执行结果，中心扩散优于动态规划

思路4

封神的马拉车算法，思路2和3，复杂度都是O(n²)，马拉车可以把复杂度降到O(n)。
马拉车具体怎么拉？
代码

    public String longestPalindrome4(String s) {
        char space = '#';
        char header = '^';
        char tail = '$';
        StringBuilder sb = new StringBuilder();
        sb.append(header).append(space);
        int len = s.length();
        for (int i = 0; i < len; i++) {
            sb.append(s.charAt(i)).append(space);
        }
        sb.append(tail);
        String newS = sb.toString();

        int p[] = new int[newS.length()];
        int left, right, value;
        for (int i = 1; i < newS.length() - 1; i++) {
            left = i - 1;
            right = i + 1;
            value = 0;
            while (newS.charAt(left) != tail && newS.charAt(right) != tail
                    && newS.charAt(left) == newS.charAt(right)) {
                left--;
                right++;
                value++;
            }
            p[i - 1] = value;
        }

        int maxLen = 0;
        int start = 0;
        for (int i = 0; i < p.length; i++) {
            if (p[i] >= maxLen) {
                start = i;
                maxLen = p[i];
            }
        }
        start = (start - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }