最长回文子序列的变种：统计所有回文子序列的个数（进阶版：考虑重复子序列的统计）

我将为您详细讲解这个线性动态规划问题。这个问题是经典最长回文子序列问题的变种，要求统计字符串中所有不同的回文子序列的个数。

问题描述

给定一个字符串s，统计其中所有不同的非空回文子序列的个数。子序列不要求连续，但必须保持原始顺序，且回文子序列是正读反读都相同的序列。

例如：

• 输入："bccb"
• 输出：6
• 解释：不同的回文子序列有："b", "c", "bb", "cc", "bcb", "bccb"

解题思路

步骤1：定义状态

我们定义dp[i][j]表示在子串s[i...j]中不同回文子序列的个数。

步骤2：状态转移方程

情况1：首尾字符相同
如果s[i] == s[j]：

• 我们考虑子串s[i+1...j-1]中的所有回文子序列
• 在这些子序列的左右两边都加上字符s[i]，仍然构成回文
• 还要考虑单个字符s[i]和s[i] + s[j]这两个新的回文

状态转移方程：

dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + (dp[i+1][j-1] + 1)

简化后：

dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1

情况2：首尾字符不同
如果s[i] != s[j]：

• 我们需要减去重复计算的部分

dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]

步骤3：处理重复子序列

为了避免重复统计，我们需要特殊处理：

• 当找到相同的字符时，检查中间是否有相同的字符
• 如果有，需要减去重复计算的部分

详细解法

def countPalindromicSubsequences(s: str) -> int:
    n = len(s)
    MOD = 10**9 + 7
    dp = [[0] * n for _ in range(n)]
    
    # 初始化：单个字符都是回文
    for i in range(n):
        dp[i][i] = 1
    
    # 填充DP表
    for length in range(2, n + 1):  # 子串长度
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j]:
                # 找到左右边界内第一个和最后一个与s[i]相同的字符
                left = i + 1
                right = j - 1
                
                # 向右找到第一个等于s[i]的字符
                while left <= right and s[left] != s[i]:
                    left += 1
                # 向左找到第一个等于s[i]的字符  
                while left <= right and s[right] != s[i]:
                    right -= 1
                
                if left > right:
                    # 中间没有相同的字符
                    # dp[i+1][j-1] * 2 + 2
                    # *2：给所有中间的回文子序列左右都加上s[i]
                    # +2：单个字符s[i]和s[i]+s[j]
                    dp[i][j] = dp[i+1][j-1] * 2 + 2
                elif left == right:
                    # 中间恰好有一个相同的字符
                    # dp[i+1][j-1] * 2 + 1
                    # +1：因为s[i]+s[j]会与中间的重复
                    dp[i][j] = dp[i+1][j-1] * 2 + 1
                else:
                    # 中间有多个相同的字符
                    # 需要减去重复计算的部分
                    dp[i][j] = dp[i+1][j-1] * 2 - dp[left+1][right-1]
            else:
                # 首尾字符不同
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
            
            # 处理负数情况
            if dp[i][j] < 0:
                dp[i][j] += MOD
            dp[i][j] %= MOD
    
    return dp[0][n-1]

逐步示例

以字符串"bccb"为例：

初始化：

dp[0][0] = 1 ("b")
dp[1][1] = 1 ("c") 
dp[2][2] = 1 ("c")
dp[3][3] = 1 ("b")

长度2的子串：

• s[0:1] = "bc"：不同字符
  dp[0][1] = dp[1][1] + dp[0][0] - dp[1][0] = 1 + 1 - 0 = 2
• s[1:2] = "cc"：相同字符，中间没有相同字符
  dp[1][2] = dp[2][2] * 2 + 2 = 1 * 2 + 2 = 4 ("c", "c", "cc", "c")
• s[2:3] = "cb"：不同字符
  dp[2][3] = dp[3][3] + dp[2][2] - dp[3][2] = 1 + 1 - 0 = 2

长度3的子串：

• s[0:2] = "bcc"：首尾不同
  dp[0][2] = dp[1][2] + dp[0][1] - dp[1][1] = 4 + 2 - 1 = 5
• s[1:3] = "ccb"：首尾不同
  dp[1][3] = dp[2][3] + dp[1][2] - dp[2][2] = 2 + 4 - 1 = 5

长度4的子串：

• s[0:3] = "bccb"：首尾相同'b'
  找到left=1, right=2，中间有相同字符'c'
  dp[0][3] = dp[1][2] * 2 - dp[2][1] = 4 * 2 - 0 = 8

最终结果为6个不同的回文子序列。

时间复杂度

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

这个算法通过动态规划巧妙地统计了所有不同的回文子序列，避免了重复计算，是处理此类问题的经典解法。