最长回文子序列（进阶版：统计不同非空回文子序列的个数）
题目描述：
给定一个字符串 s，统计其中所有不同非空回文子序列的个数。注意，即使多个子序列由相同的字符组成但起始和结束位置不同，只要它们的内容相同就被视为同一个子序列。结果需要对 10^9 + 7 取模。
解题过程：
-
定义状态：
设 dp[i][j] 表示字符串 s 在区间 [i, j] 内的不同回文子序列个数。我们需要避免重复计数相同内容的子序列。 -
状态转移思路：
考虑区间 [i, j]：-
若 s[i] ≠ s[j]：
根据容斥原理，dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]。因为中间部分会被重复计算一次。 -
若 s[i] = s[j] = c：
此时区间内的回文子序列包括：
a) 内部子序列：即 [i+1, j-1] 内的所有回文子序列（记为内部集）。
b) 外部扩展：以 c 包裹内部集的每个子序列，形成新回文序列（如 "a" + X + "a"）。
c) 新增单字符 "c" 和双字符 "cc"。但需避免重复：若内部集已包含单字符 "c"，则新增的 "c" 会重复。因此需要找到区间内第一个和最后一个等于 c 的位置，设 left 为 i 右侧第一个等于 c 的位置，right 为 j 左侧最后一个等于 c 的位置：
- 若 left > right：说明内部无字符 c，新增序列为 {"c", "cc"}。
即 dp[i][j] = 2 * dp[i+1][j-1] + 2。 - 若 left == right：说明内部恰有一个 c，新增序列为 {"c", "cc"}，但 "c" 已存在于内部集。
即 dp[i][j] = 2 * dp[i+1][j-1] + 1。 - 若 left < right：说明内部有多个 c，此时以 left 和 right 为边界的内部子序列会被重复计算（因其已包含在 [i+1, j-1] 中）。
需减去重复部分：dp[i][j] = 2 * dp[i+1][j-1] - dp[left+1][right-1]。
- 若 left > right：说明内部无字符 c，新增序列为 {"c", "cc"}。
-
-
边界条件：
- 当 i > j 时，dp[i][j] = 0（空区间无子序列）。
- 当 i == j 时，dp[i][j] = 1（单字符本身是回文）。
-
计算顺序：
按区间长度从小到大计算，从长度 1 到 n。 -
示例（s = "bccb"）：
- 初始化长度为1：dp[0][0]=1, dp[1][1]=1, dp[2][2]=1, dp[3][3]=1。
- 长度2：
[0,1]：s[0]≠s[1] → dp[0][1]=dp[1][1]+dp[0][0]-dp[1][0]=1+1-0=2（"b","c"）。
[1,2]：s[1]=s[2]='c'，内部[2,1]无效，left=1, right=2 → left<right 且内部无c？实际检查：left=1, right=2，区间 [2,1] 无效，故按 left>right 处理？ 此处需谨慎：left=1 和 right=2 是同一位置？ 不，left是i右侧第一个c（索引1），right是j左侧最后一个c（索引2），但此时i=1, j=2，内部区间为[i+1,j-1]=[2,1]无效，故内部无字符，应属 left>right 情况（因内部区间空）。正确计算：dp[1][2] = 2dp[2][1] + 2 = 20 + 2 = 2（"c","cc"）。
但注意索引1和2的字符都是'c'，内部区间空，所以新增序列为 "c"（已存在？）和 "cc"。实际上，初始时dp[1][1]和dp[2][2]各有一个"c"，但合并时需去重。正确逻辑应通过预处理记录每个区间内字符的左右边界来避免混淆。
为清晰，我们换用标准解法：
预处理数组 next[i][c] 和 prev[i][c] 分别表示从i向右/向左第一个字符c的位置。
在 s[i]=s[j] 时：
left = next[i][c], right = prev[j][c]。- 若 left < right：减去重复部分 dp[left+1][right-1]。
- 若 left = right：加1（仅新增"cc"）。
- 若 left > right：加2（新增"c"和"cc"）。
-
最终结果：
dp[0][n-1] 即为所有不同非空回文子序列个数，取模后返回。
总结：
本题通过动态规划按区间扩展，结合字符位置预处理去重，确保每个回文子序列只被统计一次。