Leetcode 646. Maximum Length of Pair Chain (python+cpp)

题目

解法：动态规划

这个题目跟Leetcode 300 longest increasing subsequency几乎是一模一样的。只是这边有个隐藏条件就是需要排个序，按照第一个元素从小到大排，这边采用LIS最经典的二维动态规划
python解法如下：

class Solution:def findLongestChain(self, pairs: List[List[int]]) -> int:if not pairs:return 0pairs.sort()dp = [1]*len(pairs)for i in range(1,len(pairs)):for j in range(i):if pairs[i][0]>pairs[j][1]:dp[i] = max(dp[i],dp[j]+1)return max(dp)

C++解法：
C++解法只需要注意一下对一个vector求最大值的方法即可

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