[dynamic programming] subsequence problem

Subsequence problem is also a problem with a lot of problems .「 Random code recording 」 Take you through DP Subsequence problem ！300. The longest increasing subsequence - The longest increasing subsequence - Power button （LeetCode） (leetcode-cn.com)

300. The longest increasing subsequence - Power button （LeetCode） (leetcode-cn.com)

In turn, to solve ：

1.【300】 The longest increasing subsequence

300. The longest increasing subsequence - Power button （LeetCode） (leetcode-cn.com)

1.1. Dynamic programming

Honest double-layer circulation method .

Time complexity ：O(n^2)

Spatial complexity ：O(n)

The code is as follows ：

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp=[1 for _ in nums]
        for i in range(len(nums)):
            for j in range(i):
                if nums[i]>nums[j]:
                    dp[i]=max(dp[i],dp[j]+1)
        return max(dp)

1.2. The law of greed + Dichotomy search

Create an empty array d Store the found incremental subsequence , Traversal array nums, If nums[i]>d[-1], be append; otherwise , Binary search will nums[i]【 Insert and replace 】 To the increasing subsequence , That is to find the closest nums[i]<=d[j],d[j]=nums[i],d The length is constant . The result of doing so ,d The final result in the array is not necessarily the real largest subsequence of the sequence .

example ：

nums:[1,3,6,7,9,4,10,5,6]

d:[1,3,4,5,6,10]

The actual longest subsequence ：[1,3,6,7,9,10]

d The record of searching for the largest subsequence is preserved in the array , If you change the starting point of the array , Then the new sequence must be longer than the previous sequence, then the array length will change , Because the final solution is length , So even so len(d) Still the right answer .

example ：

nums:[4,5,6,7,8,1,2]

d:[1,2,6,7,8]

The actual longest subsequence ：[4,5,6,7,8]

nums:[7,8,1,2,3,4,5,6]

d:[1,2,3,4,5,6]

The actual longest subsequence ：[1,2,3,4,5,6]

Time complexity ：O（nlogn)

Spatial complexity ：O（m)

The implementation code is as follows ：

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        d=[]
        for n in nums:
            if not d or n>d[-1]:
                d.append(n)
            else:
                left,right=0,len(d)-1  
                loc=right      
                while left<=right:
                    mid=(left+right)//2
                    if n<d[mid]:
                        loc=mid
                        right=mid-1
                    elif n>d[mid]:
                        left=mid+1
                    else:
                        loc=mid
                        break
                d[loc]=n
        return len(d)

After finishing this problem, I found , If you use greed + Two points search , Then the detail to pay attention to is binary search , Binary search advice ： Don't omit any case .

Tortured , So post the results .

Detailed explanation of the boundary of binary search ： Explain the binary search algorithm in detail - murphy_gb - Blog Garden (cnblogs.com)

There's another way 【 Dynamic programming + Two points search 】： Longest ascending subsequence - The longest increasing subsequence - Power button （LeetCode） (leetcode-cn.com)