区间动态规划例题：统计同值子数组的数目问题（进阶版）

字数 1032 2025-11-18 17:32:55

区间动态规划例题：统计同值子数组的数目问题（进阶版）

题目描述

给定一个整数数组 nums，统计所有元素都相同的连续子数组的个数。例如，数组 [1,1,2,1,1] 中，所有元素相同的连续子数组包括：

长度为1: [1], [1], [2], [1], [1] (5个)
长度为2: [1,1], [1,1] (2个)
长度为3: [1,1,2] 不是（因为元素不同），[2,1,1] 不是
长度为4: 无
长度为5: 无
总数为 5 + 2 = 7

解题思路

这个问题可以用区间动态规划解决。我们定义 dp[i][j] 表示子数组 nums[i..j] 是否所有元素都相同。

详细解题步骤

状态定义
- dp[i][j] 表示子数组 nums[i..j] 的所有元素是否相同
- 如果相同，dp[i][j] = true，否则为 false
状态转移方程
- 基本情况：当 i = j 时，单个元素肯定相同，dp[i][i] = true
- 对于区间 [i, j] (i < j)：
  dp[i][j] = dp[i][j-1] && (nums[j] == nums[j-1])
  或者
  dp[i][j] = dp[i+1][j] && (nums[i] == nums[i+1])
初始化
- 所有长度为1的子数组都满足条件：dp[i][i] = true
计算顺序
- 按区间长度从小到大计算
- 先计算所有长度为1的区间，然后长度为2，依此类推
统计结果
- 遍历所有 dp[i][j]，统计其中为 true 的个数

具体计算过程

以数组 [1,1,2,1,1] 为例：

步骤1：初始化长度为1的区间

dp[0][0] = true  (子数组 [1])
dp[1][1] = true  (子数组 [1])  
dp[2][2] = true  (子数组 [2])
dp[3][3] = true  (子数组 [1])
dp[4][4] = true  (子数组 [1])
当前计数：5

步骤2：计算长度为2的区间

dp[0][1] = dp[0][0] && (nums[1]==nums[0]) = true && (1==1) = true  ([1,1])
dp[1][2] = dp[1][1] && (nums[2]==nums[1]) = true && (2==1) = false ([1,2])
dp[2][3] = dp[2][2] && (nums[3]==nums[2]) = true && (1==2) = false ([2,1])
dp[3][4] = dp[3][3] && (nums[4]==nums[3]) = true && (1==1) = true  ([1,1])
当前计数：5 + 2 = 7

步骤3：计算长度为3的区间

dp[0][2] = dp[0][1] && (nums[2]==nums[1]) = true && (2==1) = false ([1,1,2])
dp[1][3] = dp[1][2] && (nums[3]==nums[2]) = false && (1==2) = false ([1,2,1])
dp[2][4] = dp[2][3] && (nums[4]==nums[3]) = false && (1==1) = false ([2,1,1])
当前计数：7 + 0 = 7

步骤4：计算长度为4的区间

dp[0][3] = dp[0][2] && (nums[3]==nums[2]) = false && (1==2) = false ([1,1,2,1])
dp[1][4] = dp[1][3] && (nums[4]==nums[3]) = false && (1==1) = false ([1,2,1,1])
当前计数：7 + 0 = 7

步骤5：计算长度为5的区间

dp[0][4] = dp[0][3] && (nums[4]==nums[3]) = false && (1==1) = false ([1,1,2,1,1])
当前计数：7 + 0 = 7

最终结果：7

算法优化

实际上，我们可以用更简单的方法：遍历数组，统计连续相同元素的长度，然后用数学公式计算。对于长度为 k 的连续相同元素段，可以形成 k*(k+1)/2 个满足条件的子数组。

对于 [1,1,2,1,1]：

前2个1：长度2，贡献 2×3/2 = 3
中间的2：长度1，贡献 1×2/2 = 1
后2个1：长度2，贡献 2×3/2 = 3
总数：3 + 1 + 3 = 7

这种方法时间复杂度 O(n)，空间复杂度 O(1)，比动态规划更优。

区间动态规划例题：统计同值子数组的数目问题（进阶版）题目描述给定一个整数数组 nums，统计所有元素都相同的连续子数组的个数。例如，数组 [ 1,1,2,1,1 ] 中，所有元素相同的连续子数组包括：长度为1: [ 1], [ 1], [ 2], [ 1], [ 1 ] (5个) 长度为2: [ 1,1], [ 1,1 ] (2个) 长度为3: [ 1,1,2] 不是（因为元素不同），[ 2,1,1 ] 不是长度为4: 无长度为5: 无总数为 5 + 2 = 7 解题思路这个问题可以用区间动态规划解决。我们定义 dp[ i][ j] 表示子数组 nums[ i..j ] 是否所有元素都相同。详细解题步骤状态定义 dp[ i][ j] 表示子数组 nums[ i..j ] 的所有元素是否相同如果相同，dp[ i][ j ] = true，否则为 false 状态转移方程基本情况：当 i = j 时，单个元素肯定相同，dp[ i][ i ] = true 对于区间 [ i, j] (i < j)： dp[ i][ j] = dp[ i][ j-1] && (nums[ j] == nums[ j-1 ]) 或者 dp[ i][ j] = dp[ i+1][ j] && (nums[ i] == nums[ i+1 ]) 初始化所有长度为1的子数组都满足条件：dp[ i][ i ] = true 计算顺序按区间长度从小到大计算先计算所有长度为1的区间，然后长度为2，依此类推统计结果遍历所有 dp[ i][ j ]，统计其中为 true 的个数具体计算过程以数组 [ 1,1,2,1,1 ] 为例：步骤1：初始化长度为1的区间步骤2：计算长度为2的区间步骤3：计算长度为3的区间步骤4：计算长度为4的区间步骤5：计算长度为5的区间最终结果：7 算法优化实际上，我们可以用更简单的方法：遍历数组，统计连续相同元素的长度，然后用数学公式计算。对于长度为 k 的连续相同元素段，可以形成 k* (k+1)/2 个满足条件的子数组。对于 [ 1,1,2,1,1 ]：前2个1：长度2，贡献 2×3/2 = 3 中间的2：长度1，贡献 1×2/2 = 1 后2个1：长度2，贡献 2×3/2 = 3 总数：3 + 1 + 3 = 7 这种方法时间复杂度 O(n)，空间复杂度 O(1)，比动态规划更优。