leetcode 5最长回文字符串

这个题感觉不太好想，对于动态规划不太熟练，导致遇到这种可以拆分成子问题的题目想不到解法，并且感觉能用动态规划来解的题目，如果不用的话，真的很难解。

这个题是利用回文串的左右对称特性，想要dp[i][j]是一个回文串，dp[i + 1][j - 1]就要是个回文子串，同时s[i] == s[j], 在j - i >= 2的情况下，具体java解法如下：

class Solution {

    public String longestPalindrome(String s) {

        int n = s.length();

        String res = "";

        boolean[][] dp = new boolean[n][n];

        for (int i = n - 1; i >= 0; i--) {

            for (int j = i; j < n; j++) {

                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]);

                if (dp[i][j] && j - i + 1 > res.length()) {

                    res = s.substring(i, j + 1);

                }

            }

        }

        return res;

    }

}