企业网站seo方案案例_自适应h5网页模板_怎么给自己的公司做网站_电商平台网站

646. 最长数对链 - 力扣（LeetCode）

题目要求：

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。

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

找出并返回能够形成的 最长数对链的长度 。

你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例 1：

输入：pairs = [[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4] 。

示例 2：

输入：pairs = [[1,2],[7,8],[4,5]]
输出：3
解释：最长的数对链是 [1,2] -> [4,5] -> [7,8] 。

提示：

• n == pairs.length
• 1 <= n <= 1000
• -1000 <= lefti < righti <= 1000

解法-1 动态规划 O(N)：

        链子后端小于链子前端才能连接成同一个数对链，那么我们可以先对原数组，根据每个pairs[i]的前端进行升序排列，这样才能保证连接顺序必然是从左往右（可能跳过中间的pairs[i]）。接下来就可以使用熟悉的动态规划了。

        使用一个dp表，dp[i]存放以pairs[i]为结尾的最长数对链的长度，遍历前面的数对链，只要pairs[i][0] > pairs[j][1]则它们可以连接成链子，再判断此时的长度是否最长，即：

                                        dp[i] = max(dp[i],dp[j]+1);

        假如前面没有可连接的数对链，那么pairs[i]为结尾的最长数对链就是pairs[i]本身：

                                        dp[i]=1;

class Solution {
public:int findLongestChain(vector<vector<int>>& pairs) {sort(pairs.begin(), pairs.end(),[](vector<int>& a, vector<int>& b) { return a[0] < b[0]; });int n = pairs.size();vector<int> dp(n,1);int ret = dp[0];for(int i = 1;i < n;i++){for(int j = 0;j < i;j++){if(pairs[i][0] > pairs[j][1]){dp[i] = max(dp[i],dp[j]+1);}ret  = max(ret,dp[i]);}}return ret;}
};