力扣646. 最长数对链

本文主要是介绍力扣646. 最长数对链，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划

• 思路：
  • 思路与 力扣354. 俄罗斯套娃信封问题 类似
  • 将序列进行排序，然后假设 dp[i] 为第 i 个元素的最长数对链个数；
  • 则其状态转移方程：
    • 第 i 个元素之前的某一个元素（假设是下标是 j），如果满足：
      • pairs[j][1] < pairs[i][0]，且
      • dp[j] 是所有数对链最长的；
    • 则：dp[i] = dp[j] + 1

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

• 其同样可以通过二分查找来进行优化，思路参见 力扣354. 俄罗斯套娃信封问题

————————————————————————————————————

这篇关于力扣646. 最长数对链的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---