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

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

示例 1：

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

示例 2：

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

提示：

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

注意是子序列不是子串。

动态规划-函数递归+备忘录

memo[i][j] 表示字符串 s 的子串 s[i...j] 的最长回文子序列长度。dfs(int i, int j)计算 s[i..j] 中最长回文子序列的长度， 结束条件：如果 i 超过 j，表示空串，返回 0，如果 i 等于 j，表示只有一个字符，返回 1。查备忘录， 如果 s[i] 等于 s[j]，则递归计算dp(i+1, j-1)，如果不相等，则递归计算dfs(i + 1, j), dfs(i, j - 1)。

class Solution {
    // 字符串的字符数组
    private char[] s;
    // 备忘录数组，memo[i][j] 表示 s[i..j] 中最长回文子序列的长度
    private int[][] memo;

    public int longestPalindromeSubseq(String S) {
        s = S.toCharArray(); // 将字符串转换为字符数组
        int n = s.length;
        
        // 初始化备忘录数组，-1 表示尚未计算过
        memo = new int[n][n];
        for (int i = 0; i < n; ++i) Arrays.fill(memo[i], -1);
        
        // 计算 s[0..n-1] 中最长回文子序列的长度
        return dfs(0, n - 1);
    }

    // 递归函数，计算 s[i..j] 中最长回文子序列的长度
    private int dfs(int i, int j) {
        // 如果 i 超过 j，表示空串，返回 0。只有偶数长度才会走到这里。
        if (i > j) return 0;
        // 如果 i 等于 j，表示只有一个字符，返回 1。只有奇数长度才会走到这里。
        if (i == j) return 1;
        // 如果 memo[i][j] 不为 -1，表示已经计算过，直接返回结果
        if (memo[i][j] != -1) return memo[i][j];
        
        // 如果 s[i] 等于 s[j]，则可以将这两个字符包含在回文子序列中
        if (s[i] == s[j]) return memo[i][j] = dfs(i + 1, j - 1) + 2;
        // 如果 s[i] 不等于 s[j]，则分别计算不包含 s[i] 或 s[j] 的情况。
        // 重点。如果是子串，则为0，因为不连续了。
        return memo[i][j] = Math.max(dfs(i + 1, j), dfs(i, j - 1));
    }
}

• 时间复杂度： $O\left(n^2\right)$ ，其中 $n$ 为 $s$ 的长度。动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的转移个数。本题中状态个数等于 $O\left(n^2\right)$（i有n个，j有n个，所以有n^2种组合），而单个状态的转移个数为 $O(1)$ ，因此时间复杂度为 $O\left(n^2\right)$ 。
• 空间复杂度： $O\left(n^2\right)$ 。

动态规划-数组递推

f[i][j] 表示 s[i..j] 中最长回文子序列的长度。倒序遍历 i，正序遍历 j。

遍历范围为矩阵的对角线及其上方。

class Solution {
    public int longestPalindromeSubseq(String S) {
        // 将字符串转换为字符数组，方便访问
        char[] s = S.toCharArray();
        // 获取字符串的长度
        int n = s.length;
        // 定义二维数组 f，f[i][j] 表示 s[i..j] 中最长回文子序列的长度
        int[][] f = new int[n][n];
        
        // 从字符串末尾开始遍历，i倒序遍历
        for (int i = n - 1; i >= 0; --i) {
            // 重点，单独处理j=i。
            f[i][i] = 1;
            // 遍历 i 后面的字符，j正序遍历
            for (int j = i + 1; j < n; ++j)
                // 如果 s[i] == s[j]，则 f[i][j] 可以通过 f[i + 1][j - 1] + 2 得到
                // 否则 f[i][j] 等于 f[i + 1][j] 和 f[i][j - 1] 中的较大值
                // 在 Java 中，二维数组的元素默认初始化为 0。具体来说，f[i][j] 是一个整型二维数组，未明确赋值的位置都会被默认初始化为 0。
                // 因此，当 f[i+1][i] 不符合规范（即 i+1 > i），程序试图访问的是默认初始化的值 0。
                f[i][j] = s[i] == s[j] ? f[i + 1][j - 1] + 2 : Math.max(f[i + 1][j], f[i][j - 1]);
        }
        
        // 返回整个字符串的最长回文子序列长度
        return f[0][n - 1];
    }
}

• 时间复杂度： $O\left(n^2\right)$ ，其中 $n$ 为 $s$ 的长度。动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的转移个数。 本题中状态个数等于 $O\left(n^2\right)$ ，而单个状态的转移个数为 $O(1)$ ，因此时间复杂度为 $O\left(n^2\right)$ 。
• 空间复杂度： $O\left(n^2\right)$。

滚动更新

在第一层循环中定义pre变量为0，在内层循环中先保存更新前的f[j]，再利用pre更新f[j]，再把更新前的f[j]赋给pre

class Solution {
    public int longestPalindromeSubseq(String S) {
        // 将输入字符串转换为字符数组，方便逐个字符访问
        char[] s = S.toCharArray();
        // 获取字符串的长度
        int n = s.length;
        // 定义一维数组 f，用于保存当前状态的最长回文子序列长度
        int[] f = new int[n];
        
        // 从字符串的末尾开始遍历
        for (int i = n - 1; i >= 0; --i) {
            // pre 变量保存 f[i] 的值。滚动更新的特点就是更新前要保存原值。
            int pre = f[i];
            // 单个字符的回文子序列长度为1
            f[i] = 1;
            // 遍历当前字符 i 之后的所有字符 j
            for (int j = i + 1; j < n; ++j) {
                // 保存 f[i+1][j] 的值，用于后续更新 pre。这是更新前的f[j]，所以是上一次i循环中的f[j]，即f[i+1][j]
                int tmp = f[j];
                
                // 如果 s[i] == s[j]，则 f[i][j] = f[i+1][j-1] + 2
                // 否则 f[i][j] = max(f[i+1][j], f[i][j-1])
                // 这是更新后的f[j]，即f[i][j]。
                f[j] = s[i] == s[j] ? pre + 2 : Math.max(f[j], f[j - 1]);
                
                // 更新 pre 为当前的 f[i+1][j]
                pre = tmp;
            }
        }
        
        // 返回整个字符串的最长回文子序列长度
        return f[n - 1];
    }
}

• 时间复杂度： $O\left(n^2\right)$ ，其中 $n$ 为 $s$ 的长度。
• 空间复杂度： $O(n)$ 。