统计不同非空回文子序列个数问题（字符集限制版）

题目描述
给定一个字符串 s，由字符集 {'a','b','c','d'} 中的字符组成，长度不超过 1000。要求统计字符串中所有不同的非空回文子序列的个数。由于结果可能很大，返回对 10^9 + 7 取模后的结果。

注意：子序列是从原字符串中删除零个或多个字符后，剩余字符的相对顺序保持不变形成的序列。回文子序列是正读和反读相同的子序列。即使多个子序列由相同的字符组成但在原字符串中的位置不同，只要它们对应的索引集合不同，就视为不同的子序列。

解题思路
这是一个典型的区间动态规划问题。我们需要统计所有不同的回文子序列，关键在于避免重复计数。定义 dp[i][j] 为子串 s[i..j] 中不同回文子序列的个数。通过分情况讨论，可以逐步推导状态转移方程。

步骤详解

1. 状态定义
   设 dp[i][j] 表示子串 s[i..j] 内不同回文子序列的数量（包括空序列？但题目要求非空，最终需减去空序列）。为简化，先计算包含空序列的结果，最后减去 1。

2. 基础情况

   • 当 i > j：无效区间，dp[i][j] = 0。
   • 当 i == j：单个字符，只有该字符本身和空序列，但题目要求非空，但按包含空序列的惯例，dp[i][j] = 2（空序列和该字符）。

3. 状态转移
   考虑区间 [i, j]：

   • 若 s[i] != s[j]：
     回文子序列要么包含 s[i] 但不含 s[j]，要么包含 s[j] 但不含 s[i]，要么两者都不含。但直接加会重复计算两者都不含的部分（即 dp[i+1][j-1]）。因此：

     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]：
     设字符 c = s[i]。此时所有回文子序列可分为：
     a. 包含 c 作为两端字符的子序列：形如 c + X + c，其中 X 是 s[i+1..j-1] 中的任意回文子序列。
     b. 不包含 c 作为两端字符的子序列：即 s[i+1..j-1] 中的所有回文子序列。
     但注意，情况 a 中，X 可以是空序列（此时子序列为 cc），且所有由 c 包裹的子序列都是新的，不会与情况 b 重复。因此：

     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 是因为空序列被 c 包裹形成 cc 是新的子序列？不对，需修正：实际上，当 s[i] == s[j] 时，新增的子序列是所有 s[i+1..j-1] 中的回文子序列两端加 c，再加上 c 和 cc 两个特殊序列。但更精确的处理是：
     设 L 为第一个大于 i 且 s[L] == c 的位置，R 为最后一个小于 j 且 s[R] == c 的位置：

     • 如果 L > R，说明中间没有相同字符，新增的子序列为 c 和 cc，即新增 2 个：
       dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + 2
     • 如果 L == R，说明中间有一个相同字符，新增的子序列为 c 和 cc，但 c 会重复？需避免重复计数。实际上，通用公式为：
       dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + dp[L+1][R-1] + 1
       其中 L 和 R 是中间最靠近两端的相同字符位置。但更标准解法是直接使用以下递推：

       dp[i][j] = 2 * dp[i+1][j-1] + 2   (如果中间无相同字符)
       dp[i][j] = 2 * dp[i+1][j-1] - dp[L+1][R-1]  (如果中间有相同字符，L、R 为最内同字符位置)
       

     但为简化，我们采用标准解法（避免重复计数）：

     • 先计算 dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
     • 若 s[i] == s[j]，则加上以 s[i] 和 s[j] 作为两端的新回文子序列数量，即 dp[i+1][j-1] + 1（其中 +1 是序列 cc 本身）。但这样会重复计算中间已有同字符序列？实际上，正确公式为：

       dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1   (如果 s[i] == s[j])
       

       但需验证：例如 "aba"，i=0, j=2：
       dp[1][2]=2 ("b", ""), dp[0][1]=2 ("a",""), dp[1][1]=2 ("","a")? 不对。

   实际上，标准解法是：

   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] + dp[i][j-1] + 1  (如果 s[i] == s[j])
   

   但需处理重复：当 s[i] == s[j] 时，中间部分的所有回文子序列加上两端字符后都是新序列，且额外多一个序列 cc（即两端字符单独形成的序列）。但这样会重复计算中间已有同字符包裹的序列？不会，因为中间部分的序列加上两端字符后是新的，不会与之前的重复。

4. 最终结果
   整个字符串 s[0..n-1] 的 dp[0][n-1] 包含了空序列，因此最终答案为 dp[0][n-1] - 1（减去空序列）。

5. 复杂度优化
   直接按上述递推计算所有区间，时间复杂度 O(n²)，空间复杂度 O(n²)，满足题目要求。

示例验证
以 s = "ab" 为例：

• dp[0][0] = 2（序列：""、"a"）
• dp[1][1] = 2（序列：""、"b"）
• dp[0][1]：s[0] != s[1]，
  dp[0][1] = dp[1][1] + dp[0][0] - dp[1][0] = 2 + 2 - 0 = 4（序列："", "a", "b", "ab"？但 "ab" 不是回文）
  这里发现错误！实际上，dp[i][j] 应只统计回文子序列，但上述递推未限制回文性质。

修正：
正确解法应使用 dp[i][j] 表示 s[i..j] 中不同回文子序列数，且递推时需确保新增序列是回文。标准解法是：

1. 若 s[i] != s[j]：dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
2. 若 s[i] == s[j]：
   • 设 L = i+1, R = j-1
   • while L <= R and s[L] != s[i]: L++
   • while R >= L and s[R] != s[i]: R--
   • 如果 L > R：中间无相同字符，dp[i][j] = 2 * dp[i+1][j-1] + 2
   • 如果 L == R：中间有一个相同字符，dp[i][j] = 2 * dp[i+1][j-1] + 1
   • 如果 L < R：中间有多个相同字符，dp[i][j] = 2 * dp[i+1][j-1] - dp[L+1][R-1]

此解法可避免重复计数，确保每个回文子序列只被统计一次。最终答案取 dp[0][n-1] 即可（已包含非空序列）。