是我在学习动态规划时遇到的一道题。
题目：
一共有两种解法：
- 动态规划
- 贪心 二分（很难理解，我还没完全懂。。。）
解法一：动态规划
思路：
状态：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);
}
