最长递增子序列两种算法实现（动态规划，二分查找）
恭喜你刷到博主 DP 经典题目详解部分第一期，想学好 DP 请关注订阅，会连续更新！！！！！发起先阅读DP算法入门
00001 最长递增子序列（Longest Increasing Subsequence，简写 LIS）
提要：本文先容两种算法实现
一种是动态规划（算法复杂度 O（n ^ 2））：
通过本题了解设计动态规划的通用技巧 ————> 数学归纳思想
一种是二分查找（算法复杂度 O（n log n））：
由 patience game 的纸牌游戏（甚至有一种排序方法就叫做 patience sorting（耐心排序））的思想衍生的算法
01 动态规划
假设这个结论在 k < n 时成立，然后想办法证明 k = n 的时候此结论也成立。如果能够证明出来，那么就说明这个结论对于 k 等于任何数都成立
类似的，我们设计动态规划算法，不是需要一个 dp 数组吗？我们可以假设 dp 都已经被算出来了，怎么通过这些结果算出 dp？
首先要定义清楚 dp 数组的含义，即 dp 的值到底代表着什么？
我们的定义是如许的：dp 表现以 nums 这个数结尾的最长递增子序列的长度
重申一遍 DP 框架
明确状态 -> 定义 dp 数组/函数的含义 -> 明确选择-> 明确 base case
int lengthOfLIS(vector<int> &nums)
{
if (nums.empty())
return 0;
int n = nums.size();
//dp 数组应该全部初始化为 1，因为子序列最少也要包含自己，所以长度最小为 1
vector<int> dp(n, 1);
// 填充 dp 数组
for (int i = 1; i < n; ++i)
{
//找到前面那些结尾比 i 小的子序列，然后把 i 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加 1
for (int j = 0; j < i; ++j)
{
if (nums > nums)
{
dp = max(dp, dp + 1);
}
}
}
// 寻找 dp 数组中的最大值即找最长递增子序列
int res = 0;
for (int i = 0; i < n; ++i)
{
res = max(res, dp);
}
return res;
}
10 二分查找
首先我们玩下叫 patience game 的纸牌游戏
规则：他的实现原理就是首先使用数组中的第一个数字创建一个纸牌堆，然后逐个读取数组中的剩余数字，如果当前数字比所有纸牌堆中最上面的数字都大，就新建一个纸牌堆，把当前数字放到该堆中。否则找到一个最上面数字不小于当前数字的纸牌堆，把当前数字放到该纸牌堆中
https://i-blog.csdnimg.cn/img_convert/f2d1752e4a96fb463434c1228c6fa19c.png
https://i-blog.csdnimg.cn/img_convert/8cd21f883c1f14fbbd94a759aaa6a44b.png
https://i-blog.csdnimg.cn/img_convert/ab641c2ac574c1f2c34f3f70b08b45b4.png
https://i-blog.csdnimg.cn/img_convert/7d8f37eb8cbdf625e3815e9f5b4cee91.png
https://i-blog.csdnimg.cn/img_convert/5c5bc484f6ab41dd07421704e9a422f0.png
https://i-blog.csdnimg.cn/img_convert/ee42135e62e3ddb16df64e234ee9f58f.png
https://i-blog.csdnimg.cn/img_convert/f357c55393f1df9af15ea4bb885e3498.png
我们只要把处理扑克牌的过程编程写出来即可。每次处理一张扑克牌不是要找一个符合的牌堆顶来放吗？牌堆顶的牌不是有序吗？
———> 用到二分查找了：搜索当前牌应放置的位置
int LIS(vector<int> &nums)
{
if (nums.empty())
return 0;
vector<int> top; // 用于存储牌堆的顶端元素
for (int poker : nums)
{
// 二分查找，找到比 poker 大的最小位置
auto it = lower_bound(top.begin(), top.end(), poker);
// 如果没有找到合适的位置，说明 poker 应该作为新的牌堆加入
if (it == top.end())
{
top.push_back(poker);
}
else
{
// 否则，更新找到的位置
*it = poker;
}
}
// 牌堆数即为 LIS 长度
return top.size();
}
这里的二分查找直接用了 STL 算法库中的 lower_bound （因为lower_bound 底层实现使用二分查找）
想要相识二分查找的实现的参考
template <typename ForwardIterator, typename T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val) {
while (first < last) {
ForwardIterator mid = first + (last - first) / 2;// 计算中点
if (*mid < val) {
first = mid + 1;// 如果 mid 小于 val，则搜索右半部分
} else {
last = mid;// 如果 mid 大于或等于 val，则搜索左半部分
}
}
return first;// 返回第一个不小于 val 的元素
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]