dp[i] = max(dp[i-1], weight_i + dp[p(i)])

带权重的活动选择问题（Weighted Interval Scheduling） 题目描述 给定一系列活动（或区间），每个活动有一个开始时间、结束时间和权重（价值）。目标是选择一组互不重叠的活动，使得总权重最大。 形式化描述： 输入： n 个活动，每个活动 i 表示为 (start_i, end_i, weight_i) 输出：最大总权重，且所选活动之间时间不重叠（即任意两个活动 i 和 j 满足 end_i ≤ start_j 或 end_j ≤ start_i ）。 解题过程 步骤 1：预处理与排序 首先按结束时间将所有活动升序排序。这样便于判断哪些活动在某个活动之前结束，从而避免重叠。 排序后，活动编号为 1, 2, ..., n （按结束时间从早到晚）。 步骤 2：定义动态规划状态 设 dp[i] 表示考虑前 i 个活动（按结束时间排序后）时，能获得的最大权重。 我们需要决定是否选择第 i 个活动： 不选第 i 个活动 ： dp[i] = dp[i-1] 选择第 i 个活动 ：则需要找到最后一个不与第 i 个活动重叠的活动 p(i) ，即满足 end_j ≤ start_i 的最大 j 。此时 dp[i] = weight_i + dp[p(i)] 因此状态转移方程为： 步骤 3：计算 p(i) 对每个活动 i ，二分查找最大的 j 使得 end_j ≤ start_i 。 如果不存在这样的 j ，则 p(i) = 0 ，且 dp[0] = 0 。 预处理 p(i) 的时间复杂度为 O(n log n) （排序 + 二分查找）。 步骤 4：递推计算 dp[ i ] 按 i = 1 to n 顺序计算 dp[i] ： 初始化 dp[0] = 0 对于每个 i ： 若 p(i) = 0 ，则 dp[i] = max(dp[i-1], weight_i) 否则 dp[i] = max(dp[i-1], weight_i + dp[p(i)]) 最终答案： dp[n] 步骤 5：示例演示 假设活动如下（已按结束时间排序）： | i | start | end | weight | p(i) | |---|-------|-----|--------|------| | 1 | 1 | 3 | 2 | 0 | | 2 | 2 | 5 | 4 | 0 | | 3 | 4 | 6 | 4 | 1 | | 4 | 5 | 7 | 7 | 1 | | 5 | 6 | 9 | 2 | 3 | 计算过程： dp[0] = 0 i=1 ： p(1)=0 ， dp[1] = max(0, 2) = 2 i=2 ： p(2)=0 ， dp[2] = max(2, 4) = 4 i=3 ： p(3)=1 ， dp[3] = max(4, 4+dp[1]=4+2=6) = 6 i=4 ： p(4)=1 ， dp[4] = max(6, 7+dp[1]=7+2=9) = 9 i=5 ： p(5)=3 ， dp[5] = max(9, 2+dp[3]=2+6=8) = 9 最大权重为 9 （选择活动 1 和 4）。 步骤 6：重构解方案 若要输出具体选择了哪些活动，可以反向追踪： 从 i=n 开始，若 dp[i] != dp[i-1] ，说明选择了活动 i ，然后跳转到 p(i) ；否则继续检查 i-1 。 在上例中： dp[5]=9 ， dp[4]=9 ，说明未选活动 5 dp[4]=9 ， dp[3]=6 ，说明选了活动 4，跳至 p(4)=1 dp[1]=2 ， dp[0]=0 ，说明选了活动 1，结束 因此选择活动 1 和 4。 总结 该算法时间复杂度为 O(n log n) （排序 + 二分预处理 p(i) + 线性 DP），是解决带权重活动选择问题的标准方法。