3.最长回文子串

![XEJ6QC0TA6NSQ}}3H%S0I.png
题解：
对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。因此写出动态规划方程：

其中，其他情况包括：1.其子串不为回文串 2. 其i>j,不符合字符串规范
从而，状态转移方程为

从而边界条件为：

java代码：

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        for (int l = 0; l < n; ++l) {
            for (int i = 0; i + l < n; ++i) {
                int j = i + l;
                if (l == 0) {
                    dp[i][j] = true;
                } else if (l == 1) {
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                } else {
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                }
                if (dp[i][j] && l + 1 > ans.length()) {
                    ans = s.substring(i, i + l + 1);
                }
            }
        }
        return ans;
    }
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

附上一个暴力破解的算法：

class Solution {
        public String longestPalindrome(String s) {
        String max = s.substring(0,1);
        for (int i = 0; i < s.length();i++){
            //比它短的就不用判断了
            for (int j = i+max.length();j < s.length() ; j++){
                String temp = s.substring(i,j+1);
                boolean flag = true;
                //判定temp是否回文
                for (int k = 0;k<=temp.length()/2-1;k++){
                    if (temp.charAt(k) != temp.charAt(temp.length()-k-1)){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    max = temp;
                }
            }
        }
        return max;
    }
}