区间动态规划例题：带权重的区间调度问题（最大化总权重） 我们先来理解这个问题的描述： 给定若干个区间，每个区间有开始时间、结束时间以及一个权重（表示这个区间的价值）。我们需要选择若干 不重叠 的区间，使得它们的 总权重最大 。这是经典区间调度问题（选择最多不重叠区间）的加权版本，可以用区间DP解决。 第一步：问题形式化 假设有 \(n\) 个区间，每个区间表示为 \((s_ i, e_ i, w_ i)\)，其中 \(s_ i\) 是开始时间，\(e_ i\) 是结束时间，\(w_ i\) 是权重。目标：选择若干个互不重叠的区间，最大化总权重。 注意：区间是闭区间还是开区间通常不影响解法，常见处理是按照结束时间排序后定义不重叠条件。这里我们假设区间是闭区间，不重叠要求前一个区间的结束时间小于后一个区间的开始时间。 第二步：排序 为了方便动态规划，我们 按照结束时间 将区间升序排序。 排序后，区间编号为 \(1\) 到 \(n\)，每个区间记作 \((s_ i, e_ i, w_ i)\)，且 \(e_ 1 \le e_ 2 \le \dots \le e_ n\)。 这样，当我们考虑区间 \(i\) 时，所有与它不冲突的区间都在它前面。 第三步：定义状态 一种常见状态定义是： \(dp[ i]\) 表示 考虑前 i 个区间 ，且 必须选择第 i 个区间 时，能获得的最大权重。 最终答案是 \(\max(dp[ i ])\) 对所有 \(i\)。 为什么这样定义？因为如果我们不强制选某个区间，状态转移时需要考虑不选的情况，会复杂一些。这个定义可以直接用不冲突的前驱来转移。 第四步：状态转移 对于 \(dp[ i]\)，我们要找前一个可以选择的区间 \(j\)，满足 \(e_ j \le s_ i\)（不重叠），那么： \[ dp[ i] = w_ i + \max\{ dp[ j] \mid e_ j \le s_ i \} \] 如果不存在这样的 \(j\)，则 \(dp[ i] = w_ i\)（只选自己）。 为了快速找到满足条件的 \(j\) 中 dp 最大值，我们可以预处理： 对每个 \(i\)，用二分查找找到最后一个满足 \(e_ j \le s_ i\) 的区间编号 \(p(i)\)。 那么： \[ dp[ i] = w_ i + \max\{ dp[ 1], dp[ 2], \dots, dp[ p(i) ] \} \] 记 \(preMax[ k] = \max(dp[ 1..k ])\)，则： \[ dp[ i] = w_ i + (p(i) \ge 1 ? preMax[ p(i) ] : 0) \] 第五步：计算与答案 初始化 \(dp[ 0 ]=0\) 方便处理。 对 \(i=1\) 到 \(n\)： 找到 \(p(i)\)（在排序后的区间数组中，二分查找最后一个 \(e_ j \le s_ i\) 的 \(j\)）。 \(dp[ i] = w_ i + preMax[ p(i) ]\)。 更新 \(preMax[ i] = \max(preMax[ i-1], dp[ i ])\)。 最终答案就是 \(preMax[ n]\)，也就是所有 \(dp[ i ]\) 的最大值。 第六步：示例 假设有区间： 1: (1,3,5) 2: (2,5,6) 3: (4,6,4) 4: (6,7,3) 按结束时间排序后顺序不变（这里结束时间已升序）。 i=1: s1=1,e1=3,w1=5, p(1) 没有 e_ j ≤ 1? 没有，p(1)=0, dp[ 1]=5, preMax[ 1 ]=5 i=2: s2=2, 找 e_ j ≤ 2 → e1=3>2, 没有，p(2)=0, dp[ 2]=6, preMax[ 2 ]=6 i=3: s3=4, 找 e_ j ≤ 4 → e1=3≤4, e2=5>4, 所以 p(3)=1, dp[ 3]=4+preMax[ 1]=4+5=9, preMax[ 3 ]=9 i=4: s4=6, 找 e_ j ≤ 6 → e3=6≤6, 所以 p(4)=3, dp[ 4]=3+preMax[ 3]=3+9=12, preMax[ 4 ]=12 答案 = 12。 对应选择区间1和3和4，权重5+4+3=12，不冲突。 第七步：复杂度 排序 O(n log n)。 对每个 i 二分查找 p(i) 是 O(log n)，总 O(n log n)。 空间 O(n)。 这就是带权区间调度的完整区间DP解法。它的核心是将区间按结束时间排序，定义以某个区间结尾的最优解，然后利用前缀最大值快速转移。