统计不同回文子序列个数问题（字符集限制版） 题目描述： 给定一个字符串s，统计其中不同非空回文子序列的个数。由于结果可能很大，返回对10^9+7取模的结果。 字符串s只包含字符'a','b','c','d'四种字符，长度不超过1000。 解题过程： 问题分析： 我们需要统计字符串中所有不同的回文子序列 子序列不要求连续，但必须保持相对顺序 相同的回文序列只计数一次 由于字符集只有4种字符，我们可以利用这个限制进行优化 状态定义： 定义dp[ i][ j]表示在子串s[ i...j ]中不同回文子序列的个数。 基础情况： 当i > j时，dp[ i][ j ] = 0（空子串） 当i = j时，dp[ i][ j ] = 1（单个字符本身就是一个回文序列） 状态转移分析： 考虑子串s[ i...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]，要么包含s[ j]但不包含s[ i]，但这样会重复计算既不包含s[ i]也不包含s[ j ]的部分。 情况2：s[ i] = s[ j ] 这种情况比较复杂，我们需要考虑以s[ i]和s[ j ]作为回文序列两端的子序列。 避免重复计数的关键： 当s[ i] = s[ j ]时，我们不能简单地将所有情况相加，因为可能会重复计算某些序列。 具体算法步骤： 找到子串s[ i+1...j-1]中第一个等于s[ i ]的位置left 找到子串s[ i+1...j-1]中最后一个等于s[ i ]的位置right 根据left和right的位置关系，分情况讨论 详细状态转移方程： if s[ i] ≠ s[ j ]: dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1 ] else: left = 在i+1到j-1范围内第一个s[ k]=s[ i ]的位置 right = 在i+1到j-1范围内最后一个s[ k]=s[ i ]的位置 if left == -1: # 中间没有相同的字符 dp[ i][ j] = 2 * dp[ i+1][ j-1 ] + 2 elif left == right: # 中间恰好有一个相同的字符 dp[ i][ j] = 2 * dp[ i+1][ j-1 ] + 1 else: # 中间有至少两个相同的字符 dp[ i][ j] = 2 * dp[ i+1][ j-1] - dp[ left+1][ right-1 ] 算法实现细节： 使用动态规划，按子串长度从小到大计算 预处理每个位置对于每个字符的next和prev位置，以快速找到left和right 注意取模操作 时间复杂度：O(n²)，空间复杂度：O(n²) 这个算法的关键在于当两端字符相同时，通过找到中间区域中相同字符的出现位置来避免重复计数，确保每个不同的回文子序列只被统计一次。