[leetcode-646-Maximum Length of Pair Chain]
2024-10-21 06:38:16
You are given n
pairs of numbers. In every pair, the first number is always smaller than the second number.
Now, we define a pair (c, d)
can follow another pair (a, b)
if and only if b < c
. Chain of pairs can be formed in this fashion.
Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.
Example 1:
Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]
Note:
- The number of given pairs will be in the range [1, 1000].
思路:
动态规划。递推公式是 dp[i] = max(dp[i],dp[j]+1);其中0=<j<i;
int findLongestChain(vector<vector<int>>& pairs)
{
sort(pairs.begin(), pairs.end(), [](const vector<int>&a, const vector<int>&b){return a[] < b[]; }); vector<int> dp(pairs.size(), );
for (int i = ; i < pairs.size(); i++)
{
for (int j = ; j<i;j++)
{
if (pairs[i][]>pairs[j][])
{
dp[i] = max(dp[i],dp[j]+);
}
} }
return *max_element(dp.begin(), dp.end());
}
最新文章
- win下修改mysql默认的字符集以防止乱码出现
- 【GoLang】golang HTTP GET/POST JSON的服务端、客户端示例,包含序列化、反序列化
- ${pageContext.request.contextPath} JSP取得绝对路径
- ThinkPHP 使用极光推送给ios推送消息
- javascript 正则匹配手机号码
- Flashback Version/Transaction Query
- python词云的制作方法
- 分享一下自己写的一个vscode-leetcode答题插件
- java连接sqlserver2008
- Silverlight中验证码生成
- 010 Editor 8.0.1 之 逆向分析及注册机编写
- java - Integer、int 、String相互转换总结
- webstorm破解版
- [转]Qt 之 QFileSystemWatcher
- 使用Eclipse可以方便的统计工程或文件的代码行数,
- [daily][CentOS][SELinux]用key免登陆不成功,原来是SElinux在搞事情
- vue中assets文件夹与static文件夹的区别
- 利用VBS下载EXE文件手法记录
- 【刷题】BZOJ 1070 [SCOI2007]修车
- go基础语法-变量定义