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

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

题目：

一共有两种解法：

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

---

?

解法一：动态规划

思路：

状态：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);
}