最长数对链的变种：带权值的最长数对链

字数 2705 2025-11-08 20:56:04

最长数对链的变种：带权值的最长数对链

题目描述

给定一个数对数组 pairs，其中每个数对 pairs[i] = [left_i, right_i]，并且 left_i < right_i。我们定义数对链为一系列数对，其中每个后续数对的 left 值严格大于前一个数对的 right 值。与经典的最长数对链问题不同，每个数对带有一个权值 value_i。我们的目标是找出一个数对链，使得链中所有数对的权值之和最大。返回这个最大的权值和。

解题过程

问题分析
我们需要从给定的数对中选出一个序列（链），使得序列满足：
- 对于序列中相邻的两个数对 pairs[i] 和 pairs[j]（i 在 j 之前），有 pairs[i][1] < pairs[j][0]。
- 序列中所有数对的权值之和最大。
这是一个典型的序列型动态规划问题，类似于带权值的最长递增子序列（LIS）问题。我们可以将数对看作一个“活动”，链的规则就是活动之间的依赖关系。
动态规划状态定义
我们定义 dp[i] 表示以第 i 个数对作为结尾的所有可能的数对链中，能够获得的最大权值和。
状态转移方程
如何求解 dp[i]？考虑链中倒数第二个数对。倒数第二个数对可能是 pairs 中排在 i 之前的某个数对 j，并且必须满足 pairs[j][1] < pairs[i][0]。这样，数对 j 和数对 i 就可以连接起来。
因此，状态转移方程为：
dp[i] = max(value_i, max_{j < i 且 pairs[j][1] < pairs[i][0]} { dp[j] + value_i })
其中 value_i 是数对 i 自身的权值。
- value_i 表示链中只包含数对 i 本身的情况。
- max_{j} { dp[j] + value_i } 表示链中包含数对 i 和至少一个在它之前的数对 j 的情况。
初始化
对于每一个数对 i，初始时最差的情况就是链中只有它自己，所以我们可以将 dp 数组初始化为每个数对自身的权值：dp[i] = value_i。
计算顺序与最终答案
- 排序：为了确保当我们处理 dp[i] 时，所有可能出现在数对 i 之前的数对 j（即满足 pairs[j][1] < pairs[i][0] 的 j）都已经被计算过，我们需要先对所有的数对进行排序。一个合理且高效的排序方式是按照每个数对的右端点（right_i）进行升序排序。这样，对于任意 j < i，都有 pairs[j][1] <= pairs[i][1]。虽然不能保证 pairs[j][1] < pairs[i][0]，但至少保证了候选 j 的右端点不会大于 pairs[i][1]，这有利于我们后续的优化。
- 计算：排序后，我们从小到大遍历索引 i（从 0 到 n-1）。对于每个 i，我们遍历所有 j 从 0 到 i-1，检查是否满足 pairs[j][1] < pairs[i][0]。如果满足，则用 dp[j] + value_i 来更新 dp[i]。
- 答案：最终答案不是 dp[n-1]，因为最大权值和链不一定以最后一个数对结尾。答案应该是整个 dp 数组中的最大值，即 max(dp[0], dp[1], ..., dp[n-1])。
复杂度分析与优化（进阶）
- 基础算法复杂度：上述算法需要两重循环，时间复杂度为 O(n²)，空间复杂度为 O(n)。
- 优化思路：当数对数量 n 很大时，O(n²) 可能超时。我们可以利用动态规划 + 二分查找或线段树/树状数组进行优化，将时间复杂度降至 O(n log n)。
  - 核心思想：在计算 dp[i] 时，我们需要快速找到所有右端点小于 pairs[i][0] 的数对中，最大的 dp[j] 值。
  - 实现方法：
    1. 将数对按右端点升序排序。
    2. 我们维护一个数据结构（如数组 ends），其中 ends[k] 表示所有右端点等于某个值的数对中，最大的 dp 值（或者更一般地，记录到目前为止，所有右端点小于等于当前值的数对中，出现过的最大 dp 值）。但实际上，我们通常使用树状数组（Fenwick Tree）或线段树（Segment Tree），键为右端点的值（需要离散化），值为当前区间内最大的 dp 值。
    3. 当我们计算 dp[i] 时：
      - 我们查询该数据结构中，所有键（右端点）小于 pairs[i][0] 的区间内的最大值 max_val。
      - 然后，dp[i] = max(value_i, max_val + value_i)。
      - 接着，我们将当前数对的右端点 pairs[i][1] 作为键，用当前的 dp[i] 值去更新数据结构（即确保数据结构中，键为 pairs[i][1] 的位置的值至少为 dp[i]，因为我们要维护的是区间最大值）。
示例
假设 pairs = [[1, 2], [2, 3], [3, 4]]，权值 value = [5, 6, 7]。
- 排序后数对顺序不变。
- 初始化 dp = [5, 6, 7]。
- 计算 i=0：前面无数对，dp[0] 保持 5。
- 计算 i=1：检查 j=0，pairs[0][1] (2) < pairs[1][0] (2)？不满足（必须严格小于）。所以 dp[1] 保持 6。
- 计算 i=2：检查 j=0，pairs[0][1] (2) < pairs[2][0] (3)，满足。dp[2] = max(7, 5+7=12) = 12。检查 j=1，pairs[1][1] (3) < pairs[2][0] (3)？不满足。
- dp 数组为 [5, 6, 12]，最大值为 12。
- 最大权值和链为 [1,2] -> [3,4]，权值和为 5+7=12。

总结
解决带权值的最长数对链问题，关键在于：

按右端点排序，为动态规划创造无后效性的计算顺序。
定义 dp[i] 为以第 i 个数对结尾的最大权值和。
状态转移时，寻找所有能接在当前数对之前的数对，并取最大值。
对于大规模数据，利用树状数组或线段树优化查询过程。

最长数对链的变种：带权值的最长数对链题目描述给定一个数对数组 pairs ，其中每个数对 pairs[i] = [left_i, right_i] ，并且 left_i < right_i 。我们定义数对链为一系列数对，其中每个后续数对的 left 值严格大于前一个数对的 right 值。与经典的最长数对链问题不同，每个数对带有一个权值 value_i 。我们的目标是找出一个数对链，使得链中所有数对的权值之和最大。返回这个最大的权值和。解题过程问题分析我们需要从给定的数对中选出一个序列（链），使得序列满足：对于序列中相邻的两个数对 pairs[i] 和 pairs[j] （ i 在 j 之前），有 pairs[i][1] < pairs[j][0] 。序列中所有数对的权值之和最大。这是一个典型的序列型动态规划问题，类似于带权值的最长递增子序列（LIS）问题。我们可以将数对看作一个“活动”，链的规则就是活动之间的依赖关系。动态规划状态定义我们定义 dp[i] 表示以第 i 个数对作为结尾的所有可能的数对链中，能够获得的最大权值和。状态转移方程如何求解 dp[i] ？考虑链中倒数第二个数对。倒数第二个数对可能是 pairs 中排在 i 之前的某个数对 j ，并且必须满足 pairs[j][1] < pairs[i][0] 。这样，数对 j 和数对 i 就可以连接起来。因此，状态转移方程为： dp[i] = max(value_i, max_{j < i 且 pairs[j][1] < pairs[i][0]} { dp[j] + value_i }) 其中 value_i 是数对 i 自身的权值。 value_i 表示链中只包含数对 i 本身的情况。 max_{j} { dp[j] + value_i } 表示链中包含数对 i 和至少一个在它之前的数对 j 的情况。初始化对于每一个数对 i ，初始时最差的情况就是链中只有它自己，所以我们可以将 dp 数组初始化为每个数对自身的权值： dp[i] = value_i 。计算顺序与最终答案排序：为了确保当我们处理 dp[i] 时，所有可能出现在数对 i 之前的数对 j （即满足 pairs[j][1] < pairs[i][0] 的 j ）都已经被计算过，我们需要先对所有的数对进行排序。一个合理且高效的排序方式是按照每个数对的右端点（ right_i ）进行升序排序。这样，对于任意 j < i ，都有 pairs[j][1] <= pairs[i][1] 。虽然不能保证 pairs[j][1] < pairs[i][0] ，但至少保证了候选 j 的右端点不会大于 pairs[i][1] ，这有利于我们后续的优化。计算：排序后，我们从小到大遍历索引 i （从 0 到 n-1 ）。对于每个 i ，我们遍历所有 j 从 0 到 i-1 ，检查是否满足 pairs[j][1] < pairs[i][0] 。如果满足，则用 dp[j] + value_i 来更新 dp[i] 。答案：最终答案不是 dp[n-1] ，因为最大权值和链不一定以最后一个数对结尾。答案应该是整个 dp 数组中的最大值，即 max(dp[0], dp[1], ..., dp[n-1]) 。复杂度分析与优化（进阶）基础算法复杂度：上述算法需要两重循环，时间复杂度为 O(n²)，空间复杂度为 O(n)。优化思路：当数对数量 n 很大时，O(n²) 可能超时。我们可以利用动态规划 + 二分查找或线段树/树状数组进行优化，将时间复杂度降至 O(n log n)。核心思想：在计算 dp[i] 时，我们需要快速找到所有右端点小于 pairs[i][0] 的数对中，最大的 dp[j] 值。实现方法：将数对按右端点升序排序。我们维护一个数据结构（如数组 ends ），其中 ends[k] 表示所有右端点等于某个值的数对中，最大的 dp 值（或者更一般地，记录到目前为止，所有右端点小于等于当前值的数对中，出现过的最大 dp 值）。但实际上，我们通常使用树状数组（Fenwick Tree）或线段树（Segment Tree），键为右端点的值（需要离散化），值为当前区间内最大的 dp 值。当我们计算 dp[i] 时：我们查询该数据结构中，所有键（右端点）小于 pairs[i][0] 的区间内的最大值 max_val 。然后， dp[i] = max(value_i, max_val + value_i) 。接着，我们将当前数对的右端点 pairs[i][1] 作为键，用当前的 dp[i] 值去更新数据结构（即确保数据结构中，键为 pairs[i][1] 的位置的值至少为 dp[i] ，因为我们要维护的是区间最大值）。示例假设 pairs = [[1, 2], [2, 3], [3, 4]] ，权值 value = [5, 6, 7] 。排序后数对顺序不变。初始化 dp = [5, 6, 7] 。计算 i=0 ：前面无数对， dp[0] 保持 5。计算 i=1 ：检查 j=0 ， pairs[0][1] (2) < pairs[1][0] (2) ？不满足（必须严格小于）。所以 dp[1] 保持 6。计算 i=2 ：检查 j=0 ， pairs[0][1] (2) < pairs[2][0] (3) ，满足。 dp[2] = max(7, 5+7=12) = 12 。检查 j=1 ， pairs[1][1] (3) < pairs[2][0] (3) ？不满足。 dp 数组为 [5, 6, 12] ，最大值为 12。最大权值和链为 [1,2] -> [3,4] ，权值和为 5+7=12。总结解决带权值的最长数对链问题，关键在于：按右端点排序，为动态规划创造无后效性的计算顺序。定义 dp[i] 为以第 i 个数对结尾的最大权值和。状态转移时，寻找所有能接在当前数对之前的数对，并取最大值。对于大规模数据，利用树状数组或线段树优化查询过程。