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

题目描述

给定一个字符串s，找到其中最长的回文子序列的长度。子序列定义为：通过删除原字符串中的一些字符（也可以不删除）而不改变剩余字符的相对顺序得到的新字符串。

例如：

• 输入："bbbab"
• 输出：4
• 解释：最长回文子序列是"bbbb"

解题过程

1. 问题分析
回文子序列不要求字符在原字符串中连续，但必须保持相对顺序。我们需要找到最长的这样的序列。

2. 基础DP思路
定义dp[i][j]表示子串s[i...j]的最长回文子序列长度。

状态转移方程：

• 如果s[i] == s[j]：
  • 当i == j时，dp[i][j] = 1（单个字符）
  • 当i + 1 == j时，dp[i][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. 状态压缩优化
观察发现，计算dp[i][j]时只依赖于：

• 当前行的dp[i+1][j]
• 前一行的dp[i][j-1]
• 前一行的dp[i+1][j-1]

因此可以用一维数组优化空间复杂度。

4. 优化后的DP实现

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    # 使用一维数组，dp[j]表示当前处理行中区间[i,j]的最长回文子序列长度
    dp = [0] * n
    
    for i in range(n-1, -1, -1):
        # pre保存dp[i+1][j-1]的值
        pre = 0
        dp[i] = 1  # 单个字符的情况
        
        for j in range(i+1, n):
            # temp保存当前dp[j]的值，用于下一轮作为pre
            temp = dp[j]
            
            if s[i] == s[j]:
                # dp[i][j] = dp[i+1][j-1] + 2
                dp[j] = pre + 2
            else:
                # dp[i][j] = max(dp[i+1][j], dp[i][j-1])
                dp[j] = max(dp[j], dp[j-1])
            
            # 更新pre为当前轮的dp[i+1][j-1]
            pre = temp
    
    return dp[n-1]

5. 逐步计算示例（s = "bbbab"）

初始状态：dp = [0,0,0,0,0]

i=4（从右往左处理）：

• dp[4] = 1
• 最终dp = [0,0,0,0,1]

i=3：

• dp[3] = 1
• j=4: s[3]=='a' != s[4]=='b'，dp[4]=max(1,0)=1
• dp = [0,0,0,1,1]

i=2：

• dp[2] = 1
• j=3: s[2]=='b' != s[3]=='a'，dp[3]=max(1,1)=1
• j=4: s[2]=='b' == s[4]=='b'，dp[4]=pre+2=0+2=2
• dp = [0,0,1,1,2]

i=1：

• dp[1] = 1
• j=2: s[1]=='b' == s[2]=='b'，dp[2]=pre+2=0+2=2
• j=3: s[1]=='b' != s[3]=='a'，dp[3]=max(1,2)=2
• j=4: s[1]=='b' == s[4]=='b'，dp[4]=pre+2=1+2=3
• dp = [0,1,2,2,3]

i=0：

• dp[0] = 1
• j=1: s[0]=='b' == s[1]=='b'，dp[1]=pre+2=0+2=2
• j=2: s[0]=='b' == s[2]=='b'，dp[2]=pre+2=1+2=3
• j=3: s[0]=='b' != s[3]=='a'，dp[3]=max(2,3)=3
• j=4: s[0]=='b' == s[4]=='b'，dp[4]=pre+2=2+2=4
• 最终dp = [1,2,3,3,4]

结果为dp[4] = 4

6. 复杂度分析

• 时间复杂度：O(n²)
• 空间复杂度：O(n)（从O(n²)优化到O(n)）

这种状态压缩方法在保持正确性的同时，显著降低了空间复杂度。