最长回文子序列的变种：统计不同非空回文子序列的个数（进阶版：考虑重复子序列的统计） 题目描述 给定一个字符串s，要求统计其中所有不同非空回文子序列的个数。注意，这里的"不同"指的是内容不同的子序列，即使它们来自原字符串的不同位置，只要内容相同就视为同一个。例如，对于字符串"bccb"，不同的回文子序列包括："b", "c", "bb", "cc", "bcb", "bccb"，共6个。 解题思路 这个问题是经典最长回文子序列问题的变种，我们需要统计所有不同的回文子序列，而不仅仅是找到最长的那个。我们可以使用动态规划来解决这个问题，关键在于如何避免重复计数。 详细步骤 第一步：定义状态 我们定义 dp[i][j] 为字符串s从索引i到j（包含两端）的子串中，不同回文子序列的个数。 第二步：状态转移方程 考虑子串s[ i...j ]： 如果s[ i] == s[ j ]： 我们可以将s[ i]和s[ j ]作为新的回文子序列的边界 此时，回文子序列包括： 单独的s[ i]和s[ j ] 所有s[ i+1...j-1]中的回文子序列，两端加上s[ i]和s[ j ] 但是需要注意避免重复计数 如果s[ i] != s[ j ]： 回文子序列来自三个部分： s[ i+1...j ]中的回文子序列 s[ i...j-1 ]中的回文子序列 减去重复计算的s[ i+1...j-1 ]中的回文子序列 更精确的状态转移方程： 如果s[ i] == s[ j ]： 找到最左边的等于s[ i]的字符位置left，和最右边的等于s[ i ]的字符位置right 如果left == right（只有一个这样的字符）： dp[i][j] = 2 * dp[i+1][j-1] + 1 如果left == right - 1（有两个这样的字符）： dp[i][j] = 2 * dp[i+1][j-1] + 2 否则（有三个或更多这样的字符）： dp[i][j] = 2 * dp[i+1][j-1] - dp[left+1][right-1] 如果s[ i] != s[ j ]： dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] 第三步：边界条件 当i > j时， dp[i][j] = 0 （空子串） 当i == j时， dp[i][j] = 1 （单个字符本身就是一个回文子序列） 第四步：计算顺序 由于dp[ i][ j]依赖于dp[ i+1][ j]、dp[ i][ j-1]和dp[ i+1][ j-1 ]，我们需要从较短的子串向较长的子串计算，即按子串长度递增的顺序计算。 第五步：最终结果 最终结果是 dp[0][n-1] ，其中n是字符串s的长度。 示例演示 以字符串"bccb"为例： 初始化：所有长度为1的子串都有1个回文子序列 计算长度为2的子串： "bc"：'b', 'c' → 2 "cc"：'c', 'cc' → 2 "cb"：'c', 'b' → 2 计算长度为3的子串： "bcc"：'b', 'c', 'cc', 'bcb' → 4 "ccb"：'c', 'b', 'cc', 'cbc' → 4 计算长度为4的子串："bccb" → 6 最终得到6个不同的回文子序列。 复杂度分析 时间复杂度：O(n²)，需要填充n×n的DP表 空间复杂度：O(n²)，用于存储DP表 这种方法通过动态规划巧妙地避免了重复计数，准确地统计了所有不同的回文子序列。