数据结构学习Leetcode300最长递增子序列

是我在学习动态规划时遇到的一道题。

题目：

一共有两种解法：

动态规划贪心 二分（很难理解，我还没完全懂。。。）

---

 

解法一：动态规划 思路：

状态：nums的前i个数的最长递增子序列。dp[i]

转移方程：依次计算每个状态dp[i]的状态，这个状态依赖于前dp[0...i-1]的状态。

如果大于前面的数nums[j] < nums[i]，则说明有递增现象了。起码nums[j] ，nums[i]是一对的，如果j前面还有子序列，那岂不是美哉，总之dp[i] = dp[j] + 1。但是别急，万一这个dp[j]小，赋值了反而dp[i]就变小了。我们要的是最长的，先要比较，再确定。

主要是为了防止这种情况：【3 4 5 6 0 1 2 7】

比如这个时候7已经和6比完了，7>6，所以dp[7]=dp[3]+1

然后又和0比，7>0，如果直接dp[7]=dp[4]+1，那么dp[7]就会变成2了。

 最后找到dp里最大的，就是我们想要的。

复杂度计算：

时间复杂度O(n^2) 空间复杂度O(n)

代码： #include <vector> //最长递增子序列 //解法一：动态规划 //时间复杂度O(n^2) //空间复杂度O(n) class Solution { public: int lengthOfLIS(std::vector<int>& nums) { //状态就是前i个数最长递增子序列 std::vector<int> dp(nums.size(), 1);//状态 int max_count = 1; for (int i = 1; i < nums.size(); ++i)//一个一个状态算 { //转移方程 for (int j = 0; j < i ; ++j)//查询前面的数是否小于 { if (nums[j] < nums[i])//如果大于前面的数，则说明有递增 { dp[i]=std::max(dp[i], dp[j] + 1);//有递增也不能直接赋值，有可能这个dp[j]小，赋值了反而dp[i]就变小了 } } max_count = max_count > dp[i] ? max_count : dp[i];//取最大的dp[i] } return max_count; } }; void Test_solution1() { std::vector<int> nums{ 1,3,6,7,9,4,10,5,6 }; Solution solution; std::cout<<solution.lengthOfLIS(nums); }

---

 

 解法二：贪心 二分 思路：

二分就是用来查找的。关键是用贪心创建的dp[]是一个单调递增的，所以可以二分查找。

很难解释，因为我也一知半解。挖个坑！

复杂度计算： 

时间复杂度O(nlogn) 空间复杂度O(n)

代码： #include <vector> //最长递增子序列 //解法二：贪心 二分 //时间复杂度O(nlogn) //空间复杂度O(n) class Solution { public: int lengthOfLIS(std::vector<int>& nums) { //dp[x]:长度为x的最长递增子序列的最小一个末尾值 //举个例子{1,2,3,4,5,6} // 长度为3的最长递增子序列有好几个，比如：{1,2,3} {3,4,5} {4,5,6}，他们有各种末尾值，但是最小的一个末尾值是3 std::vector<int> dp(nums.size(),0);//dp实际有多长（len），就意味着最长递增子序列有多长 dp[0] = nums[0]; int len = 0;//初始化，长度为1，指着dp第一个数dp[0] for (int i = 1; i < nums.size(); ++i) { if (nums[i] > dp[len]) { ++len; dp[len] = nums[i]; } else { int j = 0, z = len; while (j < z) { int mid = (j + z) / 2; if (dp[mid] < nums[i])j = mid + 1; else z = mid; } dp[j] = nums[i]; } } //for (const auto& x : dp) //{ // std::cout << x << ' '; //} //std::cout << std::endl; return len + 1; } }; void Test_solution2() { //std::vector<int> nums{ 1,3,6,7,9,4,10,5,6 }; std::vector<int> nums{ 5,6,7,8,9,1,2,3,4 }; Solution solution; std::cout << solution.lengthOfLIS(nums); }