线性动态规划：最长数对链（Longest Increasing Pair Chain）的变种——带权值的最长数对链（Maximum Sum Increasing Pair Chain）

题目描述
给定一个数组 pairs，其中每个 pairs[i] = [a_i, b_i] 表示一个数对，并且每个数对具有一个权值 value[i]。我们希望找到一个严格递增的数对链，使得链中每个数对 (a_i, b_i) 满足：

• 对于链中任意两个相邻的数对 (a_j, b_j) 和 (a_k, b_k)（其中 (a_j, b_j) 出现在 (a_k, b_k) 之前），有 a_j < a_k 且 b_j < b_k。
• 链中的数对可以不连续选取（即可以从原数组中跳过某些数对）。

目标是最大化所选数对的权值之和，而不是单纯最大化链的长度。

注意：

• 数对的两个维度都需要严格递增（即前一个数对的 a 和 b 都分别小于后一个数对的 a 和 b）。
• 这是经典“最长数对链”问题的加权版本，原问题只要求最大化链的长度（每个数对权值为1）。

解题思路

这个问题可以通过动态规划解决。我们将问题分解为以下步骤：

1. 排序预处理
   为了满足“前一个数对的两个值都小于后一个数对”，我们先将所有数对按照第一个维度 a 升序排序。如果第一个维度相同，则按第二个维度 b 升序排序。
   排序后，我们只需要保证在选取的链中，后一个数对的 b 大于前一个数对的 b 即可（因为 a 已经非递减，而由于严格递增要求，当 a 相等时，两个数对不可能同时被选，所以实际上我们只需比较 b 是否严格递增）。

2. 定义状态
   设 dp[i] 表示以第 i 个数对结尾的、权值和最大的严格递增数对链的权值和。
   注意：dp[i] 不一定包含前 i 个元素中的最大权值链，但我们可以通过遍历所有 i 来找到全局最大值。

3. 状态转移
   对于每个 i，我们考虑所有 j < i，检查 pairs[j] 是否能在 pairs[i] 之前（即满足 a_j < a_i 且 b_j < b_i）。
   如果满足，则：

   dp[i] = max(dp[i], dp[j] + value[i])
   

   如果不满足，则 dp[i] 至少为 value[i] 本身（即只选第 i 个数对）。

4. 初始化
   dp[i] = value[i]，因为至少可以选择只包含第 i 个数对的链。

5. 最终答案
   取所有 dp[i] 的最大值。

6. 复杂度优化
   如果直接对每个 i 遍历所有 j < i，时间复杂度是 O(n²)，其中 n 为数对个数。这在 n 较大时可能效率较低，但通常可以接受。如果需要优化，可以考虑用树状数组或线段树进行二维偏序优化，但本题我们先讲解基础动态规划解法。

详细步骤

步骤1：排序
将数对按 a 升序排序，如果 a 相同则按 b 升序排序。

示例输入：

pairs = [[1,2], [3,4], [2,3], [4,5]]
values = [3, 7, 5, 9]

排序后（这里已按 a 排序，无需调整）：

pairs = [[1,2], [2,3], [3,4], [4,5]]
values = [3, 5, 7, 9]  // 注意 values 随着 pairs 一起排序

步骤2：初始化 dp 数组
dp[i] = values[i]

步骤3：状态转移
对于每个 i 从 0 到 n-1：

• 遍历所有 j 从 0 到 i-1：
  • 如果 pairs[j][0] < pairs[i][0] 且 pairs[j][1] < pairs[i][1]，则更新：
    dp[i] = max(dp[i], dp[j] + values[i])

以示例计算：

• i=0: dp[0] = 3
• i=1: 检查 j=0: (1,2) 和 (2,3) 满足 1<2 且 2<3，所以 dp[1] = max(5, 3+5=8) = 8
• i=2: 检查 j=0: (1,2) 和 (3,4) 满足 → dp[2] = max(7, 3+7=10) = 10
  检查 j=1: (2,3) 和 (3,4) 满足 → dp[2] = max(10, 8+7=15) = 15
• i=3: 检查 j=0: (1,2) 和 (4,5) 满足 → dp[3] = max(9, 3+9=12) = 12
  检查 j=1: (2,3) 和 (4,5) 满足 → dp[3] = max(12, 8+9=17) = 17
  检查 j=2: (3,4) 和 (4,5) 满足 → dp[3] = max(17, 15+9=24) = 24

步骤4：取最大值
max(dp) = max(3, 8, 15, 24) = 24
对应链：(1,2) → (2,3) → (3,4) → (4,5)，权值和 = 3+5+7+9 = 24。

边界情况与注意事项

1. 如果所有数对都无法形成链（即每个数对都不满足前后严格递增），则答案为 max(values)。
2. 排序时，如果 a 相同，则按 b 升序排序。这样在比较时，如果 a 相等，由于严格递增要求，它们不可能同时被选，所以排序顺序不会影响结果，但方便处理。
3. 如果权值有负数，我们的初始化 dp[i] = values[i] 仍然成立，因为我们可以选择只取一个数对（即使它是负数，但如果不取任何数对，和为0，但题目通常要求至少选一个数对，如果允许不选，则在最后答案中与0比较取最大值即可）。本题我们假设至少选一个数对。

时间复杂度与空间复杂度

• 时间复杂度：O(n²)，因为双重循环比较。
• 空间复杂度：O(n)，用于存储 dp 数组。

扩展思考

如果问题改为可以非严格递增（即 a_j <= a_k 且 b_j <= b_k），则排序时需要按 a 升序、b 升序，并在比较时允许相等。此时状态转移条件变为 a_j <= a_i 且 b_j <= b_i，但要避免同一个数对与自己比较（即 j ≠ i）。