区间动态规划例题：统计同构子字符串的数目问题 题目描述 给定一个字符串 s，你需要统计其中同构子字符串的数目。同构子字符串定义为：如果一个子字符串的所有字符都相同，那么它就是同构的。例如，字符串 "aaa" 有 6 个同构子字符串："a", "a", "a", "aa", "aa", "aaa"。 注意：子字符串是字符串中连续的字符序列。即使内容相同，只要起始和结束位置不同，就被视为不同的子字符串。 解题思路 这个问题可以用简单的数学方法解决，但为了练习区间动态规划，我们将使用 DP 方法。基本思想是定义 dp[ i][ j] 表示子串 s[ i:j+1 ] 是否是同构的（即所有字符相同），然后统计所有满足条件的子串。 详细解题步骤 定义状态 定义 dp[ i][ j] 为一个布尔值，表示子字符串 s[ i...j ]（包含 i 和 j）是否是同构的（即所有字符相同）。 状态转移方程 考虑如何判断 s[ i...j ] 是否同构： 如果 i == j（子串只有一个字符），那么它一定是同构的。 如果 j > i，那么 s[ i...j ] 是同构的条件是： s[ i] == s[ j ]（首尾字符相同） 并且 s[ i...j-1] 是同构的（即 dp[ i][ j-1 ] 为真） 这是因为如果整个字符串所有字符都相同，那么去掉最后一个字符后的子串也必须所有字符相同，并且最后一个字符要与前面的字符相同。 所以状态转移方程为： 当 i == j 时：dp[ i][ j ] = true 当 j > i 时：dp[ i][ j] = (s[ i] == s[ j]) && dp[ i][ j-1 ] 初始化 所有长度为 1 的子串都是同构的：dp[ i][ i ] = true（对于所有 i） 计算顺序 由于计算 dp[ i][ j] 需要用到 dp[ i][ j-1 ]，我们应该按照子串长度从小到大进行计算： 先计算所有长度为 1 的子串 然后计算长度为 2 的子串 接着计算长度为 3 的子串 ... 最后计算长度为 n 的整个字符串 统计结果 遍历整个 dp 表，统计所有 dp[ i][ j ] 为 true 的个数，这就是同构子字符串的总数。 复杂度分析 时间复杂度：O(n²)，需要填充 n×n 的 DP 表 空间复杂度：O(n²)，需要存储 DP 表 示例演示 以字符串 "aab" 为例： 初始化 dp 表（3×3）： dp[ 0][ 0 ] = true ("a") dp[ 1][ 1 ] = true ("a") dp[ 2][ 2 ] = true ("b") 计算长度为 2 的子串： dp[ 0][ 1]：s[ 0]='a' == s[ 1]='a' 且 dp[ 0][ 0 ]=true → true ("aa") dp[ 1][ 2]：s[ 1]='a' ≠ s[ 2 ]='b' → false ("ab") 计算长度为 3 的子串： dp[ 0][ 2]：s[ 0]='a' ≠ s[ 2 ]='b' → false ("aab") 统计结果：dp[ 0][ 0], dp[ 1][ 1], dp[ 2][ 2], dp[ 0][ 1 ] 为 true，共 4 个同构子串。 实际同构子串有："a"(0-0), "a"(1-1), "aa"(0-1), "b"(2-2)，确实为 4 个。 优化思路 实际上，这个问题有 O(n) 的简单解法：遍历字符串，统计连续相同字符的区间，对于长度为 k 的连续相同字符区间，它包含的同构子串数为 k×(k+1)/2。但 DP 方法帮助我们理解了区间DP的思维模式。