区间动态规划例题：统计同值子数组的数目问题 题目描述 给定一个整数数组nums，统计数组中所有元素值相同的连续子数组的个数。例如，对于数组[ 1,1,2,1,1 ]，其中： 单个元素的子数组[ 1]、[ 1]、[ 2]、[ 1]、[ 1 ]都是同值子数组 两个元素的子数组[ 1,1]、[ 1,1 ]也是同值子数组 三个元素的子数组[ 1,1,1 ]也是同值子数组 总共有5 + 2 + 1 = 8个同值子数组。 解题思路 这个问题可以用区间动态规划来解决。我们定义dp[ i][ j]表示从位置i到位置j的子数组是否是同值子数组。如果是，dp[ i][ j ] = 1，否则为0。 详细解题步骤 定义状态 设dp[ i][ j]表示子数组nums[ i...j ]是否所有元素都相同（1表示是，0表示否） 状态转移方程 基本情况：当i = j时，单个元素总是同值的，所以dp[ i][ i ] = 1 递归情况：对于i < j，dp[ i][ j ] = 1当且仅当： nums[ i] == nums[ j] 且 dp[ i][ j-1 ] == 1 也就是说，只有当右端点元素等于左端点元素，且去掉右端点后的子数组也是同值的，整个子数组才是同值的 初始化 所有长度为1的子数组都是同值的：dp[ i][ i ] = 1 计算顺序 按子数组长度从小到大计算： 先计算所有长度为1的子数组 再计算长度为2，3，...，n的子数组 结果统计 最终结果是所有dp[ i][ j ] = 1的(i,j)对的数量 具体示例分析 以数组[ 1,1,2,1,1 ]为例： 初始化 （长度为1）： dp[ 0][ 0] = 1, dp[ 1][ 1] = 1, dp[ 2][ 2] = 1, dp[ 3][ 3] = 1, dp[ 4][ 4 ] = 1 长度为2 ： [ 0,1]: nums[ 0]=1, nums[ 1]=1, 相同且dp[ 0][ 0]=1 → dp[ 0][ 1 ] = 1 [ 1,2]: nums[ 1]=1, nums[ 2]=2, 不同 → dp[ 1][ 2 ] = 0 [ 2,3]: nums[ 2]=2, nums[ 3]=1, 不同 → dp[ 2][ 3 ] = 0 [ 3,4]: nums[ 3]=1, nums[ 4]=1, 相同且dp[ 3][ 3]=1 → dp[ 3][ 4 ] = 1 长度为3 ： [ 0,2]: nums[ 0]=1, nums[ 2]=2, 不同 → dp[ 0][ 2 ] = 0 [ 1,3]: nums[ 1]=1, nums[ 3]=1, 相同但dp[ 1][ 2]=0 → dp[ 1][ 3 ] = 0 [ 2,4]: nums[ 2]=2, nums[ 4]=1, 不同 → dp[ 2][ 4 ] = 0 长度为4 ： [ 0,3]: nums[ 0]=1, nums[ 3]=1, 相同但dp[ 0][ 2]=0 → dp[ 0][ 3 ] = 0 [ 1,4]: nums[ 1]=1, nums[ 4]=1, 相同但dp[ 1][ 3]=0 → dp[ 1][ 4 ] = 0 长度为5 ： [ 0,4]: nums[ 0]=1, nums[ 4]=1, 相同但dp[ 0][ 3]=0 → dp[ 0][ 4 ] = 0 最终统计 ：所有dp[ i][ j ] = 1的个数为5（长度1）+ 2（长度2）= 7 算法优化 实际上，我们可以用更简单的方法：遍历数组，统计每个连续相同元素的段，对于长度为k的连续段，它能贡献的同值子数组个数为k×(k+1)/2。 优化后算法步骤 ： 遍历数组，找到所有连续的相同元素段 对于每个长度为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) 这种方法比区间DP更高效，但区间DP的解法展示了如何用动态规划的思路来解决这类问题。