区间动态规划例题：统计同构子字符串的数目问题 题目描述 给定一个字符串 s ，统计其中同构子字符串的数目。同构子字符串定义为所有字符都相同的连续子串。例如，字符串 "abbccca" 的同构子字符串包括 "a" 、 "b" 、 "bb" 、 "c" 、 "cc" 、 "ccc" 、 "a" （最后一个字符）等。注意，单个字符是长度为 1 的同构子串，而 "bb" 是长度为 2 的同构子串。要求计算所有同构子串的总数。 解题思路 问题分析 若直接枚举所有子串再判断是否同构，时间复杂度为 O(n³)（枚举子串 O(n²)，判断同构 O(n)），效率太低。 观察规律：对于连续相同字符的区间（如 "aaa" ），其包含的同构子串数量为 1+2+3+...+k = k(k+1)/2 ，其中 k 为区间长度。 因此，只需遍历字符串，统计连续相同字符的区间长度，对每个区间计算子串数并累加。 动态规划定义 定义 dp[i] 表示以 s[i] 结尾的同构子串的最大长度（即连续相同字符的区间长度）。 状态转移方程： \[ dp[ i ] = \begin{cases} dp[ i-1] + 1, & \text{if } s[ i] = s[ i-1 ] \\ 1, & \text{otherwise} \end{cases} \] 最终答案：对每个 dp[i] 累加，因为以 i 结尾的同构子串数恰好为 dp[i] （例如 "aaa" 以末位结尾的子串有 "a" 、 "aa" 、 "aaa" 共 3 个）。 步骤详解 初始化： dp[0] = 1 ，总计数 ans = dp[0] 。 遍历 i = 1 到 n-1 ： 若 s[i] == s[i-1] ，则 dp[i] = dp[i-1] + 1 ； 否则 dp[i] = 1 。 ans += dp[i] 。 返回 ans 。 示例演算 以 s = "abbccca" 为例： i=0: dp[0]=1 , ans=1 i=1: s[1]='b' ≠ s[0]='a' → dp[1]=1 , ans=2 i=2: s[2]='b' = s[1] → dp[2]=2 , ans=4 i=3: s[3]='c' ≠ s[2] → dp[3]=1 , ans=5 i=4: s[4]='c' = s[3] → dp[4]=2 , ans=7 i=5: s[5]='c' = s[4] → dp[5]=3 , ans=10 i=6: s[6]='a' ≠ s[5] → dp[6]=1 , ans=11 最终结果：11。 总结 本题通过动态规划记录连续相同字符的长度，将问题转化为对每个位置结尾的同构子串数的累加，时间复杂度 O(n)，空间复杂度可优化至 O(1)。