线性动态规划：最长回文子序列的变种——统计不同非空回文子序列的个数 题目描述： 给定一个字符串s，你需要统计其中所有不同的非空回文子序列的个数。注意，子序列不要求连续，但不同的序列即使由相同的字符组成，只要字符的索引位置不同就被视为不同的子序列。同时，相同的字符序列即使出现在不同的位置也被视为相同的子序列（即我们只关心字符序列本身，不关心位置）。结果可能很大，需要对10^9+7取模。 解题过程： 这个问题是经典最长回文子序列问题的变种，我们需要统计所有不同的回文子序列，而不是找最长的那个。 问题分析： 我们需要找到所有不同的回文子序列 子序列可以不连续，但必须保持原字符串中的相对顺序 相同的字符序列只计数一次（即使出现在不同位置） 空序列不计入 动态规划定义： 我们定义dp[ i][ j]表示在子串s[ i...j ]中，所有不同的非空回文子序列的个数。 状态转移方程： 考虑子串s[ i...j ]： 如果s[ i] ≠ s[ j ]： dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1] - dp[ i+1][ j-1 ] 这里减去dp[ i+1][ j-1 ]是为了避免重复计算两个子区间的交集部分 如果s[ i] = s[ j ]： 我们需要找到在区间(i,j)内所有与s[ i ]相同的字符位置 设left为第一个在i右侧且等于s[ i ]的字符位置 设right为第一个在j左侧且等于s[ j ]的字符位置 情况分析： a) 如果left > right：说明i和j之间没有相同的字符 dp[ i][ j] = dp[ i+1][ j-1 ] × 2 + 2 乘以2是因为对于s[ i+1...j-1]中的每个回文子序列，我们可以在两边加上s[ i]和s[ j ]得到新的回文 加2是因为新增了单个字符s[ i]和两个字符s[ i]s[ j ]这两个回文 b) 如果left == right：说明i和j之间恰好有一个相同的字符 dp[ i][ j] = dp[ i+1][ j-1 ] × 2 + 1 加1是因为新增的两个字符s[ i]s[ j]与单个字符s[ left ]是相同的回文 c) 如果left < right：说明i和j之间有多个相同的字符 dp[ i][ j] = dp[ i+1][ j-1] × 2 - dp[ left+1][ right-1 ] 这里减去dp[ left+1][ right-1 ]是为了避免重复计算 边界条件： 当i > j时，dp[ i][ j ] = 0（空序列） 当i = j时，dp[ i][ j ] = 1（单个字符） 计算顺序： 我们需要按照子串长度从小到大的顺序计算，从长度为1的子串开始，逐步计算到整个字符串。 示例说明： 以字符串"bccb"为例： 长度为1：所有单个字符都是回文，共4个 长度为2："bc"、"cc"、"cb" 长度为3："bcc"、"ccb"、"bcb" 长度为4："bccb" 不同的回文子序列有：b, c, bb, cc, bcb, bccb 复杂度分析： 时间复杂度：O(n²)，需要填充n×n的DP表 空间复杂度：O(n²)，用于存储DP表 通过这种动态规划方法，我们可以高效地统计字符串中所有不同的非空回文子序列的个数。