最长递增子序列

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

题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

解法一

从暴力递归到动态规划

暴力递归

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        nums.insert(0, -float('inf'))
        @functools.lru_cache()
        def process(pre, i):
            if i == len(nums):
                return 0
            
            p1 = process(pre, i+1)
            p2 = 0
            if nums[i] > nums[pre]:
                p2 = process(i, i+1) + 1
            return max(p1, p2)
        return process(0, 1)

一个自己想的错误的版本 对于一个i, 存在三种情况

1. 该位置不属于升序子序列
2. 该位置属于升序子序列最后一个元素（有条件）
3. 该位置属于一个新的升序子序列的第一个元素

感觉是对的，但是结果不对，由于对于第一个元素不好处理，可能是因为第一次调用了process(0, 0)的问题？

下面为错误的版本

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def process(pre, i):
            if i == len(nums):
                return 0
            p1 = process(pre, i+1)  # 不要
            p2 = 0
            if nums[i] > nums[pre]:  # 要（有条件）
                p2 = process(i, i+1) + 1
            p3 = process(i+1,i+1)   # 新子序列
            return max(p1, p2, p3)
        return process(0, 0) + 1

其实主要卡在了 p3，如果令 p3=process(i,i+1) 也不对，这里我令其 p3=process(i+1,i+1) 是为了和第一次调用 (0, 0) 逻辑一致。

实际上 p3 的作用是让每一位尝试做子序列的首位，那么我们也能取出来变成 for 循环来调用去掉了 p3 的 process，然后就可以通过了。 但是超时。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def process(pre, i):
            if i == len(nums):
                return 0
            p1 = process(pre, i+1)
            p2 = 0
            if nums[i] > nums[pre]:
                p2 = process(i, i+1) + 1
            return max(p1, p2)、
        
        res = 0
        # 尝试每一个位置的元素作为最长子序列的第一位
        for ii in range(1, len(nums)):
            res = max(res, process(ii-1,ii))
        return res + 1

然而，如果我们在首位添加一个负无穷，可以确定的是所有的升序自序列一定是一第一个负无穷为第一个元素，这样就避免了遍历所有的元素并令每个元素作为升序子序列的首元素。 即我们最开始的暴力递归方法。

动态规划

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        nums.insert(0, -float('inf'))
        dp = [[0 for _ in range(len(nums)+1)] for _ in range(len(nums)+1)]
        for i in range(len(nums)-1, -1, -1):
            for pre in range(i,-1,-1):
                p1 = dp[pre][i+1]
                p2 = 0
                if nums[i] > nums[pre]:
                    p2 = dp[i][i+1] + 1
                dp[pre][i] = max(p1, p2)
        return dp[0][1]

本题一定要注意pre的填写顺序，根据pre和i的意义可知pre<i，在同列中(i相同),pre依赖的是比自己大的格子，所以pre需要倒着来。 显然，当溢出的时候为0，由于我们dp初始化就是0，因此可以省略。

解法二

思路：代码随想录的方法

不知怎么的，似乎本题的解法一有一点绕，并且坑有点多。因此这里贴过来代码随想录的方法，更好理解。

题解：

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

启发和联系