最长回文子序列问题

题目描述
给定一个字符串 s，找出其最长回文子序列的长度。子序列不要求连续，但需保持相对顺序。例如，字符串 "bbbab" 的最长回文子序列是 "bbbb"，长度为 4。

解题思路
最长回文子序列问题适合用动态规划解决。核心思路是：将原问题转化为求原字符串与其反转字符串的最长公共子序列（LCS），因为回文正读反读相同。但这里我们直接基于原字符串设计动态规划状态转移。

步骤分解

1. 定义状态
   设 dp[i][j] 表示字符串 s 在区间 [i, j] 内的最长回文子序列的长度。

   • 目标：求 dp[0][n-1]（n 为字符串长度）。

2. 状态转移方程

   • 情况1：若 s[i] == s[j]，则这两个字符可以加入回文子序列，此时 dp[i][j] = dp[i+1][j-1] + 2。
   • 情况2：若 s[i] != s[j]，则这两个字符不能同时出现在回文子序列中，需分别舍弃一个字符，取最大值：
     dp[i][j] = max(dp[i+1][j], dp[i][j-1])。

3. 边界条件

   • 当 i == j 时，单个字符本身就是回文，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）。

示例详解
以 s = "bbbab" 为例：

1. 初始化

   • 对角线 dp[i][i] = 1（单个字符的回文长度为1）。

2. 填表过程（只展示部分关键步骤）：

   • 计算 dp[3][4]（子串 "ab"）：
     s[3]='a', s[4]='b'，不相等，dp[3][4] = max(dp[4][4], dp[3][3]) = max(1, 1) = 1。
   • 计算 dp[2][4]（子串 "bab"）：
     s[2]='b', s[4]='b' 相等，dp[2][4] = dp[3][3] + 2 = 1 + 2 = 3（对应 "bab"）。
   • 计算 dp[0][4]（整个字符串）：
     s[0]='b', s[4]='b' 相等，dp[0][4] = dp[1][3] + 2。
     需先计算 dp[1][3]（子串 "bba"）：
     • s[1]='b', s[3]='a' 不相等，dp[1][3] = max(dp[2][3], dp[1][2])。
     • dp[2][3]（"ba"）不相等，取 max(1,1)=1；dp[1][2]（"bb"）相等，值为 0+2=2。
     • 因此 dp[1][3] = max(1, 2) = 2。
       最终 dp[0][4] = 2 + 2 = 4。

3. 结果：dp[0][4] = 4。

代码实现（Python）

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n-1, -1, -1):  # 从后往前遍历i
        dp[i][i] = 1  # 单个字符
        for j in range(i+1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

复杂度分析

• 时间复杂度：O(n²)，需要填充 n×n 的 DP 表。
• 空间复杂度：O(n²)，可优化至 O(n)（只保留上一行数据）。