最长数对链

题目描述

给出 n 个数对。在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对 (c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个排序后的数对列表，你需要构造出一个最长的数对链。

注意：

• 数对的个数应该大于等于 1 且不超过 n。
• 数对 (a, b) 和 (c, d) (其中 a < b 且 c < d) 可以构成一个数对链，当且仅当 b < c。

解题步骤

为了计算最长数对链，我们可以使用动态规划的思想来解决问题。

1. 排序：首先对给定的数对列表按照第二个数字的升序进行排序，以确保后面的数对始终满足跟随关系。

2. 定义状态：我们可以将问题转化为对于每个数对的状态，即以该数对为结尾的最长数对链的长度。令 dp[i] 表示以第 i 个数对为结尾的最长数对链的长度。

3. 初始状态：对于每个数对，初始状态为 1，即自身形成长度为 1 的数对链。

4. 状态转移方程：对于第 i 个数对，我们需要找到所有在它之前的数对 (a, b)，其中 b < c，并更新 dp[i]。如果存在多个满足条件的数对，我们选择最长的数对链长度进行更新。

   综上所述，我们可以得到状态转移方程为：

   dp[i] = max(dp[j] + 1)，其中 0 ≤ j < i 且 pairs[j][1] < pairs[i][0]。

5. 最终解：问题的解即为所有 dp[i] 中的最大值。

下面是使用动态规划解决最长数对链问题的算法框架：

function findLongestChain(pairs) {
  const n = pairs.length;

  // 排序
  pairs.sort((a, b) => a[1] - b[1]);

  // 初始化状态数组
  const dp = new Array(n).fill(1);

  // 计算最长数对链的长度
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (pairs[j][1] < pairs[i][0]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  // 返回最长数对链的长度
  return Math.max(...dp);
}