【动态规划】子序列问题

子序列问题也是有一堆题目的问题。「代码随想录」带你学透DP子序列问题！300、最长递增子序列 - 最长递增子序列 - 力扣（LeetCode） (leetcode-cn.com)

300、最长递增子序列 - 力扣（LeetCode） (leetcode-cn.com)

依次解决：

1.【300】最长递增子序列

300、最长递增子序列 - 力扣（LeetCode） (leetcode-cn.com)

1.1.动态规划法

老老实实双层循环法。

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

空间复杂度：O(n)

代码如下：

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.贪心法+二分查找法

创建空数组d存储找到的递增子序列，遍历数组nums，如果nums[i]>d[-1],则append；否则，二分查找将nums[i]【插入并替换】到递增子序列中，即寻找最接近nums[i]<=d[j]，d[j]=nums[i]，d长度是不变的。这么做的结果，d数组中最后的结果并不一定是该序列的真正的最大子序列。

例：

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

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

实际最长子序列：[1,3,6,7,9,10]

d数组里留存了寻找最大子序列的记录，如果更换数组起始点，则一定要新的序列比之前的序列长那么数组长度才会变化，因为最后求解的是长度，所以即使这样len(d)仍然是正确答案。

例：

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

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

实际最长子序列：[4,5,6,7,8]

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

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

实际最长子序列：[1,2,3,4,5,6]

时间复杂度：O（nlogn)

空间复杂度：O（m)

实现代码如下：

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 nd[mid]: left=mid+1 else: loc=mid break d[loc]=n return len(d)

做完这道题发现，如果用贪心+二分查找，那么要注意的细节在于二分查找，二分查找忠告：不要省略任何一种情况。

被折磨到了，所以贴一下结果。

二分查找的边界详解：详解二分查找算法 - murphy_gb - 博客园 (cnblogs.com)

还有一种方法【动态规划+二分查找】：最长上升子序列 - 最长递增子序列 - 力扣（LeetCode） (leetcode-cn.com)