上海网站开发报价,建设网站页面,云匠网接单,做网站的抬头标语怎么今日份题目#xff1a;
给你一个由 n 个数对组成的数对数组 pairs #xff0c;其中 pairs[i] [lefti, righti] 且 lefti righti 。
现在#xff0c;我们定义一种 跟随 关系#xff0c;当且仅当 b c 时#xff0c;数对 p2 [c, d] 才可以跟在 p1 [a, b] 后面…今日份题目
给你一个由 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
题目思路
动态规划一维dp数组记录到目前为止的最长数对链数值。
状态转移方程
找到当前位置之前的满足递增的最长dp值的那一组找不到就是自己1。
dp[i]max(dp[i],dp[j]1);
代码
class Solution
{
public:int findLongestChain(vectorvectorint pairs) {int npairs.size();vectorint dp(n,1);//记录到目前为止的最长数对链sort(pairs.begin(),pairs.end());for(int i0;in;i) {for(int j0;ji;j) {if(pairs[i][0]pairs[j][1]) {dp[i]max(dp[i],dp[j]1);//状态转移方程}}}return dp[n-1];}
};提交结果 欢迎大家在评论区讨论如有不懂的代码部分欢迎在评论区留言
