最长递增子序列的变种：最长数对链 题目描述 给出 n 个数对 (a, b) 的集合，其中每个数对满足 a < b。我们希望形成一个数对链，使得链中相邻的数对 (c, d) 和 (e, f) 满足 d < e（即前一个数对的第二个数小于后一个数对的第一个数）。请找出能够形成的最长数对链的长度。 示例： 输入：[ [ 1,2], [ 2,3], [ 3,4] ] 输出：2 解释：最长的数对链是 [ 1,2] -> [ 3,4]（注意不能接 [ 2,3] 因为 2 < 3 不满足 d < e 的条件） 解题过程 步骤1：理解问题与排序预处理 问题要求选择数对形成链，且链中相邻数对必须满足“前一个的第二个数 < 后一个的第一个数”。 为了便于构造最长链，我们通常先对数对进行排序。排序的标准可以是按照每个数对的第一个元素升序，如果第一个元素相同则按第二个元素升序。 排序后，问题转化为在排序后的序列中选取一个子序列，使得相邻数对满足链条件，且子序列最长。这类似于最长递增子序列（LIS）问题，但比较条件不同。 步骤2：定义动态规划状态 定义 dp[ i ] 表示以第 i 个数对结尾的最长链的长度。 初始时，每个数对自身可以形成一个长度为1的链，所以 dp[ i ] = 1 对于所有 i。 步骤3：状态转移方程 对于每个 i，我们检查所有 j < i： 如果 pairs[ j][ 1] < pairs[ i][ 0 ]（即第 j 个数对的第二个数小于第 i 个数对的第一个数），那么我们可以把第 i 个数对接在第 j 个数对后面，形成更长的链。 此时，dp[ i] = max(dp[ i], dp[ j ] + 1)。 也就是说，我们寻找所有能接在 i 前面的数对 j，并取最大的链长度。 步骤4：计算与结果 我们遍历 i 从 0 到 n-1，对于每个 i，遍历 j 从 0 到 i-1，进行状态转移。 最终结果不是 dp[ n-1 ]，而是整个 dp 数组中的最大值，因为最长链不一定以最后一个数对结尾。 步骤5：优化考虑 上述解法时间复杂度为 O(n²)，类似 LIS 的朴素解法。 实际上，这个问题可以通过贪心算法优化到 O(n log n)：先按数对的第二个元素排序，然后贪心地选择结束最早且能接上的数对。但这里我们聚焦于线性动态规划的解法。 举例说明 输入：[ [ 1,2], [ 2,3], [ 3,4] ] 排序后（已按第一个元素排序）：[ [ 1,2], [ 2,3], [ 3,4] ] dp 初始化：[ 1, 1, 1 ] i=0：前面无数对，dp[ 0 ]=1 i=1：检查 j=0，pairs[ 0][ 1]=2 < pairs[ 1][ 0]=2？不满足（需要严格小于），所以 dp[ 1 ] 保持 1 i=2： j=0：pairs[ 0][ 1]=2 < pairs[ 2][ 0]=3，满足，dp[ 2] = max(1, dp[ 0 ]+1=2) = 2 j=1：pairs[ 1][ 1]=3 < pairs[ 2][ 0 ]=3？不满足 最终 dp = [ 1, 1, 2 ]，最大值是 2。 这样，我们得到了最长数对链的长度为 2。