class Solution {
    public int longestPalindromeSubseq(String s) {
        //使用的是动态规划二维数组 i是指起始值,j是指终止位置,记录当前最长回文数
        int[][] arr = new int[s.length()][s.length()];
        //对该二维数组初始化
        for (int i = 0; i < s.length(); i++) {
            arr[i][i] = 1;
        }
        //使用动态规划
        //先用的是i值后面的数,i要从大到小遍历
        for (int i = arr.length-1; i >= 0; i--) {
            //先用的是j值前面的数,j要从小到大遍历
            for (int j = i+1; j < arr[0].length; j++) {
                //起始值和终止值相等的情况下,就是前面的回文数加2就是现在的长度
                if(s.charAt(i)==s.charAt(j)){
                    arr[i][j] = arr[i+1][j-1]+2;
                //起始值和终止值不相等的情况下,就是比i+1到j或者i到j-1的回文数长度大就选那个
                }else {
                    arr[i][j] = Math.max(arr[i+1][j],arr[i][j-1]);
                }
            }
        }
        //最后返回所有数的最长回文数,就是起始值为0,最终值为s.length()-1的下标的最长回文数
        return arr[0][s.length()-1];
    }
}