最长数对链

字数 2362 2025-10-28 20:05:14

最长数对链

题目描述
给出 n 个数对。在每个数对中，第一个数字总是比第二个数字小。我们定义一个数对 (c, d) 可以跟在另一个数对 (a, b) 后面，当且仅当 b < c。数对可以以这种形式连接起来，形成一个数对链。找出能够形成的最长数对链的长度。你不需要使用所有的数对，可以以任何顺序选择其中的一些数对来构造这个链。

例如，给定数对集合 [[1,2], [2,3], [3,4]]，最长的数对链是 [1,2] -> [3,4]，其长度为 2。

解题过程

这个问题与“最长递增子序列”问题在思路上有相似之处，但约束条件不同。我们的目标是选择一系列数对，使得每个后续数对的第一个数都大于前一个数对的第二个数，从而形成一个链。链的长度就是所选数对的数量。

步骤 1：问题分析与状态定义
一个关键的观察是，为了给后面的数对留下更多的“空间”，我们希望当前数对的第二个数尽可能小。这样，链就有可能连接得更长。因此，一个常见的预处理步骤是按照每个数对的第二个数进行升序排序。

排序后，问题就转化为：从排序后的数对序列中，按顺序选取一个子序列，使得每个被选中的数对的第一个数都大于前一个被选中的数对的第二个数。

我们可以定义动态规划状态：
dp[i] 表示以第 i 个数对作为结尾时，能够形成的最长数对链的长度。

步骤 2：状态转移方程
对于状态 dp[i]，我们需要考虑所有在 i 之前的数对 j (其中 0 <= j < i)。如果第 j 个数对的第二个数小于第 i 个数对的第一个数（即 pairs[j][1] < pairs[i][0]），那么第 i 个数对就可以接在第 j 个数对之后，从而形成一条更长的链。此时，dp[i] 的值至少可以是 dp[j] + 1。

为了找到以 i 结尾的最长链，我们需要遍历所有满足条件的 j，并取最大值。
因此，状态转移方程为：
dp[i] = max(dp[i], dp[j] + 1)，对于所有满足 pairs[j][1] < pairs[i][0] 的 j。

当然，最基础的情况是，每个数对自己本身就可以构成一个长度为 1 的链。所以我们需要初始化所有的 dp[i] 为 1。

步骤 3：算法实现细节

排序：首先将数对数组 pairs 按照每个数对的第二个元素（即 pair[1]）进行升序排序。
初始化 DP 数组：创建一个长度为 n（数对个数）的数组 dp，并将每个元素初始化为 1。
填充 DP 数组：
- 使用双重循环。外层循环 i 从 0 遍历到 n-1，表示当前正在计算以第 i 个数对结尾的链。
- 内层循环 j 从 0 遍历到 i-1，检查第 j 个数对是否能连接到第 i 个数对之前。
- 如果满足连接条件 (pairs[j][1] < pairs[i][0])，则更新 dp[i] = max(dp[i], dp[j] + 1)。
获取结果：最终答案并不是 dp[n-1]，因为最长链不一定以最后一个数对结尾。我们需要遍历整个 dp 数组，找到其中的最大值。

步骤 4：举例说明
假设输入数对为：pairs = [[5, 9], [3, 4], [1, 2], [6, 7]]

排序：按照每个数对的第二个数排序后，得到：[[1, 2], [3, 4], [6, 7], [5, 9]]。注意，[5,9] 的第二个数 9 是最大的，所以排在了最后。
初始化 DP 数组：dp = [1, 1, 1, 1]
填充 DP 数组：
- i = 0（数对 [1,2]）：前面没有数对，dp[0] 保持为 1。
- i = 1（数对 [3,4]）：
  - 检查 j=0 ([1,2])：2 < 3 成立。所以 dp[1] = max(1, dp[0] + 1) = max(1, 2) = 2。
- i = 2（数对 [6,7]）：
  - 检查 j=0 ([1,2])：2 < 6 成立。dp[2] = max(1, 1+1) = 2。
  - 检查 j=1 ([3,4])：4 < 6 成立。dp[2] = max(2, 2+1) = 3。
- i = 3（数对 [5,9]）：
  - 检查 j=0 ([1,2])：2 < 5 成立。dp[3] = max(1, 1+1) = 2。
  - 检查 j=1 ([3,4])：4 < 5 成立。dp[3] = max(2, 2+1) = 3。
  - 检查 j=2 ([6,7])：7 < 5 不成立。跳过。
  - 所以最终 dp[3] = 3。
获取结果：dp 数组为 [1, 2, 3, 3]，最大值是 3。
验证一下最长链：[1,2] -> [3,4] -> [6,7]，长度为 3。[5,9] 因为第一个数 5 小于前面 [3,4] 的第二个数 4，所以无法接上，但它自己可以接在 [1,2] 后面形成 [1,2] -> [5,9]，长度为 2，不是最长的。

步骤 5：复杂度分析

时间复杂度：O(n²)，主要由双重循环决定，其中 n 是数对的个数。排序的时间复杂度为 O(n log n)，小于 O(n²)，因此总时间复杂度为 O(n²)。
空间复杂度：O(n)，用于存储 DP 数组。

通过这个循序渐进的过程，我们利用动态规划解决了最长数对链问题。核心思路是通过排序创造贪心选择的可能性（优先选择结束早的数对），并使用动态规划来精确计算最优解。

最长数对链题目描述给出 n 个数对。在每个数对中，第一个数字总是比第二个数字小。我们定义一个数对 (c, d) 可以跟在另一个数对 (a, b) 后面，当且仅当 b < c。数对可以以这种形式连接起来，形成一个数对链。找出能够形成的最长数对链的长度。你不需要使用所有的数对，可以以任何顺序选择其中的一些数对来构造这个链。例如，给定数对集合 [[1,2], [2,3], [3,4]] ，最长的数对链是 [1,2] -> [3,4] ，其长度为 2。解题过程这个问题与“最长递增子序列”问题在思路上有相似之处，但约束条件不同。我们的目标是选择一系列数对，使得每个后续数对的第一个数都大于前一个数对的第二个数，从而形成一个链。链的长度就是所选数对的数量。步骤 1：问题分析与状态定义一个关键的观察是，为了给后面的数对留下更多的“空间”，我们希望当前数对的第二个数尽可能小。这样，链就有可能连接得更长。因此，一个常见的预处理步骤是按照每个数对的第二个数进行升序排序。排序后，问题就转化为：从排序后的数对序列中，按顺序选取一个子序列，使得每个被选中的数对的第一个数都大于前一个被选中的数对的第二个数。我们可以定义动态规划状态： dp[i] 表示以第 i 个数对作为结尾时，能够形成的最长数对链的长度。步骤 2：状态转移方程对于状态 dp[i] ，我们需要考虑所有在 i 之前的数对 j (其中 0 <= j < i )。如果第 j 个数对的第二个数小于第 i 个数对的第一个数（即 pairs[j][1] < pairs[i][0] ），那么第 i 个数对就可以接在第 j 个数对之后，从而形成一条更长的链。此时， dp[i] 的值至少可以是 dp[j] + 1 。为了找到以 i 结尾的最长链，我们需要遍历所有满足条件的 j ，并取最大值。因此，状态转移方程为： dp[i] = max(dp[i], dp[j] + 1) ，对于所有满足 pairs[j][1] < pairs[i][0] 的 j 。当然，最基础的情况是，每个数对自己本身就可以构成一个长度为 1 的链。所以我们需要初始化所有的 dp[i] 为 1。步骤 3：算法实现细节排序：首先将数对数组 pairs 按照每个数对的第二个元素（即 pair[1] ）进行升序排序。初始化 DP 数组：创建一个长度为 n （数对个数）的数组 dp ，并将每个元素初始化为 1。填充 DP 数组：使用双重循环。外层循环 i 从 0 遍历到 n-1 ，表示当前正在计算以第 i 个数对结尾的链。内层循环 j 从 0 遍历到 i-1 ，检查第 j 个数对是否能连接到第 i 个数对之前。如果满足连接条件 ( pairs[j][1] < pairs[i][0] )，则更新 dp[i] = max(dp[i], dp[j] + 1) 。获取结果：最终答案并不是 dp[n-1] ，因为最长链不一定以最后一个数对结尾。我们需要遍历整个 dp 数组，找到其中的最大值。步骤 4：举例说明假设输入数对为： pairs = [[5, 9], [3, 4], [1, 2], [6, 7]] 排序：按照每个数对的第二个数排序后，得到： [[1, 2], [3, 4], [6, 7], [5, 9]] 。注意， [5,9] 的第二个数 9 是最大的，所以排在了最后。初始化 DP 数组： dp = [1, 1, 1, 1] 填充 DP 数组： i = 0 （数对 [1,2] ）：前面没有数对， dp[0] 保持为 1。 i = 1 （数对 [3,4] ）：检查 j=0 ( [1,2] )： 2 < 3 成立。所以 dp[1] = max(1, dp[0] + 1) = max(1, 2) = 2 。 i = 2 （数对 [6,7] ）：检查 j=0 ( [1,2] )： 2 < 6 成立。 dp[2] = max(1, 1+1) = 2 。检查 j=1 ( [3,4] )： 4 < 6 成立。 dp[2] = max(2, 2+1) = 3 。 i = 3 （数对 [5,9] ）：检查 j=0 ( [1,2] )： 2 < 5 成立。 dp[3] = max(1, 1+1) = 2 。检查 j=1 ( [3,4] )： 4 < 5 成立。 dp[3] = max(2, 2+1) = 3 。检查 j=2 ( [6,7] )： 7 < 5 不成立。跳过。所以最终 dp[3] = 3 。获取结果： dp 数组为 [1, 2, 3, 3] ，最大值是 3。验证一下最长链： [1,2] -> [3,4] -> [6,7] ，长度为 3。 [5,9] 因为第一个数 5 小于前面 [3,4] 的第二个数 4，所以无法接上，但它自己可以接在 [1,2] 后面形成 [1,2] -> [5,9] ，长度为 2，不是最长的。步骤 5：复杂度分析时间复杂度：O(n²)，主要由双重循环决定，其中 n 是数对的个数。排序的时间复杂度为 O(n log n)，小于 O(n²)，因此总时间复杂度为 O(n²)。空间复杂度：O(n)，用于存储 DP 数组。通过这个循序渐进的过程，我们利用动态规划解决了最长数对链问题。核心思路是通过排序创造贪心选择的可能性（优先选择结束早的数对），并使用动态规划来精确计算最优解。