最长递增子序列两种算法实现（动态规划，二分查找） ...

恭喜你刷到博主 DP 经典题目详解部分第一期，想学好 DP 请关注订阅，会连续更新！！！！！

发起先阅读DP算法入门
00001 最长递增子序列（Longest Increasing Subsequence，简写 LIS）

提要：本文先容两种算法实现
一种是动态规划（算法复杂度 O（n ^ 2））：

1. 通过本题了解设计动态规划的通用技巧 ————> 数学归纳思想

复制代码

一种是二分查找（算法复杂度 O（n log n））：

1. 由 patience game 的纸牌游戏（甚至有一种排序方法就叫做 patience sorting（耐心排序））的思想衍生的算法

复制代码

---

01 动态规划

1. 假设这个结论在 k < n 时成立，然后想办法证明 k = n 的时候此结论也成立。如果能够证明出来，那么就说明这个结论对于 k 等于任何数都成立
3. 类似的，我们设计动态规划算法，不是需要一个 dp 数组吗？我们可以假设 dp[0...i - 1] 都已经被算出来了，怎么通过这些结果算出 dp[i]？

复制代码

首先要定义清楚 dp 数组的含义，即 dp 的值到底代表着什么？
我们的定义是如许的：dp 表现以 nums 这个数结尾的最长递增子序列的长度
重申一遍 DP 框架

1. 明确状态 -> 定义 dp 数组/函数的含义 -> 明确选择-> 明确 base case

复制代码

1. int lengthOfLIS(vector<int> &nums)
2. {
3.     if (nums.empty())
4.         return 0;
6.     int n = nums.size();
7.     //dp 数组应该全部初始化为 1，因为子序列最少也要包含自己，所以长度最小为 1
8.     vector<int> dp(n, 1);
10.     // 填充 dp 数组
11.     for (int i = 1; i < n; ++i)
12.     {
13.         //找到前面那些结尾比 i 小的子序列，然后把 i 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加 1
14.         for (int j = 0; j < i; ++j)
15.         {
16.             if (nums[i] > nums[j])
17.             {
18.                 dp[i] = max(dp[i], dp[j] + 1);
19.             }
20.         }
21.     }
23.     // 寻找 dp 数组中的最大值即找最长递增子序列
24.     int res = 0;
25.     for (int i = 0; i < n; ++i)
26.     {
27.         res = max(res, dp[i]);
28.     }
29.     return res;
30. }

复制代码

10 二分查找

首先我们玩下叫 patience game 的纸牌游戏

1. 规则：他的实现原理就是首先使用数组中的第一个数字创建一个纸牌堆，然后逐个读取数组中的剩余数字，如果当前数字比所有纸牌堆中最上面的数字都大，就新建一个纸牌堆，把当前数字放到该堆中。否则找到一个最上面数字不小于当前数字的纸牌堆，把当前数字放到该纸牌堆中

复制代码

---

我们只要把处理扑克牌的过程编程写出来即可。每次处理一张扑克牌不是要找一个符合的牌堆顶来放吗？牌堆顶的牌不是有序吗？
———> 用到二分查找了：搜索当前牌应放置的位置

---

2. int LIS(vector<int> &nums)
3. {
4.     if (nums.empty())
5.         return 0;
7.     vector<int> top; // 用于存储牌堆的顶端元素
8.     for (int poker : nums)
9.     {
10.         // 二分查找，找到比 poker 大的最小位置
11.         auto it = lower_bound(top.begin(), top.end(), poker);
13.         // 如果没有找到合适的位置，说明 poker 应该作为新的牌堆加入
14.         if (it == top.end())
15.         {
16.             top.push_back(poker);
17.         }
18.         else
19.         {
20.             // 否则，更新找到的位置
21.             *it = poker;
22.         }
23.     }
25.     // 牌堆数即为 LIS 长度
26.     return top.size();
27. }

复制代码

---

这里的二分查找直接用了 STL 算法库中的 lower_bound （因为lower_bound 底层实现使用二分查找）
想要相识二分查找的实现的参考

1. template <typename ForwardIterator, typename T>
2. ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val) {
3.     while (first < last) {
4.         ForwardIterator mid = first + (last - first) / 2;  // 计算中点
5.         if (*mid < val) {
6.             first = mid + 1;  // 如果 mid 小于 val，则搜索右半部分
7.         } else {
8.             last = mid;  // 如果 mid 大于或等于 val，则搜索左半部分
9.         }
10.     }
11.     return first;  // 返回第一个不小于 val 的元素
12. }

复制代码

---

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。