暴力递归到动态规划 07（516. 最长回文子序列）

516.最长回文子序列

力扣题目链接

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1:
输入: “bbbab”
输出: 4
一个可能的最长回文子序列为 “bbbb”。

示例 2:
输入:“cbbd”
输出: 2
一个可能的最长回文子序列为 “bb”。

提示：

• 1 <= s.length <= 1000
• s 只包含小写英文字母

暴力递归

左右开始比较，如果左右是同一个位置，那一定是回文序列，返回1，如果左右相邻了，如果左右相等，则返回2 ，因为两个都是回文子序列的一员；否则返回1，两个只有1个可以作为回文子序列中的一员。
其他情况：

不以 L 开头，不以 R 结尾
以 L 开头，不以 R 结尾
不以 L 开头，以 R 结尾
以 L 开头，以 R 结尾 （这个要比较一下这个情况存在不存在，存在直接结果+2，两个都是结果的一员）
取四个中的最大值

    public int longestPalindromeSubseq(String s) {
    
        return process(s.toCharArray(), 0, s.length() - 1);
    }

    public int process(char[] s, int L, int R) {
    
        if (L == R) {
    
            return 1;
        } else if (L + 1 == R) {
    
            //如果只有两位 0 和 1 位
            return s[L] == s[R] ? 2 : 1;
        } else {
    
            //其他情况
            //以不以L开头 不以R结尾
            int NLNR = process(s, L + 1, R - 1);
            //以L开头，不以R结尾
            int LNR = process(s, L, R - 1);
            //不以L开头，以R结尾
            int NLR = process(s, L + 1, R);
            //以L开头，以R结尾
            int LR = s[L] == s[R] ? 2 + process(s, L + 1, R - 1) : 0;
            return Math.max(Math.max(NLNR, LNR), Math.max(NLR, LR));
        }
    }

动态规划

先把对角线和对角线上面的线处理了
对角线上自己和自己肯定是回文的，值为1
后一个如果和前一个相等，则两个都是回文的一员，返回2，否则其中一个都是回文的一员，返回1。
从下往上，从左往右计算，此时 j 至少是 i + 2 了。

    public int longestPalindromeSubseq2(String s) {
    
        int n = s.length();
        char[] chars = s.toCharArray();
        int[][] dp = new int[n][n];
        dp[n - 1][n - 1] = 1;
        for (int i = 0; i < n - 1; i++) {
    
            //当为主对角线上元素时，一定和当前相等，即为1
            dp[i][i] = 1;
            //主对角线上一条线
            dp[i][i + 1] = chars[i] == chars[i + 1] ? 2 : 1;
        }
        for (int i = n - 3; i >= 0; i--) {
    
            for (int j = i + 2; j < n; j++) {
    
                //其他情况
                //以不以L开头 不以R结尾
                int NLNR = dp[i + 1][j - 1];
                //以L开头，不以R结尾
                int LNR = dp[i][j - 1];
                //不以L开头，以R结尾
                int NLR = dp[i + 1][j];
                //以L开头，以R结尾
                int LR = chars[i] == chars[j] ? 2 + dp[i + 1][j - 1] : 0;
                dp[i][j] = Math.max(Math.max(NLNR, LNR), Math.max(NLR, LR));
            }
        }

        return dp[0][n - 1];
    }