最长回文子序列 递归与动态规划

public static int longestPalindromeSubseq(String s) {

        char[] chars = s.toCharArray();

        int n = chars.length;

        int[][] dp = new int[n][n];

        //先约束边界 dp[L][R]

        dp[n-1][n-1] = 1;

        //约束的下边界，那就从上边界开始，直至下边界的前一位

        //此处初始化对角线以及倒数第二的对角线，在上面的分析中已经提到过范围约束，不可能存在对角线左下方的情况

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

            dp[i][i]=1;

            dp[i][i+1] = chars[i]==chars[i+1]?2:1;

        }

        //dp矩阵需画图

        for (int i = 0; i < n - 3; i++) {

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

                //将原本的递归，转换为动态规划

// int res1 = process(chars,i+1,j-1);

                int res1 = dp[i+1][j-1];

// int res2 = process(chars,i,j-1);

                int res2 = dp[i][j-1];

// int res3 = process(chars,i+1,j);

                int res3 = dp[i+1][j];

// int res4 = chars[i]==chars[j]?2+res1:0;

                int res4 = chars[i]==chars[j]?2+res1:0;

                //当前要求的值是dp[i][j]

                dp[i][j] = Math.max(Math.max(res1,res4),Math.max(res2,res3));

            }

        }

        return dp[0][n-1];

    }