动态规划：LC5.最长回文子串（二维）

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

思路：

1.暴力破解：

遍历出所有的回文子串，找出最大的一个返回即可。

两次for循环遍历数组+判断回文==时间复杂度为O(n^3)。

2.动态规划：

状态数组：dp[i][j]—s[i..j]是否为回文串

转移方程：
1.[i+1][j-1]的个数<2–里面只有1/0个字符，一定是回文
2.个数大于2–就判断dp[i+1][j-1]的值

初始值：dp[i][i]=true

参考题解：5.最长回文子串

代码：

1.暴力

class Solution {
    public String longestPalindrome(String s) {
        int len=s.length();
        if(len<2){
            return s;
        }
        //max是回文子串的长度，begin是子串起始点
        int max=1;
        int begin=0;
        //转为字符数组
        char[] c=s.toCharArray();
        //循环判断子串
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if(j-i+1>max && isPa(c,i,j)){ //如果长度小于max就不必记了
                    //定义新的最长子串
                    max=j-i+1;
                    begin=i;
                }
            }
        }
        return s.substring(begin,begin+max);
    }
    //判断是否为回文串
    public boolean isPa(char[] c,int left,int right){
        while(left<right){
            if(c[left]!=c[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

class Solution {
    public String longestPalindrome(String s) {
        //状态数组：dp[i][j]--s[i..j]是否是回文子串
        //方程：dp[i][j]=dp[i+1][j-1]
        //初始值：dp[i][i]=true;
        int len=s.length();
        if(len<2) return s;
        int max=1;
        int begin=0;
        char[] c=s.toCharArray();

        boolean[][] dp=new boolean[len][len];
        //初始化dp
        for(int i=0;i<len;i++){
            dp[i][i]=true;
        }
        //动态转移,只填表格的右上角
        for(int j=1;j<len;j++){
            for(int i=0;i<j;i++){
                if(c[i]!=c[j]){
                    dp[i][j]=false;
                }else{
                    //头尾相同，那就判断里面是否是回文
                    //1.如果里面只有1/0个字符，那么肯定是回文
                    //2.如果里面有多个字符，那么就要进行状态转移，判断dp[i+1][j-1]了
                    if(j-i<3){ //第一种情况
                        dp[i][j]=true;
                    }else{
                        dp[i][j]=dp[i+1][j-1];
                    }
                }
                 //此时已经判断出dp[i][j]了，所以如果为true且长度大于上一次的，那么就可以记下新的最长回文串了
                 if(dp[i][j]==true && j-i+1>max){
                     max=j-i+1;
                     begin=i;
                 }
            }
        }
        return s.substring(begin,begin+max);
    }
}