区间动态规划例题：统计不同回文子序列个数问题

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

注意：即使多个子序列由相同的字符组成但在s中的位置不同，只要这些字符来自s中的不同位置，它们就被视为不同的子序列。但题目要求统计"不同"的回文子序列，意味着我们需要去重：如果两个子序列的字符内容完全相同，即使来自不同位置，也只算一个。

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

解题思路
这是一个经典的区间DP问题，我们需要统计字符串中所有不同的回文子序列。关键点在于避免重复计数。

详细解题步骤

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

2. 状态转移方程
   考虑区间[i, j]：

   • 基本情况：当i = j时，只有一个字符，dp[i][j] = 1

   • 当s[i] ≠ s[j]时：
     根据容斥原理：dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
     因为中间部分被重复计算了一次，需要减去

   • 当s[i] = s[j]时：
     情况更复杂，需要找到左右边界相同的字符：
     dp[i][j] = dp[i+1][j-1] × 2 + 2
     解释：中间的dp[i+1][j-1]可以独立存在，也可以与两端的s[i]和s[j]组合，所以乘以2。
     额外的+2表示单独的s[i]和s[i]+s[j]这两个回文子序列。

     但是，如果中间有与s[i]相同的字符，需要避免重复计数：

     • 找到左边第一个等于s[i]的位置l
     • 找到右边第一个等于s[i]的位置r
       根据l和r的位置关系调整计数。

3. 处理重复情况
   为了避免重复计数相同内容的回文子序列，我们需要：

   • 当找到l和r时，如果l < r，说明中间有重复字符
   • 需要减去dp[l+1][r-1]来避免重复计数

4. 最终结果
   整个字符串的答案就是dp[0][n-1]，其中n是字符串长度。

完整算法实现

def countPalindromicSubsequences(s: str) -> int:
    MOD = 10**9 + 7
    n = len(s)
    
    # DP数组
    dp = [[0] * n for _ in range(n)]
    
    # 单个字符的情况
    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]:
                # 两端字符不同
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
            else:
                # 两端字符相同
                left, right = i + 1, 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][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]
            
            # 处理负数情况和取模
            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表

这个算法通过区间DP巧妙地处理了回文子序列的统计问题，同时避免了重复计数，是区间动态规划的经典应用。