统计同值子数组的数目问题（区间DP解法）

题目描述
给定一个长度为n的整数数组nums，统计数组中所有元素值相同的连续子数组的个数。注意：子数组必须是连续的，且所有元素值必须相同。

例如：
输入：nums = [1,1,2,1,1]
输出：8
解释：同值子数组包括：

• 长度为1：[1],[1],[2],[1],[1] (5个)
• 长度为2：[1,1],[1,1] (2个)
• 长度为3：[1,1,1] (1个)
  总共5 + 2 + 1 = 8个

解题思路
这个问题可以用区间动态规划解决。定义dp[i][j]表示子数组nums[i...j]中所有元素值相同的情况下，该子数组内同值子数组的个数。

详细步骤

1. 状态定义

   • dp[i][j]：表示从索引i到j的子数组中，所有元素值相同的情况下，该子数组内同值子数组的个数
   • 如果nums[i...j]不是所有元素值相同，则dp[i][j] = 0

2. 基础情况

   • 当i = j时，单个元素本身就是一个同值子数组，所以dp[i][i] = 1

3. 状态转移方程
   对于区间[i,j]，我们需要考虑两种情况：

   情况1：nums[i] = nums[j] 且 nums[i...j]所有元素值相同

   • 此时整个区间[i,j]是一个同值子数组
   • 此外，我们还要考虑区间内的所有同值子数组
   • 转移方程：dp[i][j] = dp[i][j-1] + 1

   情况2：nums[i] = nums[j] 但区间内元素值不完全相同

   • 我们需要找到所有可能的分割点k，使得[i,k]和[k+1,j]都是同值区间
   • 但更高效的方法是：如果nums[i] = nums[k]且[i,k]和[k+1,j]都是同值区间，那么[i,j]也是同值区间

4. 算法实现

   def count_homogeneous_subarrays(nums):
       n = len(nums)
       if n == 0:
           return 0
   
       # 初始化DP数组
       dp = [[0] * n for _ in range(n)]
       total_count = 0
   
       # 基础情况：单个元素
       for i in range(n):
           dp[i][i] = 1
           total_count += 1
   
       # 遍历所有可能的区间长度（从2到n）
       for length in range(2, n + 1):
           for i in range(n - length + 1):
               j = i + length - 1
   
               # 只有当nums[i] = nums[j]且中间所有元素都相同时才计算
               if nums[i] == nums[j]:
                   # 检查中间所有元素是否都与nums[i]相同
                   all_same = True
                   for k in range(i + 1, j):
                       if nums[k] != nums[i]:
                           all_same = False
                           break
   
                   if all_same:
                       # 整个区间[i,j]是一个新的同值子数组
                       # 加上区间[i,j-1]中的所有同值子数组
                       dp[i][j] = dp[i][j-1] + 1
                       total_count += dp[i][j]
   
       return total_count
   

5. 优化方案
   上面的解法时间复杂度为O(n³)，我们可以优化到O(n²)：

   def count_homogeneous_subarrays_optimized(nums):
       n = len(nums)
       if n == 0:
           return 0
   
       dp = [[0] * n for _ in range(n)]
       total_count = 0
   
       # 基础情况
       for i in range(n):
           dp[i][i] = 1
           total_count += 1
   
       # 预处理相同值区间
       for i in range(n):
           current = nums[i]
           for j in range(i + 1, n):
               if nums[j] == current:
                   dp[i][j] = dp[i][j-1] + 1
                   total_count += dp[i][j]
               else:
                   break  # 遇到不同值就停止
   
       return total_count
   

6. 更进一步的优化（O(n)解法）
   实际上这个问题有更简单的线性解法：

   def count_homogeneous_subarrays_linear(nums):
       if not nums:
           return 0
   
       total_count = 0
       current_count = 1
   
       for i in range(1, len(nums)):
           if nums[i] == nums[i-1]:
               current_count += 1
           else:
               # 计算连续相同值段落的子数组个数
               total_count += current_count * (current_count + 1) // 2
               current_count = 1
   
       # 处理最后一段
       total_count += current_count * (current_count + 1) // 2
   
       return total_count
   

复杂度分析

• 时间复杂度：基础DP解法O(n³)，优化后O(n²)，最优解O(n)
• 空间复杂度：DP解法O(n²)，线性解法O(1)

这个问题的区间DP解法虽然不如线性解法高效，但它很好地展示了区间动态规划的思想和应用场景。