最长回文子序列的个数（Count Different Palindromic Subsequences）

题目描述：
给定一个字符串 s，你需要统计字符串中不同的非空回文子序列的个数。注意，这里的“不同”是指子序列本身作为字符串是不同的，即使它们由相同的字符组成但在原串中选取的位置不同，只要最终的字符串相同，就视为同一种。返回结果对 10^9+7 取模。

例如，对于字符串 s = "bccb"，不同的回文子序列有：
"b" (索引 0 或 3), "c" (索引 1 或 2), "bb", "cc", "bcb", "bccb"，一共 6 种。
注意 "b" 虽然可以由不同位置的 'b' 构成，但作为字符串 "b" 只算一种。

解题过程：

第一步：理解问题与子问题定义

我们需要统计所有不同的回文子序列，而不是求最长长度。
关键难点在于避免重复：相同的回文字符串可能由原串中不同位置的字符组合而成，但我们只应统计一次。

思路：
定义 dp[i][j] 表示在子串 s[i..j] 中，不同的回文子序列的个数（模 MOD）。

但这样直接定义无法处理重复问题。
举例：s = "aba"，dp[0][2] 中，"a" 可以由 s[0] 或 s[2] 得到，但应只算一种。

第二步：避免重复的核心思路

为了避免重复，我们可以按子序列的首尾字符来分类。
更精确的做法是：在计算 dp[i][j] 时，我们考虑以某种字符 ch 作为最外层的回文子序列。
即：我们要找的回文子序列，其最左字符是 ch，最右字符也是 ch，中间可以是任何回文子序列（包括空）。

具体地，对于区间 [i, j]，我们先找到这个区间内最左边的字符等于某个字符 c 的位置，记作 left，以及最右边的字符等于 c 的位置，记作 right。

• 如果 left > right，说明区间内没有字符 c，则对于字符 c 来说，贡献为 0。
• 如果 left == right，说明只有一个字符 c，那么只有单个字符 "c" 这一种回文子序列。
• 如果 left < right，那么我们可以构造出：
  1. 单个字符 "c"。
  2. 字符 c 在两端，中间是子串 s[left+1 .. right-1] 中的任何回文子序列（包括空）。
     注意：中间部分的不同回文子序列都会与两端的 c 组成新的回文子序列，并且这些新序列彼此不同（因为中间不同或为空）。
  3. 但是，中间部分的不同回文子序列可能包含以 c 开头和结尾的子序列，这会导致重复计数，需要小心处理。

为了避免重复，我们实际可以采用如下递推公式（分四种情况）：

第三步：递推公式推导

定义 dp[i][j] 为子串 s[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] 是因为它在前面两项中被重复计算了（即两个端点都不包含的子序列）。

2. 如果 s[i] == s[j]：
   设 s[i] = s[j] = c，我们需要找到区间内下一个等于 c 的位置：

   • 令 low 为 i 之后第一个等于 c 的位置。
   • 令 high 为 j 之前最后一个等于 c 的位置。

   然后分情况：

   • 如果 low > high，说明在 (i, j) 区间内没有字符 c，那么可以构成的新回文子序列是：单个字符 c 和 c + 中间任意回文子序列 + c，中间任意回文子序列来自 dp[i+1][j-1]，但注意这里要包括空串（即 "cc"）。
     所以：

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

     解释：dp[i+1][j-1] 是中间的回文子序列个数，每个都可以在两端加 c 得到新的回文序列（2倍），另外新增 "c" 和 "cc" 两种。

   • 如果 low == high，说明中间恰好只有一个 c，那么中间的回文子序列中，只有以这个 c 为唯一字符的会与两端的 c 形成 "c" 和 "ccc" 等，但注意要避免重复。实际推导可得：

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

     这里 +1 是因为新增了 "cc" 这个回文串（两端 c 和中间那个 c 构成 "ccc" 其实与 "c"+"c" 重叠计算需小心）。严格推导：此时中间只有一个 c，那么中间的回文子序列个数为 dp[low+1][high-1] 实际是 dp[low+1][low-1] 即 0，但整体推导时可用通用公式。

   实际上，通用公式是：

   if s[i] == s[j]:
       low = 第一个 >i 且 s[low]==c 的位置
       high = 最后一个 <j 且 s[high]==c 的位置
       if low > high:
           dp[i][j] = 2 * dp[i+1][j-1] + 2
       elif low == high:
           dp[i][j] = 2 * dp[i+1][j-1] + 1
       else:  # low < high
           dp[i][j] = 2 * dp[i+1][j-1] - dp[low+1][high-1]
   

   解释 low < high 情况：此时中间至少有两个 c，那么以中间那两个 c 为端点的回文子序列在两端加 c 时会与以更靠近两端的 c 为端点的子序列重复，所以要减去 dp[low+1][high-1] 这一部分（即中间夹着的那一段的回文子序列个数），因为它们被重复计算了。

第四步：边界条件

• 当 i > j 时，dp[i][j] = 0。
• 当 i == j 时，dp[i][j] = 1（单个字符本身是一个回文子序列）。

第五步：计算顺序

由于 dp[i][j] 依赖于 dp[i+1][j]、dp[i][j-1]、dp[i+1][j-1] 以及更小的区间，所以我们可以按区间长度从小到大计算。

第六步：举例验证

以 s = "bccb" 为例：

长度 1：dp[0][0]=1, dp[1][1]=1, dp[2][2]=1, dp[3][3]=1。

长度 2：

• [0,1]："b","c" → dp=2。
• [1,2]："c","c" → 注意 s[1]==s[2]，且中间无 c，公式：2dp[2][1]+2=20+2=2。
• [2,3]："c","b" → dp=2。

长度 3：

• [0,2]：s[0]!=s[2]，dp=dp[1][2]+dp[0][1]-dp[1][1]=2+2-1=3。
  实际回文子序列："b","c","cc"。
• [1,3]：s[1]!=s[3]，dp=dp[2][3]+dp[1][2]-dp[2][2]=2+2-1=3。
  实际："c","b","cc"。

长度 4：
[0,3]：s[0]==s[3]='b'，找到 low=第一个 >0 的 'b' 是 3，high=最后一个 <3 的 'b' 是 0，但注意 low 是第一个大于 i 的，这里 i=0, 下一个 b 是 3，此时 low=3, high=0（因为从右往左找最后一个小于 j=3 的 b 是 0）。
实际上，我们要找的 low 是 i 右边第一个等于 b 的位置，high 是 j 左边第一个等于 b 的位置，但这样会出错。正确做法是用下一个相同字符的位置。

实现时，我们可以预处理数组 next[i][k] 表示从 i 开始下一个字符 'a'+k 的位置，prev[i][k] 表示 i 之前上一个字符 'a'+k 的位置。

更常用做法是：在递归函数中，当 s[i]==s[j] 时，用 while 循环找 low 和 high。

但推导公式不变，举例 [0,3]：
s[0]=='b', s[3]=='b'，在 (0,3) 区间内找 'b' 的位置，没有。
所以 low>high，公式：dp=2dp[1][2]+2=22+2=6。
实际："b","c","bb","bcb","bccb","cc"。一共 6 种，符合。

第七步：模运算

每一步加、减、乘后都要对 MOD=1e9+7 取模，注意减法可能产生负数，要加 MOD 再取模。

第八步：复杂度与实现

时间复杂度 O(n^2)，空间复杂度 O(n^2)。
预处理 next 和 prev 数组可帮助快速找到 low 和 high，但也可在循环中直接查找（增加 O(n) 时间，总复杂度仍 O(n^2)）。

总结步骤：

1. 定义 dp[i][j] 为 s[i..j] 中不同回文子序列的个数。
2. 根据 s[i] 与 s[j] 是否相等分情况递推，注意处理重复情况。
3. 按区间长度从小到大计算 dp 值。
4. 结果 = dp[0][n-1]。