最长回文子串的变种——统计所有回文子串的数量 题目描述 给定一个字符串 s ，要求统计其中所有回文子串（即正读反读都一样的连续子串）的数量。例如，字符串 "abc" 的回文子串有三个： "a" , "b" , "c" ；字符串 "aaa" 的回文子串有六个：三个单字符 "a" ，两个双字符 "aa" （起始位置不同），一个三字符 "aaa" 。 要求：设计一个动态规划算法，高效地统计回文子串的总数，并解释其原理。 解题思路 我们可以使用一个二维动态规划数组 dp[i][j] 来表示子串 s[i..j] 是否为回文串。但这里我们只需统计数量，而不需要存储所有子串的具体内容。动态规划的状态转移方程为： 当 i == j 时，单个字符总是回文， dp[i][j] = true 。 当 j = i+1 时，两个字符需相等才是回文， dp[i][j] = (s[i] == s[j]) 。 当 j > i+1 时， dp[i][j] = (s[i] == s[j] and dp[i+1][j-1]) 。 每发现一个回文子串（ dp[i][j] == true ），就将计数器加一。 详细步骤 定义状态 ： 设 dp[i][j] 表示子串 s[i..j] （闭区间）是否为回文串，其中 0 ≤ i ≤ j < n 。 初始化 ： 所有单个字符的子串都是回文串，即当 i == j 时， dp[i][j] = true ，计数器加一。 对于长度大于 1 的子串，初始时 dp[i][j] 设为 false 。 状态转移 ： 我们需要按子串长度从小到大的顺序计算。这是因为在判断 dp[i][j] 时，我们需要知道 dp[i+1][j-1] （即去掉首尾字符的子串）是否为回文。 当 s[i] == s[j] 时： 如果子串长度为 2（即 j = i+1 ），则 dp[i][j] = true 。 如果子串长度大于 2（即 j > i+1 ），则 dp[i][j] = dp[i+1][j-1] 。 当 s[i] != s[j] 时， dp[i][j] = false 。 每设置一个 dp[i][j] = true ，就表示发现一个新的回文子串，计数器加一。 计算顺序 ： 外层循环枚举子串长度 len ，从 2 到 n（因为长度为 1 的已在初始化时处理）。内层循环枚举起始位置 i ，则 j = i + len - 1 。这样能保证在计算 dp[i][j] 时， dp[i+1][j-1] 已经被计算过（因为其长度更短）。 最终结果 ： 计数器最终的值即为所有回文子串的数量。 复杂度分析 ： 时间复杂度：O(n²)，因为需要填充一个 n × n 的二维表。 空间复杂度：O(n²)，用于存储 dp 数组。实际上可以优化到 O(n)，但为了清晰理解，我们先使用二维数组。 示例演示 以 s = "aba" 为例： 初始化： 长度为 1 的子串： "a" , "b" , "a" ，计数器为 3。 长度 2： "ab" ：s[ 0] != s[ 1 ]，不回文。 "ba" ：s[ 1] != s[ 2 ]，不回文。 长度 3： "aba" ：s[ 0] == s[ 2] 且 dp[1][1] 为真，所以是回文，计数器加一。 最终共有 4 个回文子串。 这个算法清晰且易于实现，直接统计了所有可能的回文子串。