统计不同回文子序列个数问题（字符集限制版） 题目描述： 给定一个字符串s，统计其中不同非空回文子序列的个数。由于结果可能很大，返回对10^9+7取模后的结果。字符串只包含字符'a','b','c','d'四种字符。 解题过程： 问题分析 我们需要统计字符串中所有不同的回文子序列个数。子序列不要求连续，但必须保持相对顺序。由于只包含四种字符，我们可以利用这个限制来设计高效算法。 动态规划定义 定义dp[ i][ j]表示子串s[ i...j ]中不同回文子序列的个数。 基础情况 当i > j时，dp[ i][ j ] = 0（空子串） 当i = j时，dp[ i][ j ] = 1（单个字符本身就是一个回文子序列） 状态转移方程 情况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 ] 此时需要更仔细分析： 首先包含dp[ i+1][ j]和dp[ i][ j-1 ]中的所有回文子序列 但dp[ i+1][ j-1 ]被重复计算了，需要减去 另外，所有dp[ i+1][ j-1]中的回文子序列都可以在两端加上s[ i]（等于s[ j ]）形成新的回文子序列 但要避免重复计数 更精确的解法： 定义dp[ i][ j][ c]表示在子串s[ i...j ]中，以字符c开头和结尾的不同回文子序列个数。 优化解法 由于只有4种字符，我们可以使用三维DP： dp[ i][ j][ k]：子串s[ i...j ]中，以第k种字符开头和结尾的不同回文子序列个数。 状态转移： 如果i > j：dp[ i][ j][ k ] = 0 如果i = j：如果s[ i]等于第k个字符，dp[ i][ j][ k ] = 1，否则为0 如果s[ i] ≠ 第k个字符或s[ j ] ≠ 第k个字符： dp[ i][ j][ k] = dp[ i+1][ j][ k] 或 dp[ i][ j-1][ k] 或 dp[ i+1][ j-1][ k ] 如果s[ i] = s[ j ] = 第k个字符： 此时可以形成新的回文序列：字符c本身，以及所有dp[ i+1][ j-1 ]中的回文序列两端加上c 最终计算 总的不同回文子序列数 = 对所有i,j组合和所有字符k的dp[ 0][ n-1][ k ]求和 时间复杂度 O(n² × 4) = O(4n²)，其中n是字符串长度。 空间优化 可以使用二维数组，通过遍历顺序优化来减少空间复杂度。 这个解法充分利用了字符集有限的特性，通过三维DP精确统计了以每个字符开头和结尾的回文子序列个数，避免了重复计数问题。