最长回文子序列

题目描述
给定一个字符串 s，找出其中最长的回文子序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符（也可以不删除）得到的新序列。注意：回文是正着读和反着读都一样的字符串。

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

解题过程

1. 问题分析
   最长回文子序列（LPS）问题要求从原字符串中按顺序选取字符构成最长的回文串。关键点在于：子序列不要求连续，但顺序必须与原字符串一致。
   思路：将问题转化为求原字符串 s 与其反转字符串 s' 的最长公共子序列（LCS）。因为回文串正反读相同，LPS 即为 s 与 s' 的 LCS。

2. 定义状态
   设 dp[i][j] 表示字符串 s 的前 i 个字符与反转字符串 s' 的前 j 个字符的 LCS 长度。
   注意：实际编码中，我们通常直接比较 s 的两个区间，避免显式构造 s'。更优的定义是：
   dp[i][j] 表示 s 从索引 i 到 j 的子串中的最长回文子序列长度（0 ≤ i ≤ j < n）。

3. 状态转移方程

   • 如果 s[i] == s[j]：
     当前两个字符相等，它们可以作为回文子序列的两端，因此长度加 2：
     dp[i][j] = dp[i+1][j-1] + 2（当 i < j）。
   • 如果 s[i] != s[j]：
     当前两端字符不同，它们不能同时作为回文子序列的两端，因此分别考虑去掉一端后的子问题：
     dp[i][j] = max(dp[i+1][j], dp[i][j-1])。
   • 边界情况：
     • 当 i == j：单个字符是长度为 1 的回文，dp[i][j] = 1。
     • 当 i > j：无效区间，dp[i][j] = 0。

4. 填表顺序
   由于 dp[i][j] 依赖于左下方 dp[i+1][j-1]、正下方 dp[i+1][j] 和正左方 dp[i][j-1]，需要从右下角向左上角填表，即：

   • 外层循环 i 从 n-1 到 0（递减）。
   • 内层循环 j 从 i 到 n-1（递增），确保 i ≤ j。

5. 示例推导（s = "bbbab"）

   • 初始化：所有 i > j 的值为 0，对角线 i=j 的值为 1。
   • 填表过程（只填 i ≤ j 部分）：

     i\j | 0(b) 1(b) 2(b) 3(a) 4(b)
     ----|----------------------
     0   | 1    2    3    3    4
     1   |      1    2    2    3
     2   |           1    1    3
     3   |                1    1
     4   |                     1
     

     最终结果：dp[0][4] = 4。

6. 复杂度分析

   • 时间复杂度：O(n²)，需要填充 n²/2 个状态。
   • 空间复杂度：O(n²)，可优化至 O(n)（仅保留上一行）。

关键点

• 将 LPS 转化为 LCS 是核心思路，但直接区间 DP 更直观。
• 注意循环方向，确保子问题先被计算。
• 边界处理（单个字符、空区间）是基础。