区间动态规划例题：最长回文子序列问题（状态压缩优化版本）

题目描述

给定一个字符串s，找出其最长回文子序列的长度。回文子序列定义为原字符串中通过删除某些字符（也可以不删除）而不改变剩余字符相对顺序构成回文序列。例如，字符串"bbbab"的最长回文子序列是"bbbb"，长度为4。

解题思路

这个问题可以使用区间动态规划解决。基本思路是定义dp[i][j]表示字符串s从索引i到j的子串中最长回文子序列的长度。通过状态转移方程计算所有可能的子串。

详细解题步骤

1. 基础动态规划解法

首先我们来看标准的区间DP解法：

1. 状态定义：dp[i][j]表示子串s[i...j]的最长回文子序列长度
2. 初始化：
   • 单个字符：dp[i][i] = 1（所有长度为1的子串都是回文）
   • 两个字符：如果s[i] == s[i+1]，则dp[i][i+1] = 2，否则为1
3. 状态转移：
   • 如果s[i] == s[j]：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])
4. 计算顺序：按子串长度从小到大计算

2. 状态压缩优化

由于标准解法需要O(n²)空间，我们可以优化到O(n)空间：

1. 优化思路：观察状态转移方程，dp[i][j]只依赖于：

   • 同一行的左边元素：dp[i][j-1]
   • 下一行的元素：dp[i+1][j]和dp[i+1][j-1]

2. 实现方法：

   • 使用一维数组dp_curr和dp_prev
   • dp_prev存储前一行的结果（即i+1行的结果）
   • dp_curr存储当前行的结果（即i行的结果）

3. 具体步骤：

   def longestPalindromeSubseq(s: str) -> int:
       n = len(s)
       # 初始化：dp_prev表示i+1行的结果
       dp_prev = [0] * n
       dp_curr = [0] * n
   
       # 从最后一行开始向上计算
       for i in range(n-1, -1, -1):
           dp_curr[i] = 1  # 单个字符的情况
           for j in range(i+1, n):
               if s[i] == s[j]:
                   # 如果首尾字符相同
                   if j == i+1:
                       dp_curr[j] = 2  # 两个相同字符
                   else:
                       dp_curr[j] = dp_prev[j-1] + 2
               else:
                   # 如果首尾字符不同，取最大值
                   dp_curr[j] = max(dp_prev[j], dp_curr[j-1])
   
           # 更新dp_prev为当前行，准备计算上一行
           dp_prev, dp_curr = dp_curr, dp_prev
   
       return dp_prev[n-1]
   

3. 算法正确性验证

以字符串"bbbab"为例：

• 初始化：所有dp[i][i] = 1
• 长度为2："bb"→2, "bb"→2, "ba"→1, "ab"→1
• 长度为3："bbb"→3, "bba"→2, "bab"→3
• 长度为4："bbba"→3, "bbab"→3
• 长度为5："bbbab"→4

结果正确，最长回文子序列"bbbb"长度为4。

4. 复杂度分析

• 时间复杂度：O(n²)，需要填充n×(n+1)/2个状态
• 空间复杂度：O(n)，从O(n²)优化到O(n)

关键点总结

1. 状态压缩利用了动态规划表格的递推特性
2. 只保留必要的前一行信息，避免存储整个二维表格
3. 计算顺序从下到上，从短子串到长子串
4. 边界情况需要单独处理（单个字符和两个字符的情况）