C++刷LeetCode（646. 最长数对链）【动态规划】
题目描述：给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例：
输入：[, , ]
输出：2
解释：最长的数对链是 ->
提示：
给出数对的个数在 范围内。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-length-of-pair-chain
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
//排序
sort(pairs.begin(), pairs.end(), [&](vector<int>&a, vector<int>&b){
return a < b;
});
//动态规划
int len = pairs.size();
vector<int>dp(len, 0);
//初始值
dp = 1;
for(int i = 1; i < len; i++){
dp = dp;
int j = i - 1;
while(j >= 0 && pairs >= pairs)j--;
if(j >= 0)dp = max(dp, dp + 1);
}
return dp;
}
};
参考链接：https://leetcode-cn.com/problems/maximum-length-of-pair-chain/solution/c-dong-tai-gui-hua-by-da-li-wang-35/
页:
[1]