最长回文子序列的变种：统计回文子序列的个数 题目描述 给定一个字符串s，统计其中回文子序列的个数。注意：子序列不要求连续，但必须保持原始顺序。同时，即使多个子序列由相同的字符组成，只要它们在原字符串中的位置索引不同，就被视为不同的子序列。 例如： 输入："aba" 输出：7 解释：回文子序列有："a", "b", "a", "aa", "aba", "aba", "aaa"（注意：位置不同的相同字符序列算作不同） 解题思路 这个问题可以通过动态规划来解决。我们定义dp[ i][ j ]表示字符串s从索引i到j（包含两端）的子串中回文子序列的个数。 详细步骤 状态定义 dp[ i][ j]：子串s[ i...j ]中的回文子序列个数 我们需要计算dp[ 0][ n-1 ]，其中n是字符串长度 基础情况 当i = j时（单个字符）：dp[ i][ j ] = 1 只有一个字符，只有1个回文子序列（该字符本身） 当i > j时：dp[ i][ j ] = 0 空子串，没有回文子序列 状态转移方程 考虑子串s[ i...j ]，有以下几种情况： 情况1：s[ i] ≠ s[ j] 回文子序列要么包含s[ i]不包含s[ j]，要么包含s[ j]不包含s[ i ]，要么两个都不包含 但不能同时包含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] 回文子序列可以： a) 不包含s[ i]和s[ j]：dp[ i+1][ j-1 ]个 b) 包含s[ i]但不包含s[ j]：dp[ i][ j-1] - dp[ i+1][ j-1 ]个 c) 包含s[ j]但不包含s[ i]：dp[ i+1][ j] - dp[ i+1][ j-1 ]个 d) 同时包含s[ i]和s[ j]：此时需要在所有s[ i+1...j-1]的回文子序列两侧加上s[ i]和s[ j ] 由于s[ i] = s[ 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 ] + 1 简化后：dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1 ] + 1 计算顺序 按子串长度从小到大计算 先计算所有长度为1的子串，然后长度为2，依此类推 最终结果 dp[ 0][ n-1 ]就是整个字符串的回文子序列个数 示例演示 以字符串"aba"为例： 初始化单个字符： dp[ 0][ 0 ] = 1 ("a") dp[ 1][ 1 ] = 1 ("b") dp[ 2][ 2 ] = 1 ("a") 计算长度为2的子串： dp[ 0][ 1]：s[ 0]='a'≠s[ 1 ]='b' = dp[ 1][ 1] + dp[ 0][ 0] - dp[ 1][ 0 ] = 1 + 1 - 0 = 2 ("a", "b") dp[ 1][ 2]：s[ 1]='b'≠s[ 2 ]='a' = dp[ 2][ 2] + dp[ 1][ 1] - dp[ 2][ 1 ] = 1 + 1 - 0 = 2 ("b", "a") 计算整个字符串dp[ 0][ 2 ]： s[ 0]='a'=s[ 2 ]='a' dp[ 0][ 2] = dp[ 1][ 2] + dp[ 0][ 1 ] + 1 = 2 + 2 + 1 = 5 但实际应该有7个，哪里出错了？ 修正状态转移方程 实际上，当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] + (dp[ i+1][ j-1 ] + 1) 简化后：dp[ i][ j] = dp[ i+1][ j] + dp[ i][ j-1 ] + 1 让我们重新验证"aba"的例子： dp[ 0][ 2] = dp[ 1][ 2] + dp[ 0][ 1 ] + 1 = 2 + 2 + 1 = 5 但实际回文子序列是： 单个字符："a"(位置0), "b", "a"(位置2) → 3个 两个字符："aa" → 1个 三个字符："aba" → 1个 总共应该是5个，不是7个。 结论 这个问题的描述可能有误，或者对"不同位置索引"的理解需要明确。如果严格按照位置索引不同就算不同子序列，那么"aba"的正确结果应该是5个回文子序列。