区间动态规划例题：统计同构子字符串的数目问题 题目描述 给定一个字符串s，定义同构子字符串为满足以下条件的子串：该子串中所有字符都相同。例如，在字符串"abbccca"中，"a"、"bb"、"ccc"、"a"都是同构子字符串。 现在要求计算字符串s中所有同构子字符串的数目。注意：结果需要包括所有可能的连续子串，只要它们满足同构条件。例如对于"abbccca"，正确答案是13，因为： 长度为1的同构子串：a, b, b, c, c, c, a（共7个） 长度为2的同构子串：bb, cc, cc（共3个） 长度为3的同构子串：ccc（共1个） 总数为7 + 3 + 1 = 11？等等，让我们重新计算... 实际上正确的计算应该是： 位置0："a"（1个） 位置1-2："b"、"b"、"bb"（3个） 位置3-5："c"、"c"、"c"、"cc"、"cc"、"ccc"（6个） 位置6："a"（1个） 总共：1 + 3 + 6 + 1 = 11 但题目说正确答案是13，说明我们可能漏掉了什么。让我重新分析题目要求... 重新理解题目 实际上，题目要求的是统计所有可能的同构子字符串，这意味着我们需要考虑字符串中所有满足"所有字符相同"条件的连续子串。 对于"abbccca"： 第一个字符'a'：产生1个同构子串 连续的2个'b'：产生3个同构子串（b, b, bb） 连续的3个'c'：产生6个同构子串（c, c, c, cc, cc, ccc） 最后一个'a'：产生1个同构子串 总共：1 + 3 + 6 + 1 = 11 但正确答案应该是13，这意味着我的理解有误。让我重新阅读题目... 正确的题目理解 实际上，题目要求的是：对于字符串s，统计所有满足同构条件的子串的数目，但这里有个关键点——我们需要考虑所有可能的连续子串，只要它们的所有字符相同。 对于长度为k的连续相同字符段，它包含的同构子串数量是k* (k+1)/2。 对于"abbccca"： "a"（长度1）：1个同构子串 "bb"（长度2）：3个同构子串 "ccc"（长度3）：6个同构子串 "a"（长度1）：1个同构子串 总共：1 + 3 + 6 + 1 = 11 但题目说答案是13，这说明我可能记错了示例。让我重新确认... 解题思路分析 这个问题可以用区间动态规划来解决，具体思路如下： 状态定义 ：定义dp[ i][ j]表示子串s[ i...j ]中同构子字符串的数目。 状态转移 ： 如果s[ i] = s[ j]且s[ i...j]中所有字符都相同，那么dp[ i][ j] = (j-i+1)* (j-i+2)/2 否则，我们需要将区间分割为更小的部分来计算 更高效的方法 ：实际上，我们可以遍历字符串，找到所有连续的相同字符段，对每个长度为k的段，贡献k* (k+1)/2个同构子串。 区间动态规划解法 让我们用动态规划的方法来系统解决： 步骤1：状态定义 定义dp[ i ]表示以第i个字符结尾的当前连续相同字符段的长度。 步骤2：状态转移方程 如果s[ i] == s[ i-1]，那么dp[ i] = dp[ i-1 ] + 1 否则，dp[ i ] = 1 步骤3：计算结果 对于每个位置i，dp[ i]表示当前连续相同字符段的长度，这个段贡献的同构子串数量就是dp[ i ]。 总结果 = Σdp[ i ] (i从0到n-1) 举例验证 对于s = "abbccca"： i=0：dp[ 0 ]=1，结果=1 i=1：s[ 1]='b' ≠ s[ 0]='a'，dp[ 1 ]=1，结果=1+1=2 i=2：s[ 2]='b' = s[ 1]='b'，dp[ 2]=dp[ 1 ]+1=2，结果=2+2=4 i=3：s[ 3]='c' ≠ s[ 2]='b'，dp[ 3 ]=1，结果=4+1=5 i=4：s[ 4]='c' = s[ 3]='c'，dp[ 4]=dp[ 3 ]+1=2，结果=5+2=7 i=5：s[ 5]='c' = s[ 4]='c'，dp[ 5]=dp[ 4 ]+1=3，结果=7+3=10 i=6：s[ 6]='a' ≠ s[ 5]='c'，dp[ 6 ]=1，结果=10+1=11 得到结果11，这与我们之前的计算一致。 总结 这个问题展示了如何用动态规划统计字符串中的同构子字符串。关键思路是识别连续的相同字符段，每个长度为k的段贡献k* (k+1)/2个同构子串。通过线性动态规划，我们可以在O(n)时间内高效解决这个问题。