leetcode 516. 最长回文子序列(JAVA)题解

题目描述：

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

子序列定义为：不改变字符相对顺序的情况下，从字符串中删除某些字符或者不删除的情况。

回文定义为：正读和反读都一样的字符串。

示例 1：

输入：s = "bbbab"

输出：4

解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"

输出：2

解释：一个可能的最长回文子序列为 "bb" 。

提示：

1 <= s.length <= 1000

s 只包含小写英文字母

解法：

动态规划，使用二维数组 dp 来记录子问题的解。其中 dp[i][j] 表示字符串 s 从 i 到 j 的子串的最长回文子序列的长度。

状态转移方程为：

• 如果 s[i] == s[j] 且 i 和 j 的下标差值不大于 1（即 i 和 j 是相邻的），那么 dp[i][j] = dp[i+1][j-1] + 2。
• 如果 s[i] != s[j] 或者 i 和 j 的下标差值大于 1，那么 dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

初始化：

• 对角线上的元素都初始化为 0，因为 dp[i][i] 总是 1（自身是回文子序列）。
• 其他位置初始化为 max(0, j - i + 1 - 2)，即 j - i + 1 和 0 中的较大值，这是因为如果 i 和 j 之间没有公共字符，那么最长回文子序列长度至少为 j - i + 1。

时间复杂度：O(n^2)

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
 
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
 
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
 
        return dp[0][n - 1];
    }
}