LeetCode_146_LongestPalindromicSubsequence

1. question: 最长回文子序列（中等）

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-subsequence

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

1 <= s.length <= 1000
s 仅由小写英文字母组成

2. answers

这道题和回文子串还是有区别的。如果当前匹配字符不相等，显然不是回文子串，但是依然可以形成回文子序列，即回文子序列的长度就是前面字符所形成的回文子序列长度。定义数组dp[i][j]表示s[i:j]形成的最长回文子序列长度。显然递推公式如下所示：

1. s[i] == s[j],
   1. j - i > 1, dp[i][j] = dp[i+1][j-1] + 2
   2. j - i =1, dp[i][j] = 2【因为这是偶数个序列】
2. s[i] != s[j], 既然不相等，此时其实就是前面的最大长度，
   1. dp[i][j] = dp[i+1][j]
   2. dp[i][j] = dp[i][j-1]
   3. 为什么没有dp[i+1][j-1]呢？因为dp[i+1][j]时，显然经历了dp[i+1][j-1]才到达的，即已经包括了该情况
   4. 上面两者取最大即可。

注意，初始化以及遍历顺序。因为递推过程中，用到的是左下方的元素，所以需要自底向上，自左向右遍历。至于初始化，显然i==j时，dp[i][j]=1。要在遍历的过程中，保证j>=i。

代码如下所示：

public class Solution_0146 {

    public int longestPalindromeSubseq(String s) {

        int[][] dp = new int[s.length()][s.length()];

        // 初始化
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if(i == j) dp[i][j] = 1;
            }
        }

        for (int i = s.length() - 1 - 1; i >= 0; i--) {

            for (int j = i + 1; j < s.length(); j++) {

                if(s.charAt(i) == s.charAt(j)) {

                    // 注意，可能存在i+1=j的情况，此时，就相当于偶数子序列
                    if(j - i == 1) dp[i][j] = 2;
                    else dp[i][j] = dp[i+1][j-1] + 2;

                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }

        // 注意，因为遍历顺序是左下到右上，即最终应该是全部序列，dp[0][s.length()-1]
        return dp[0][s.length() - 1];
    }

    public static void main(String[] args) {
        System.out.println();

        Solution_0146 s0146 = new Solution_0146();

//        String s = "bbbab";
//        String s = "cbbd";
        String s = "c";

        System.out.println(s0146.longestPalindromeSubseq(s));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。