区间动态规划例题：统计不同回文子序列个数问题（字符集限制版） 题目描述： 给定一个字符串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（单个字符本身就是一个回文子序列） 状态转移方程： 情况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 ] 设字符c = s[ i] = s[ j ] 我们需要找到在区间(i,j)内： left：第一个等于c的字符位置 right：最后一个等于c的字符位置 根据left和right的位置关系，有： 如果left > right：不存在中间的c字符 dp[ i][ j] = 2 * dp[ i+1][ j-1 ] + 2 如果left = right：存在一个中间的c字符 dp[ i][ j] = 2 * dp[ i+1][ j-1 ] + 1 如果left < right：存在至少两个中间的c字符 dp[ i][ j] = 2 * dp[ i+1][ j-1] - dp[ left+1][ right-1 ] 详细解释： 当两端字符相同时，我们考虑所有以这两个相同字符作为边界的回文子序列 +2的情况：新增"c"和"cc"两个回文子序列 +1的情况：新增"cc"一个回文子序列（"c"已经包含在内部） 减去内部重复的情况：当中间有多个相同字符时，避免重复计数 算法实现： 使用记忆化搜索或自底向上的DP： 按区间长度从小到大计算 对于每个区间[ i,j]，根据上述规则计算dp[ i][ j ] 时间复杂度：O(n²)，空间复杂度：O(n²) 取模处理： 由于结果可能很大，每次加法、减法运算后都要对10^9+7取模，注意减法可能产生负数，需要处理。