线性动态规划：最长数对链的变种——带权值的最长数对链 题目描述 给定一个由数对组成的数组 pairs，其中每个数对 pairs[ i] = [ left_ i, right_ i]，且 left_ i < right_ i。现在我们定义一种带权值的数对链： 链中的数对可以按任意顺序排列 对于链中相邻的两个数对 A 和 B，必须满足 A[ 1] < B[ 0 ]（即前一个数对的右端点严格小于后一个数对的左端点） 每个数对都有一个对应的权值 weight[ i ] 目标是找到一个数对链，使得链中所有数对的权值之和最大 请设计算法找出这样的最大权值数对链。 解题过程 这个问题是经典最长数对链问题的变种，在原问题（求最长链长度）基础上增加了权值，要求权值和最大而非链长度最长。 步骤1：问题分析 首先我们需要理解问题的核心要求： 数对之间需要满足严格的前后关系（A[ 1] < B[ 0 ]） 数对可以按任意顺序排列，不要求按原数组顺序 目标是权值和最大，不是链长度最长 步骤2：关键观察 观察1：由于数对可以任意排列，我们可以先对数对进行排序，这样能简化后续的动态规划过程。 观察2：如果我们按照每个数对的右端点进行排序，那么对于任意数对i，所有能接在它后面的数对j都满足j > i（在排序后的序列中）。 步骤3：状态定义 定义 dp[ i ] 表示以第 i 个数对为结尾的链所能获得的最大权值和。 步骤4：状态转移方程 对于每个数对 i，我们需要考虑所有在它之前的数对 j（j < i）： 如果 pairs[ j][ 1] < pairs[ i][ 0 ]（即数对j可以放在数对i前面） 那么 dp[ i] = max(dp[ i], dp[ j] + weight[ i ]) 此外，每个数对本身也可以作为链的起点，所以初始时 dp[ i] = weight[ i ]。 步骤5：算法步骤 将数对数组按照右端点进行排序 初始化dp数组，dp[ i] = weight[ i ] 对于每个i从0到n-1： 对于每个j从0到i-1： 如果pairs[ j][ 1] < pairs[ i][ 0 ]： dp[ i] = max(dp[ i], dp[ j] + weight[ i ]) 最终结果是max(dp[ 0], dp[ 1], ..., dp[ n-1 ]) 步骤6：时间复杂度优化 上面的算法时间复杂度是O(n²)，我们可以进一步优化： 在排序后，对于每个数对i，我们需要找到所有满足pairs[ j][ 1] < pairs[ i][ 0 ]的数对j。由于数组已按右端点排序，我们可以使用二分查找来快速找到这样的j。 优化后的算法： 将数对按右端点排序 初始化dp数组，dp[ i] = weight[ i ] 同时维护一个maxDP数组，其中maxDP[ i] = max(dp[ 0], dp[ 1], ..., dp[ i ]) 对于每个i： 使用二分查找找到最大的j，使得pairs[ j][ 1] < pairs[ i][ 0 ] 如果找到这样的j，那么dp[ i] = max(dp[ i], maxDP[ j] + weight[ i ]) 更新maxDP[ i] = max(maxDP[ i-1], dp[ i ]) 步骤7：示例演示 假设输入： pairs = [ [ 1,2], [ 2,3], [ 3,4] ] weights = [ 1, 2, 3 ] 步骤： 排序后数组不变（已按右端点有序） 初始化： dp = [ 1, 2, 3 ] maxDP = [ 1, 2, 3 ] 处理i=1： 二分查找j，满足pairs[ j][ 1] < pairs[ 1][ 0 ]=2 找到j=0（pairs[ 0][ 1]=2 < 2? 不满足，严格小于） 没有找到，dp[ 1 ]保持2 处理i=2： 二分查找j，满足pairs[ j][ 1] < pairs[ 2][ 0 ]=3 找到j=0（pairs[ 0][ 1]=2 < 3，满足） dp[ 2] = max(3, maxDP[ 0 ] + 3) = max(3, 1+3) = 4 更新maxDP[ 2 ] = max(2, 4) = 4 最终结果：max(1, 2, 4) = 4 步骤9：边界情况处理 空数组：返回0 单个元素：返回该元素的权值 所有数对都不满足连接条件：返回最大的单个权值 这个算法的时间复杂度优化到了O(n log n)，主要花费在排序和二分查找上，能够高效解决带权值的最长数对链问题。