【最长递增系列】动态规划法和贪心法

导言：

本文总结最长递增子序列、最长递增区间、最长数对链，

本质上都是最长递增子序列，扩展到区间、数对，解法还是一致的。

动态规划法复杂度是O（n^2)，双层循环，在这里动态规划没有节省时间，不是最优解，

贪心法需要排序+遍历，排序的时间复杂度是O(nlogn)。

在做题时，往往先想到动态规划法，但是动态规划法特别容易超时。

另外，在一维的时候，贪心+二分查找，实现上，细节较多，容易出错。

最长递增子序列300. 最长递增子序列 - 力扣（LeetCode）

动态规划法

如果模拟题目意思，直接解，那么，每到一个位置i，都要去找它的递增子序列的前序位置j，关系满足：nums[j]

所以，直接遍历nums[:i]就好了。

动态规划解法：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> 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)

 贪心法

如果想找到最长递增子序列，贪心想法：开始的结点最小，那么有可能最长。

在一维情况--最长递增子序列问题上，可以维护一个递增子序列d，当遇到在d的区间内的数时，插入d中，最后返回d的长度

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        d = []
        for n in nums:
            if not d or n > d[-1]:
                d.append(n)
            else:
                l, r = 0, len(d) - 1
                loc = r
                while l <= r:
                    mid = (l + r) // 2
                    if d[mid] >= n:
                        loc = mid
                        r = mid - 1
                    else:
                        l = mid + 1
                d[loc] = n
        return len(d)

最长数对链和无重复区间

当这个问题扩展到数对和区间上时，由于题目要求变成了【无顺序】要求，所以反而贪心法解法变得简单，可以排序后+遍历就可以完成，【时间复杂度】的要求也变高了。

动态规划法和前面是一样的解法和思路。

贪心法：

646. 最长数对链 - 力扣（LeetCode）

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda a:a[1])
        res=0
        pre=float('-inf')
        for (a,b) in pairs:
            if a>pre:
                pre=b
                res+=1
        return res

需要注意的是，最优的是，贪心法。