5. 最长回文子串

这题使用dp，dp[i][j]=1代表字符串中以i下标开始，以j下标结尾的字符串是回文子串，

当dp[i][j] =dp[i + 1][j - 1],当s[i] == s[j]的时候，很明显，dp[i][i]一定为1，因为一个字符，一定是回文子串。

class Solution {

    public String longestPalindrome(String s) {

       //习惯把String转为char[]

        char[] ss = s.toCharArray();

       //当前的回文子串长度为1

        String ans = s.substring(0,1);

        int maxLength = 1;

        //初始化dp数组

        int[][] dp = new int[ss.length][ss.length];

        for(int i = 0; i < dp.length; i++) {

            for(int j = 0; j < dp[i].length; j++) {

                if(i == j) {

                    dp[i][j] = 1;

                }

            }

        }

        int n = ss.length;

        //动态规划过程，要先遍历列，再遍历行。因为dp[row][colunm]依赖于

        //dp[row + 1][colunm - 1]，所以要先遍历列，再遍历行

        for(int colunm = 1; colunm < n; colunm++) {

            for(int row = 0; row < colunm; row++) {

                if(ss[row] == ss[colunm]) {

                    if(colunm - row <= 2) {

                        dp[row][colunm] = 1;

                    }

                    else {

                        dp[row][colunm] = dp[row + 1][colunm - 1];

                    }

                }

                if(dp[row][colunm] == 1) {

                    if(colunm - row + 1 > maxLength) {

                        maxLength = Math.max(maxLength, colunm - row + 1);

                        ans = s.substring(row, colunm + 1);

                    }

                }

            

            }

        }

        return ans;

    }

}