灵神基础算法精讲-20-学习笔记

300. 最长递增子序列

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

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

思路

子序列就是从数组中选择一些数，且顺序和数组中的顺序是一致的，这题要求选的子序列右边元素一定大于左边的元素，我们要做的就是在所有严格递增子序列中找到最长的子序列的长度。

例子：[1, 6, 7, 2, 4, 5, 3]

子序列本质上是数组的一个子集，可以用子集型回溯来思考。对于子集型回溯，有 选或不选 和 枚举选哪个 这两种思路，如果倒着思考，假设 3 是子序列的最后一个数，前面的数字就需要和 3 比较大小，所以需要知道当前下标以外，还需要知道上一个选的数字的下标；如果考虑枚举选哪个，可以直接枚举前面的比 3 小的数字，当作子序列的倒数第二个数，那么只需要知道当前所选的数字的下标就可以了。对比之后，发现 枚举选哪个 这种思路只需要一个参数，更加好写。

子问题：以 nums[i] 结尾的最长递增子序列的长度
当前操作：枚举 nums[j]
下一个子问题：以 nums[j] 结尾的最长递增子序列的长度

定义 dfs(i) 以 nums[i] 结尾的最长递增子序列长度，枚举满足要求的 nums[j]，问题就变成了以 nums[j] 结尾的最长递增子序列的长度，把这些子问题求一个最大值，然后再加上 nums[i] 这一个数字，就得到了以 nums[i] 结尾的最长公共子序列长度。

做法

记忆化搜索

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)

        @cache
        def dfs(i):
            res = 0
            for j in range(i):
                if nums[j] < nums[i]:
                    res = max(res, dfs(j))
            return res + 1
        
        return max(dfs(i) for i in range(n))

时间复杂度为状态个数 * 单个状态的计算时间，这里是 O(n) 个状态，计算每个状态需要 O(n) 的时间，所以时间复杂度是 O(n^2)；由于有 O(n) 个状态，所以空间复杂度是 O(n) 的。

递推

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        f = [0] * n

        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    f[i] = max(f[i], f[j])
            f[i] += 1
        return max(f)

时空复杂度和记忆化搜索相同。

优化时间复杂度

对于动态规划问题，如果想要优化时间复杂度，有一个进阶技巧，就是交换状态与状态值。

对于 f 数组，原始定义是末尾元素为 nums[i] 的最长递增子序列的长度，那么把长度和末尾元素交换一下，定义为长度为一个定值的时候，上升子序列的末尾元素的最小值，根据前面的代码，nums[j] 越小越容易满足 nums[j] < nums[i]，相同长度只需保留最小的 nums[j]

从左到右遍历这个数组，对于 1，它单独形成一个长为 1 的上升子序列，所以 g[0] = 1；接着遍历到 6，虽然 6 也可以单独形成一个长为 1 的上升子序列，但是 6 > 1，所以 g[0] 仍然是 1，6 可以和 1 组成一个长为 2 的上升子序列，所以 g[1] = 6；然后遍历到 7，现在有一个长为 3 的上升子序列，所以 g[2] = 7，把 7 添加到 g 的末尾；遍历到 2，现在有一个上升子序列 [1, 2]，所以 g[1] 变成 2，g[0] 和 g[2] 都不变；然后遍历到 4，现在有一个上升子序列 [1, 2, 4]，所以 g[2] 变成 4，以此类推。

从这个过程可以发现，当我们定义成最小值的时候，才更有机会去扩展 g 的长度，如果没有 2 和 4 的更新，这个 5 是无法组成长为 4 的上升子序列的；同时，按照这种定义方式，由于没有重叠子问题，是不能算作动态规划的，此时变成了一个贪心的问题。

研究一下 g 的性质,定理及证明如下：

因此，得到最终算法如下：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        g = []
        for x in nums:
            j = bisect_left(g, x)
            if j == len(g):
                g.append(x)
            else:
                g[j] = x
        return len(g)

时间复杂度 O(nlogn)，空间复杂度 O(n)

也可以直接把 nums 当成 g 数组，这样可以做到 O(1) 的额外空间。

用一个变量 ng 表示 g 的长度，那么直接在 nums 上二分，二分的范围限制为 [0, ng]。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        ng = 0
        for x in nums:
            j = bisect_left(nums, x, 0, ng)
            if j == ng:
                nums[ng] = x
                ng += 1
            else:
                nums[j] = x
        return ng

变形问题

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        ng = 0
        for x in nums:
            j = bisect_right(nums, x, 0, ng)
            if j == ng:
                nums[ng] = x
                ng += 1
            else:
                nums[j] = x
        return ng