线性动态规划：最长回文子串的变种——统计所有回文子串的数量

题目描述

给定一个字符串 s，要求统计其中所有回文子串的数量。回文子串定义为正读和反读都相同的连续子串（即子串在原串中是连续的）。
例如：

• 输入 s = "abc"，回文子串有 "a"、"b"、"c"，共 3 个。
• 输入 s = "aaa"，回文子串有 "a"（出现 3 次）、"aa"（出现 2 次）、"aaa"（出现 1 次），共 6 个。
  注意：只要起始或结束位置不同，即使内容相同的子串也视为不同的子串。

解题思路

这是一个经典的线性动态规划问题，其核心思路是使用一个二维布尔数组 dp[i][j] 来记录子串 s[i..j] 是否为回文串。通过动态规划填充这个数组，我们可以在填充过程中统计回文子串的数量。

为什么选择动态规划？

暴力枚举所有子串需要 O(n²) 个子串，对每个子串检查回文又需要 O(n)，总复杂度 O(n³)，效率太低。动态规划通过利用已计算的子问题结果，将判断回文的时间降至 O(1)，总复杂度降至 O(n²)。

动态规划定义与状态转移

定义状态
设 dp[i][j] 表示子串 s[i..j] 是否为回文串（i ≤ j）。

• dp[i][j] = true 表示 s[i..j] 是回文串。
• dp[i][j] = false 表示不是回文串。

状态转移方程
如何判断 s[i..j] 是否为回文？

1. 基本情况：
   • 单个字符一定是回文：dp[i][i] = true（所有长度为 1 的子串）。
   • 两个字符的子串：dp[i][i+1] = (s[i] == s[i+1])。
2. 长度大于 2 的子串（j - i >= 2）：
   • 首先，两端字符必须相等：s[i] == s[j]。
   • 其次，去掉两端后的子串必须是回文：dp[i+1][j-1] == true。
     因此转移方程为：

\[ dp[i][j] = (s[i] == s[j]) \ \&\&\ dp[i+1][j-1] \]

边界条件
注意当 j - i <= 1 时，不需要依赖 dp[i+1][j-1]，因为此时子串长度为 1 或 2。

计算顺序与统计方法

计算顺序
由于 dp[i][j] 依赖于 dp[i+1][j-1]（即左下角的值），我们需要按子串长度从小到大计算：

1. 先初始化所有长度为 1 和 2 的子串。
2. 然后从长度 3 开始，依次计算更长的子串。
   这样确保在计算 dp[i][j] 时，dp[i+1][j-1] 已经计算完毕。

统计数量
在填充 dp 表的过程中，每当 dp[i][j] 被设为 true，就表示发现一个新的回文子串，计数器 count 加 1。

逐步示例解析

以 s = "ababa" 为例：

1. 初始化 dp 表（5×5），所有元素为 false。
2. 长度 = 1：
   • dp[0][0]（子串 "a"）为 true → count = 1。
   • dp[1][1]（"b"）为 true → count = 2。
   • … 直到 dp[4][4]（"a"）→ count = 5。
3. 长度 = 2：
   • dp[0][1]："ab"，a != b → false。
   • dp[1][2]："ba"，b != a → false。
   • dp[2][3]："ab" → false。
   • dp[3][4]："ba" → false。
     没有新增回文子串，count 仍为 5。
4. 长度 = 3：
   • dp[0][2]："aba"，两端字符 s[0]=a，s[2]=a 相等，且 dp[1][1]=true → true → count = 6。
   • dp[1][3]："bab"，s[1]=b，s[3]=b 相等，且 dp[2][2]=true → true → count = 7。
   • dp[2][4]："aba"，两端字符相等，且 dp[3][3]=true → true → count = 8。
5. 长度 = 4：
   • dp[0][3]："abab"，s[0]=a，s[3]=b 不等 → false。
   • dp[1][4]："baba"，s[1]=b，s[4]=a 不等 → false。
6. 长度 = 5：
   • dp[0][4]："ababa"，两端字符相等，且 dp[1][3]=true → true → count = 9。

最终 count = 9。
验证：回文子串有：

• 长度 1："a", "b", "a", "b", "a"（5 个）
• 长度 3："aba", "bab", "aba"（3 个）
• 长度 5："ababa"（1 个）
  共 9 个。

算法实现

def countPalindromicSubstrings(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    
    dp = [[False] * n for _ in range(n)]
    count = 0
    
    # 子串长度从 1 到 n
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1  # 子串结束位置
            
            if length == 1:
                dp[i][j] = True
                count += 1
            elif length == 2:
                if s[i] == s[j]:
                    dp[i][j] = True
                    count += 1
            else:  # length >= 3
                if s[i] == s[j] and dp[i+1][j-1]:
                    dp[i][j] = True
                    count += 1
    
    return count

复杂度分析

• 时间复杂度：O(n²)，因为需要填充一个 n×n 的 dp 表。
• 空间复杂度：O(n²)，用于存储 dp 表。

空间优化
注意到在计算 dp[i][j] 时只依赖于 dp[i+1][j-1]（即上一行同一列的前一个位置），因此可以使用滚动数组将空间复杂度降至 O(n)。但由于代码可读性考虑，二维数组版本更直观。

总结

本问题通过动态规划高效地统计了所有回文子串的数量。关键点在于：

1. 定义 dp[i][j] 表示子串 s[i..j] 是否为回文。
2. 状态转移基于两端字符相等性和内部子串的回文性质。
3. 按子串长度从小到大计算，确保子问题先被解决。
4. 在填充过程中实时计数。

这个方法可以扩展到更复杂的回文子串问题，比如统计长度至少为 L 的回文子串数量，或者统计所有不重复的回文子串等。