区间动态规划例题：合唱队问题
字数 2087 2025-10-26 09:00:43

区间动态规划例题：合唱队问题

题目描述
合唱队有 \(n\) 位同学站成一排，每个同学有一个身高 \(h_i\)。现在需要选出若干名同学组成一个合唱队，要求合唱队中身高从左到右先严格递增再严格递减（即存在一个“顶点”，左侧递增，右侧递减）。例如：身高序列为 [1, 2, 3, 2, 1] 是合法的，但 [1, 2, 2, 1] 不合法（不允许相邻相等）。问至少需要移除多少名同学（或最多能保留多少名同学）才能使得剩余同学构成合唱队？

输入示例

n = 8
height = [1, 2, 3, 4, 5, 6, 7, 8]

输出示例
至少移除 7 人（只能保留 1 人，因为严格递增后无法递减）。

解题思路

问题可转化为：求最长的“先增后减”子序列长度，然后用总人数减去该长度即为最少移除人数。
关键观察：

  1. 合唱队形状类似于一个“山峰”，每个人在队伍中可能是左侧递增段或右侧递减段的一部分。
  2. 对于位置 \(i\)，若其作为山峰顶点，则需计算：
    • 从左到以 \(i\) 结尾的最长递增子序列（LIS）长度（记为 left[i]）
    • 从右到以 \(i\) 结尾的最长递减子序列（LDS）长度（记为 right[i]）
  3. 顶点 \(i\) 对应的合唱队长度为 left[i] + right[i] - 1（因为顶点被重复计算一次）。

步骤详解

步骤 1：计算每个位置的左侧 LIS 长度

定义 left[i] 为以 height[i] 结尾的最长严格递增子序列长度。

  • 初始化：left[i] = 1（每个位置本身构成长度为 1 的递增序列）
  • 对于每个 \(i\)（0 到 n-1），遍历所有 \(j < i\)：
    • 若 height[j] < height[i]，则 left[i] = max(left[i], left[j] + 1)

示例（身高数组 [1, 3, 2, 5, 4]）：

  • i=0: left[0]=1
  • i=1: j=0, height[0]<height[1] → left[1]=max(1, left[0]+1)=2
  • i=2: j=0, height[0]<height[2] → left[2]=max(1, left[0]+1)=2；j=1 不满足（3>2）
  • i=3: j=0 → left[3]=2; j=1 → left[3]=3; j=2 → left[3]=3
  • i=4: j=0 → 2; j=1 → 不满足; j=2 → 2; j=3 → 不满足 → left[4]=2

得到 left = [1, 2, 2, 3, 2]

步骤 2：计算每个位置的右侧 LDS 长度

定义 right[i] 为从右向左以 height[i] 结尾的最长严格递减子序列长度（等价于反向数组的 LIS）。

  • 初始化：right[i] = 1
  • 从右向左遍历 \(i\)（n-1 到 0），对于每个 \(j > i\)：
    • 若 height[j] < height[i]，则 right[i] = max(right[i], right[j] + 1)

示例（同一数组）：

  • i=4: right[4]=1
  • i=3: j=4, height[4]<height[3] → right[3]=max(1, right[4]+1)=2
  • i=2: j=3 不满足（5>2）；j=4 满足（4>2）→ right[2]=max(1, right[4]+1)=2
  • i=1: j=2 满足（2<3）→ right[1]=max(1, right[2]+1)=3；j=3 不满足；j=4 满足 → right[1]=3
  • i=0: j=1 满足 → right[0]=max(1, right[1]+1)=4；j=2 满足 → 4；j=3 不满足；j=4 满足 → 4

得到 right = [4, 3, 2, 2, 1]

步骤 3：计算每个顶点对应的合唱队长度

对于每个 \(i\)，合唱队长度 = left[i] + right[i] - 1

  • i=0: 1+4-1=4
  • i=1: 2+3-1=4
  • i=2: 2+2-1=3
  • i=3: 3+2-1=4
  • i=4: 2+1-1=2

最长合唱队长度 = 4

步骤 4：计算最少移除人数

最少移除人数 = n - 最长合唱队长度 = 5 - 4 = 1

算法复杂度

  • 时间复杂度：\(O(n^2)\)（两层循环计算 LIS/LDS）
  • 空间复杂度：\(O(n)\)（存储 left 和 right 数组）

优化提示：若用二分查找优化 LIS/LDS 计算，可降至 \(O(n \log n)\)，但需注意严格递增/递减的处理。

总结

合唱队问题是区间动态规划的变形，通过将问题分解为左侧递增和右侧递减两个子问题，结合 LIS 思想求解。核心在于枚举每个顶点，计算其左右两边的合法长度，最终找到最优解。

区间动态规划例题：合唱队问题 题目描述 合唱队有 \( n \) 位同学站成一排，每个同学有一个身高 \( h_ i \)。现在需要选出若干名同学组成一个合唱队，要求合唱队中身高从左到右 先严格递增再严格递减 （即存在一个“顶点”，左侧递增，右侧递减）。例如：身高序列为 [1, 2, 3, 2, 1] 是合法的，但 [1, 2, 2, 1] 不合法（不允许相邻相等）。问至少需要 移除多少名同学 （或最多能保留多少名同学）才能使得剩余同学构成合唱队？ 输入示例 输出示例 至少移除 7 人（只能保留 1 人，因为严格递增后无法递减）。 解题思路 问题可转化为：求最长的“先增后减”子序列长度，然后用总人数减去该长度即为最少移除人数。 关键观察 ： 合唱队形状类似于一个“山峰”，每个人在队伍中可能是左侧递增段或右侧递减段的一部分。 对于位置 \( i \)，若其作为山峰顶点，则需计算： 从左到以 \( i \) 结尾的 最长递增子序列（LIS）长度 （记为 left[i] ） 从右到以 \( i \) 结尾的 最长递减子序列（LDS）长度 （记为 right[i] ） 顶点 \( i \) 对应的合唱队长度为 left[i] + right[i] - 1 （因为顶点被重复计算一次）。 步骤详解 步骤 1：计算每个位置的左侧 LIS 长度 定义 left[i] 为以 height[i] 结尾的最长严格递增子序列长度。 初始化： left[i] = 1 （每个位置本身构成长度为 1 的递增序列） 对于每个 \( i \)（0 到 n-1），遍历所有 \( j < i \)： 若 height[j] < height[i] ，则 left[i] = max(left[i], left[j] + 1) 示例 （身高数组 [1, 3, 2, 5, 4] ）： i=0: left[ 0 ]=1 i=1: j=0, height[ 0]<height[ 1] → left[ 1]=max(1, left[ 0 ]+1)=2 i=2: j=0, height[ 0]<height[ 2] → left[ 2]=max(1, left[ 0 ]+1)=2；j=1 不满足（3>2） i=3: j=0 → left[ 3]=2; j=1 → left[ 3]=3; j=2 → left[ 3 ]=3 i=4: j=0 → 2; j=1 → 不满足; j=2 → 2; j=3 → 不满足 → left[ 4 ]=2 得到 left = [ 1, 2, 2, 3, 2 ] 步骤 2：计算每个位置的右侧 LDS 长度 定义 right[i] 为从右向左以 height[i] 结尾的最长严格递减子序列长度（等价于反向数组的 LIS）。 初始化： right[i] = 1 从右向左遍历 \( i \)（n-1 到 0），对于每个 \( j > i \)： 若 height[j] < height[i] ，则 right[i] = max(right[i], right[j] + 1) 示例 （同一数组）： i=4: right[ 4 ]=1 i=3: j=4, height[ 4]<height[ 3] → right[ 3]=max(1, right[ 4 ]+1)=2 i=2: j=3 不满足（5>2）；j=4 满足（4>2）→ right[ 2]=max(1, right[ 4 ]+1)=2 i=1: j=2 满足（2<3）→ right[ 1]=max(1, right[ 2]+1)=3；j=3 不满足；j=4 满足 → right[ 1 ]=3 i=0: j=1 满足 → right[ 0]=max(1, right[ 1 ]+1)=4；j=2 满足 → 4；j=3 不满足；j=4 满足 → 4 得到 right = [ 4, 3, 2, 2, 1 ] 步骤 3：计算每个顶点对应的合唱队长度 对于每个 \( i \)，合唱队长度 = left[i] + right[i] - 1 i=0: 1+4-1=4 i=1: 2+3-1=4 i=2: 2+2-1=3 i=3: 3+2-1=4 i=4: 2+1-1=2 最长合唱队长度 = 4 步骤 4：计算最少移除人数 最少移除人数 = n - 最长合唱队长度 = 5 - 4 = 1 算法复杂度 时间复杂度：\( O(n^2) \)（两层循环计算 LIS/LDS） 空间复杂度：\( O(n) \)（存储 left 和 right 数组） 优化提示 ：若用二分查找优化 LIS/LDS 计算，可降至 \( O(n \log n) \)，但需注意严格递增/递减的处理。 总结 合唱队问题是区间动态规划的变形，通过将问题分解为 左侧递增 和 右侧递减 两个子问题，结合 LIS 思想求解。核心在于枚举每个顶点，计算其左右两边的合法长度，最终找到最优解。