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

题目描述
给定一个字符串 s，要求统计其中所有回文子序列的个数。注意，子序列不要求连续，但必须保持原字符串中的相对顺序。结果可能很大，需要对 10^9 + 7 取模。进阶要求：不仅统计总数，还需统计以每个起始位置 i 和结束位置 j 为边界的子串中回文子序列的个数。

解题过程

1. 问题分析

   • 回文子序列：例如在字符串 "aab" 中，"a"、"aa"、"b"、"ab"（不是回文）、"aba"（不存在）都是子序列，但回文子序列包括 "a"、"a"（第二个 a）、"aa"、"b"，共 4 个（注意重复的 "a" 算两个，因为来自不同位置）。
   • 难点：子序列不连续，且需避免重复计数。动态规划可定义状态 dp[i][j] 表示子串 s[i:j]（左闭右闭区间）中的回文子序列个数。

2. 基础动态规划定义

   • 设 dp[i][j] 表示子串 s[i..j] 内回文子序列的个数。
   • 初始条件：
     • 空子串（i > j）：dp[i][j] = 0。
     • 单字符子串（i = j）：dp[i][j] = 1，因为单个字符是回文。
   • 状态转移：
     • 如果 s[i] != s[j]：回文子序列要么包含 s[i] 但不含 s[j]，要么包含 s[j] 但不含 s[i]，要么两者都不含。但直接计算易重复，使用容斥原理：

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

       这里减去 dp[i+1][j-1] 是因为两者都不含的情况被重复计算了。
     • 如果 s[i] == s[j]：除了上述情况外，新增所有 s[i+1..j-1] 中的回文子序列两端加上 s[i] 和 s[j] 形成的新回文子序列，同时还包括 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
       

       这里 +1 是直接统计 s[i]s[j] 这个二元子序列，而 dp[i+1][j-1] + 1 中的 +1 是空序列（两端加 s[i] 和 s[j] 形成 s[i]s[j]），但注意空序列本身在 dp 中未显式计数，需单独处理。更精确的推导：
       • 当 s[i] == s[j] 时，新增的回文子序列包括：所有 s[i+1..j-1] 中的回文子序列两端加 s[i] 和 s[j]（共 dp[i+1][j-1] 个），以及 s[i]s[j] 本身（1 个）。因此：

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

   • 最终答案：dp[0][n-1]，其中 n 是字符串长度。

3. 处理进阶要求

   • 需要统计以每个 (i, j) 为边界的回文子序列个数，实际上 dp[i][j] 已经直接给出该值。
   • 如果需输出所有区间结果，直接返回整个 dp 表即可。

4. 模运算处理

   • 由于结果可能很大，每次加法后需取模 10^9 + 7。
   • 减法后可能出现负数，需加模数再取模：(a - b + mod) % mod。

5. 复杂度分析

   • 时间复杂度：O(n²)，需要填充 n × n 的 DP 表。
   • 空间复杂度：O(n²)，可优化至 O(n)（仅需上一行数据），但进阶要求需完整表。

示例代码（Python）

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
                if dp[i][j] < 0:
                    dp[i][j] += mod
    
    return dp[0][n-1]

# 进阶：返回整个dp表，其中dp[i][j]表示s[i..j]的回文子序列数
def countPalindromicSubsequencesTable(s: str) -> List[List[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):
        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
                if dp[i][j] < 0:
                    dp[i][j] += mod
    return dp

总结
本题通过动态规划巧妙利用容斥原理避免重复计数，重点在于理解 s[i] == s[j] 时新增的回文子序列来源。进阶要求通过维护完整的 DP 表自然满足。