区间动态规划例题：统计不同回文子序列个数问题（字符集限制版）

题目描述

给定一个字符串 s，统计其中不同非空回文子序列的个数。由于结果可能很大，返回对 10^9+7 取模后的结果。

注意：

• 不同子序列指的是即使内容相同，只要在原始字符串中的位置不同，就视为不同的子序列
• 子序列不要求连续
• 字符串 s 只包含 'a', 'b', 'c', 'd' 四种字符
• 字符串长度不超过 1000

示例：
输入：s = "bccb"
输出：6
解释：6个不同的回文子序列为：'b', 'c', 'b', 'bb', 'cc', 'bcb'

解题思路

第一步：理解问题本质

这是一个统计不同回文子序列个数的问题，需要特别注意"不同"的含义。即使两个子序列内容相同，只要在原字符串中的位置不同，就算作不同的子序列。

第二步：定义状态

定义 dp[i][j] 表示字符串 s 从索引 i 到 j（包含两端）的子串中，不同回文子序列的个数。

第三步：状态转移分析

考虑区间 [i, j] 的所有回文子序列，可以分为以下几类：

1. 不包含 s[i] 和 s[j]：dp[i+1][j-1]
2. 包含 s[i] 但不包含 s[j]：dp[i][j-1] - dp[i+1][j-1]
3. 包含 s[j] 但不包含 s[i]：dp[i+1][j] - dp[i+1][j-1]
4. 同时包含 s[i] 和 s[j]：需要 s[i] == s[j]

当 s[i] == s[j] 时，情况比较复杂，需要仔细分析。

第四步：处理重复情况

关键难点在于避免重复计数。当 s[i] == s[j] 时，我们需要找到第一个等于 s[i] 的位置 left 和最后一个等于 s[i] 的位置 right：

• 如果 left == right：说明中间没有相同的字符，新增的回文子序列是 s[i] 和 s[i] + s[j]
• 如果 left > right：不可能出现
• 如果 left < right：需要减去中间重复计算的部分

第五步：完整状态转移方程

if i > j: dp[i][j] = 0
elif i == j: dp[i][j] = 1
else:
    if s[i] == s[j]:
        left = i + 1
        right = j - 1
        # 找到第一个等于s[i]的位置
        while left <= j and s[left] != s[i]:
            left += 1
        # 找到最后一个等于s[i]的位置  
        while right >= i and s[right] != s[i]:
            right -= 1
            
        if left > right:  # 中间没有相同字符
            dp[i][j] = dp[i+1][j-1] * 2 + 2
        elif left == right:  # 中间只有一个相同字符
            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]

第六步：边界条件处理

• 当 i > j 时，区间为空，回文子序列个数为 0
• 当 i == j 时，只有一个字符，回文子序列个数为 1（该字符本身）

第七步：实现细节

def countPalindromicSubsequences(s: str) -> int:
    n = len(s)
    MOD = 10**9 + 7
    dp = [[0] * n for _ in range(n)]
    
    # 初始化长度为1的子串
    for i in range(n):
        dp[i][i] = 1
    
    # 按长度从小到大遍历
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j]:
                left = i + 1
                right = j - 1
                
                # 找到第一个等于s[i]的位置
                while left <= j and s[left] != s[i]:
                    left += 1
                # 找到最后一个等于s[i]的位置
                while right >= i and s[right] != s[i]:
                    right -= 1
                
                if left > right:
                    # 中间没有相同字符
                    dp[i][j] = dp[i+1][j-1] * 2 + 2
                elif left == right:
                    # 中间只有一个相同字符
                    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]
            
            # 处理负数情况
            dp[i][j] %= MOD
            if dp[i][j] < 0:
                dp[i][j] += MOD
    
    return dp[0][n-1]

第八步：复杂度分析

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

第九步：示例验证

以 s = "bccb" 为例：

• dp[0][3] 计算过程会递归计算所有子区间的结果
• 最终得到 6 个不同的回文子序列
• 结果与题目示例一致

这个解法巧妙地处理了重复计数的问题，通过寻找相同字符的边界来准确计算新增的回文子序列个数。