线性动态规划：最长回文子序列的变种——统计回文子序列的个数（进阶版：不同起始和结束位置的统计）

题目描述
给定一个字符串 s，要求统计其中回文子序列的个数。注意：子序列不要求连续，但必须保持原始字符串中的相对顺序，并且空序列不算在内。结果可能很大，需要对 \(10^9 + 7\) 取模。

示例
输入：s = "aba"
输出：5
解释：回文子序列有 "a", "b", "a", "aa", "aba"。

解题思路

1. 定义状态
   设 dp[i][j] 表示字符串 s 在区间 [i, j] 内的回文子序列个数（闭区间，包含 i 和 j）。

2. 状态转移

   • 情况1：当 s[i] == s[j] 时，区间 [i+1, j-1] 内的所有回文子序列都可以在首尾加上 s[i] 和 s[j] 形成新的回文子序列。此外，还需加上 s[i] 和 s[j] 自身组成的子序列（如 "aa"）。
     转移方程：
     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
     （注意：这里需要减去重复计算的 dp[i+1][j-1]，但加上 dp[i+1][j-1] + 1 是为了包含新生成的子序列。）

   • 情况2：当 s[i] != s[j] 时，区间 [i, j] 的回文子序列等于左右子区间的并集，但需减去中间重复部分：
     dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]

3. 边界条件

   • 单个字符一定是回文子序列：dp[i][i] = 1。
   • 空区间（i > j）定义为 0。

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

详细推导（以 s = "aba" 为例）

1. 初始化（单个字符）：
   dp[0][0] = 1（"a"）
   dp[1][1] = 1（"b"）
   dp[2][2] = 1（"a"）

2. 计算长度为 2 的区间：

   • [0,1]：s[0]='a', s[1]='b'，不相等。
     dp[0][1] = dp[1][1] + dp[0][0] - dp[1][0] = 1 + 1 - 0 = 2（子序列："a", "b"）
   • [1,2]：s[1]='b', s[2]='a'，不相等。
     dp[1][2] = dp[2][2] + dp[1][1] - dp[2][1] = 1 + 1 - 0 = 2（子序列："b", "a"）

3. 计算长度为 3 的区间 [0,2]：
   s[0]='a', s[2]='a'，相等。
   dp[0][2] = dp[1][2] + dp[0][1] + 1 = 2 + 2 + 1 = 5
   解释：

   • 原有子序列：[1,2] 的 "b", "a" 和 [0,1] 的 "a", "b"。
   • 新增：将 s[0] 和 s[2] 加到 [1,1] 的子序列前，得到 "aa" 和 "aba"；再加上 "a" 和 "a" 自身。
     最终子序列："a", "b", "a", "aa", "aba"。

代码实现（关键部分）

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  # 单个字符
    
    for length in range(2, n + 1):  # 区间长度从 2 到 n
        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] + 1) % MOD
            else:
                dp[i][j] = (dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]) % MOD
    
    return dp[0][n-1] % MOD

总结

• 核心思想：通过动态规划逐步扩展区间，利用子区间的结果合并计算大区间的回文子序列数。
• 关键点：当首尾字符相同时，新增的子序列数为中间区间的子序列数加 1（因为可以单独用首尾字符组成新序列）。
• 时间复杂度：\(O(n^2)\)，空间复杂度：\(O(n^2)\)（可优化为 \(O(n)\)）。