统计回文子串的个数问题 题目描述： 给定一个字符串s，你需要统计其中回文子串的个数。回文子串要求是原字符串中连续的子串，且正着读和反着读完全相同。不同位置的相同回文子串应被计为不同的子串。 解题过程： 问题分析： 我们需要找出所有满足回文条件的连续子串 回文子串的长度可以是1到n（n为字符串长度） 单个字符一定是回文子串 我们需要一个系统的方法来避免重复计数和遗漏 动态规划定义： 定义dp[ i][ j]表示子串s[ i...j ]是否为回文子串 如果dp[ i][ j] = true，表示s[ i...j ]是回文子串 如果dp[ i][ j] = false，表示s[ i...j ]不是回文子串 状态转移方程： (1) 基本情况（长度为1）： dp[ i][ i ] = true（单个字符一定是回文） (2) 基本情况（长度为2）： dp[ i][ i+1] = (s[ i] == s[ i+1 ])（两个相同字符是回文） (3) 一般情况（长度≥3）： dp[ i][ j] = (s[ i] == s[ j]) && dp[ i+1][ j-1 ] 即：首尾字符相同，且中间子串也是回文 填表顺序： 由于dp[ i][ j]依赖于dp[ i+1][ j-1 ]（即左下方的状态），我们需要： 按子串长度从小到大计算 先计算所有长度为1的子串 再计算长度为2的子串 然后计算长度为3的子串，依此类推 算法实现步骤： 步骤1：初始化计数器和dp表 创建n×n的dp表，初始化为false 计数器count初始为0 步骤2：处理长度为1的子串 对所有i从0到n-1： dp[ i][ i ] = true count++（每个单字符都是回文） 步骤3：处理长度为2的子串 对所有i从0到n-2： 如果s[ i] == s[ i+1 ]： dp[ i][ i+1 ] = true count++ 步骤4：处理长度≥3的子串 对长度L从3到n： 对起始位置i从0到n-L： 计算结束位置j = i + L - 1 如果s[ i] == s[ j]且dp[ i+1][ j-1 ] == true： dp[ i][ j ] = true count++ 步骤5：返回结果 返回count作为回文子串的总数 示例分析（字符串"abc"）： 长度1：3个回文子串（"a", "b", "c"） 长度2：0个回文子串（"ab", "bc"都不是回文） 长度3：0个回文子串（"abc"不是回文） 总计：3个回文子串 复杂度分析： 时间复杂度：O(n²)，需要填充n×n的dp表 空间复杂度：O(n²)，用于存储dp表 这种方法通过系统性地检查所有可能的子串，确保不会遗漏任何回文子串，同时利用动态规划避免了重复计算。