线性动态规划：最长回文子序列

题目描述
给定一个字符串s，找到其中最长的回文子序列的长度。子序列是指通过删除原字符串中的某些字符（也可以不删除）而不改变剩余字符的相对顺序形成的新字符串。注意：回文是指正着读和反着读都一样的字符串。

示例：
输入：s = "bbbab"
输出：4
解释：最长回文子序列是"bbbb"

输入：s = "cbbd"
输出：2
解释：最长回文子序列是"bb"

解题思路
这个问题可以用动态规划解决。关键思路是：如果一个字符串是回文，那么它的首尾字符相同，并且去掉首尾字符后的子串也是回文。

详细解题步骤

1. 定义状态

   • 定义dp[i][j]表示字符串s从索引i到索引j（包含两端）的子串中最长回文子序列的长度
   • 我们的目标是求dp[0][n-1]，其中n是字符串长度

2. 状态转移方程
   我们需要考虑三种情况：

   • 当i = j时：单个字符本身就是回文，长度为1
   • 当s[i] = s[j]时：首尾字符相同，那么最长回文子序列长度 = 内部子串的最长回文子序列长度 + 2
     • 即：dp[i][j] = dp[i+1][j-1] + 2
   • 当s[i] ≠ s[j]时：首尾字符不同，那么最长回文子序列要么在去掉首字符的子串中，要么在去掉尾字符的子串中
     • 即：dp[i][j] = max(dp[i+1][j], dp[i][j-1])

3. 初始化

   • 对角线上的值初始化为1：dp[i][i] = 1（单个字符的回文长度为1）
   • 其他位置可以初始化为0

4. 遍历顺序

   • 由于dp[i][j]依赖于dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]
   • 我们需要从右下角往左上角遍历，或者按子串长度从小到大遍历
   • 推荐按子串长度l从1到n遍历，对于每个长度l，遍历所有起始位置i

5. 算法实现

   def longestPalindromeSubseq(s: str) -> int:
       n = len(s)
       # 创建n×n的dp数组，初始化为0
       dp = [[0] * n for _ in range(n)]
   
       # 初始化：单个字符的回文长度为1
       for i in range(n):
           dp[i][i] = 1
   
       # 按子串长度从小到大遍历
       for l in range(2, n + 1):  # l表示当前子串长度
           for i in range(n - l + 1):  # i表示子串起始位置
               j = i + l - 1  # j表示子串结束位置
   
               if s[i] == s[j]:
                   if l == 2:
                       # 长度为2且两字符相同，回文长度为2
                       dp[i][j] = 2
                   else:
                       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]
   

6. 复杂度分析

   • 时间复杂度：O(n²)，需要填充n×n的dp表
   • 空间复杂度：O(n²)，用于存储dp表

示例演示
以s = "bbbab"为例：

• 初始化：所有dp[i][i] = 1
• 长度2："bb"→2，"bb"→2，"ba"→max(1,1)=1，"ab"→max(1,1)=1
• 长度3："bbb"→dp[1][1]+2=3，"bba"→max(2,2)=2，"bab"→dp[1][1]+2=3
• 长度4："bbba"→max(3,2)=3，"bbab"→max(2,3)=3
• 长度5："bbbab"→max(dp[1][4]=3, dp[0][3]=3)=3？等等，这里s[0]=s[4]="b"，所以应该是dp[1][3]+2=2+2=4

最终得到最长回文子序列长度为4，即"bbbb"。