最长回文子序列的变种：统计所有回文子序列的个数 题目描述 给定一个字符串s，要求统计其中所有回文子序列的个数。注意，即使多个回文子序列由相同的字符组成，但如果这些字符在字符串中的位置索引不同，它们也被视为不同的子序列。结果可能很大，需要取模（如10^9+7）。 解题过程 问题分析 回文子序列是指从原字符串中删除0个或多个字符后，剩余字符按原顺序排列形成的回文串。 与最长回文子序列问题（求最长长度）不同，这里需要统计所有可能的回文子序列数量。 关键点：不同位置的相同字符序列视为不同子序列。 动态规划定义 定义dp[ i][ j ]表示字符串s中从索引i到j（闭区间）的子串中，回文子序列的个数。 最终目标是求dp[ 0][ n-1 ]，其中n是字符串长度。 状态转移方程 基础情况：当i > j时，区间无效，dp[ i][ j ] = 0。 当i == j时，单个字符本身就是一个回文子序列，dp[ i][ j ] = 1。 当i < j时，考虑区间[ i, j ]： a. 统计不包含s[ i]和s[ j]的子序列：dp[ i+1][ j-1 ]（但注意这里统计的是内部回文子序列）。 b. 当s[ i] == s[ j]时，除了内部子序列，还可以用s[ i]和s[ j ]作为首尾构造新的回文序列： 内部每个回文子序列都可以在首尾加上s[ i]和s[ j]形成新的回文序列，数量等于dp[ i+1][ j-1 ]。 另外，s[ i]和s[ j ]单独组成的两个字符序列也是一个新回文序列。 因此总数为：dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1] + (s[ i]==s[ j] ? dp[ i+1][ j-1 ] + 1 : 0) 简化后：如果s[ i]==s[ j]，dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1 ] + 1 否则，dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1 ] 计算顺序 按子串长度从小到大计算：先计算所有长度为1的子串，然后长度2、3，直到n。 这样保证计算dp[ i][ j]时，所需的子问题dp[ i+1][ j]、dp[ i][ j-1]和dp[ i+1][ j-1 ]都已计算。 示例演示 以字符串"aba"为例： 初始化：所有单字符子序列dp[ 0][ 0]=1, dp[ 1][ 1]=1, dp[ 2][ 2 ]=1 长度2："ab"：s[ 0]!=s[ 1]，dp[ 0][ 1] = dp[ 1][ 1] + dp[ 0][ 0] - dp[ 1][ 0 ] = 1+1-0=2 "ba"：同理dp[ 1][ 2 ]=2 长度3："aba"：s[ 0]==s[ 2]，dp[ 0][ 2] = dp[ 1][ 2] + dp[ 0][ 1 ] + 1 = 2+2+1=5 回文子序列：""(空序列，但题目通常不统计)、"a"、"b"、"a"、"aba"，共5个（空序列根据题目要求决定是否计入）。 边界处理 空序列：根据题目要求，如果统计空序列，初始化时dp[ i][ i ]应包括空序列和单字符。 取模：在每一步加法后立即取模，避免溢出。 复杂度分析 时间复杂度：O(n²)，需要填充n×(n)的DP表。 空间复杂度：O(n²)，可优化至O(n)使用滚动数组。 通过这种动态规划方法，我们可以高效地统计字符串中所有回文子序列的数量。