516.最长回文子序列

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

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

示例 1：

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

示例 2：

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

Solution

线性dp：一般是在前缀/后缀上转移

区间dp：从小区间转移都大区间

可以用选or不选的思路，从两侧内缩小问题规模

image-20240521171439827

递归边界：$dfs(i,i)=1,dfs(i+1,i)=0$

因为dp[i]是从dp[i+1]而来的，所以i要倒序枚举，而dp[i][j]从dp[i][j-1]转移而来，所以j要正序枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    // 主方法，计算给定字符串的最长回文子序列的长度
    public int longestPalindromeSubseq(String s) {
        int n = s.length(); // 获取字符串的长度
    
        // 初始化二维数组 dp，大小为 n x n
        int[][] dp = new int[n][n];

        // 从字符串的末尾开始遍历
        for (int i = n - 1; i > -1; i--) {
            dp[i][i] = 1; // 单个字符的最长回文子序列长度为 1

            // 遍历当前字符之后的字符
            for (int j = i + 1; j < n; j++) {
                
                // 如果字符 i 和字符 j 相等
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2; // 取 dp[i+1][j-1] 的值加上 2
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); // 否则取 dp[i+1][j] 和 dp[i][j-1] 中的较大值
                }
            }
        }

        // 返回整个字符串的最长回文子序列长度
        return dp[0][n - 1];
    }
}