Leetcode 300. Longest Increasing Subsequence (python+cpp)

题目

解法1：brutal force recursion（TLE）

这道题是著名的LIS。按照leetcode的惯例，subsequence是可以不连续的，但是subarray或者说substring是必须连续的。这个在后面讲到相关的题目的时候也会讲到
这边最直观的方法，也就是所谓的brutal force当然是找出所有可能的increasing sequence，然后取最大的。由于这道题是个很经典的动态规划题，就不详细介绍这第一种解法了，直接上代码。
python代码如下：

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:def dfs(curr_pos,prev):if curr_pos == len(nums):return 0taken = 0if (nums[curr_pos]>prev):taken = 1 + dfs(curr_pos+1,nums[curr_pos])not_taken = dfs(curr_pos+1,prev)return max(taken,not_taken)return dfs(0,float('-inf'))

这样解是超时的，因为有很多重复的recursion操作，当然可以用recursion+memorization的方法来做，不过这边就不介绍了。

解法2：动态规划 （O(n*n)解法）

这边第一种dp是最常见的解法，也是最容易理解的，具体如下：

• 定义一个dp数组，dp[i]代表到i这个位置结束能形成的increasing sequence的最大长度
• 状态转移方程为dp[i] = max(dp[i],dp[j]+1) if nums[i]>nums[j]
• 所以需要两层循环，外层循环遍历所有dp的位置，内层循环遍历i位置之前的所有位置
  python代码如下：

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if not nums:return 0dp = [1]*len(nums)for i in range(1,len(nums)):for j in range(i):if nums[i]>nums[j]:dp[i] = max(dp[i],dp[j]+1)return max(dp)

解法3：动态规划+二分搜索

这种方法说实话比较特殊，这边定义的dp数组是用来放一个递增的subsequence。感兴趣的话可以看leetcode官方的解释，我这边就不解释了，个人觉得第二种方法才是最能体现动态规划思想的。不过因为这种方法用到了二分搜索，所以最终复杂度是O(nlog(n))
python代码如下：

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:def binary_search(curr,dp):l = 0r = len(dp)while l<=r:mid = l + (r - l) // 2if dp[mid] == curr:return midif dp[mid]>curr:r = mid-1else:l = mid+1return l if not nums:return 0dp = [nums[0]]for i in range(1,len(nums)):if nums[i]>dp[-1]:dp.append(nums[i])else:pos = binary_search(nums[i],dp)dp[pos] = nums[i]return len(dp)

C++代码如下：
C++这边我自己写了一个binary search，不过也可以调用C++的内置库函数lower_bound

class Solution {
    
public:int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) return 0;vector<int> dp;dp.push_back(nums[0]);for (int i=1;i<nums.size();i++){
    if (nums[i]>dp.back()){
    dp.push_back(nums[i]);}else{
    // auto pos = lower_bound(dp.begin(),dp.end(),nums[i]);// *pos = nums[i];int pos = binary_search(dp,nums[i]);dp[pos] = nums[i];}} return dp.size();}int binary_search(vector<int> dp,int curr){
    int l=0,r=dp.size();while (l<=r){
    int mid = l+(r-l)/2;if (dp[mid]==curr) return mid;if (dp[mid]>curr){
    r = mid-1;}else l = mid+1;} return l;}
};