使用递归求解《最长递增子序列》

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

300. 最长递增子序列 <– 传送门

这道题目是一道非常经典的基础算法题。

一个数组里包含多少个子序列呢？按照数组原有的顺序，每个元素我们可以选择删除或者保留，最后形成的序列，就是一个子序列。每个位置有“删除”或“保留” 2 种情况，所以，穷举的话，总共有 2^n 个子序列。

这些子序列的长度，从 0 到 n 不等，我们现在想求出，子序列中元素严格递增的序列，最长的长度是多少。不难得到，最短的严格递增子序列长度是 1，最长的可能性是 n。也同样不难想象，某一个长度的严格递增子序列，不止一条。

解法一，递归

我们尝试使用递归法，来设计一个算法，求解这道题。下面是推理过程：

步骤 1，递归假设。我们直接假设，可以求出长度为 n 的数组的最长递增子序列的长度，也即最终答案，用 f(n) 表示。

在这个基础上，我们来考察第 n + 1 个数，我们能否使用 f(n) 计算出来。一个数字能不能让一个递增序列的长度 +1，取决于这个数字是否大于序列中最大的数字（因为是要保持数组的原有顺序，不用考虑这个数字是否小于最小值的情况）。现有递归假设，不包含那个最大值，所以假设失败。

增强假设。我们除了能计算出最长子序列的长度，我们还能计算这个子序列的最大值。考虑到，同样长度的子序列很多个，那么这么多子序列的最大值，我们返回哪个呢？稍加思考，发现，我们可以返回这里最小的一个，记为 Xs。因为新来一个数字，只要比 Xs 大，就可以让最长子序列的长度 +1 了。

在新的假设基础上，我们考察第 n + 1 个数，如果这个数字大于 Xs，那么 f(n+1) 的最长子序列，就是 f(n) 的最长长度 +1。那么，新的最长子序列的最大值是多少呢？显然也是第 n + 1 个数。可是如果第 n + 1 个数，小于 Xs 怎么办？假如 f(n) 计算的最长子序列长度是 L，最大值是 Xs，第 n + 1 个数字小于 Xs，但是比长度 L-1 的子序列的最大值要大，就可以得到另一条长度 L 的子序列，那条子序列的最大值是第 n + 1 个数，这种情况，需要更新 Xs 为第 n + 1 个数。那还是同样的问题，如果小于又怎么办呢？还要用同样的办法再向前探索 L-2 的子序列最大值。

这一部分稍微有点点抽象，但是细想一下不难理解的。所以，我们目前的假设，还是不够强。

继续增强假设。假设我们能计算出，长度从 1 到 L 的每种长度的子序列的最大值（里面的最小的一个）。

在这个最新的假设下，考察第 n + 1 个数。通过第 n + 1 个数与整个数组的每一个数，从后往前逐个判断，就能决定是追加到最后面，还是替换其中的一个。不难证明，返回的这 L 个数字，是从小到大严格递增的（所以可以用二分法找到替换的位置）。最后这个数组的长度 L 正是最后的答案。

基于上面的推理，我们写出递归算法：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def lis(i: int) -> List[int]:
            if i == 0: return [nums[i]]
            res = lis(i - 1)
            # 以下使用二分法，确认替换的位置
            j = bisect.bisect_left(res, nums[i])
            if j == len(res): # 比最大的还大，就追加到末尾
                return res + [nums[i]]
            else:             # 否则就替换
                res[j] = nums[i]
                return res
        return len(lis(len(nums) - 1)

算法复杂度分析，每一轮递归里，问题规模减小 1，总递归 n 层，并且每层进行了一次二分查找。所以总时间复杂度是 O(n logn)。空间复杂度是 O(n)。

通过递归假设和不断增强假设，我们设计出了递归算法来求解最长递增子序列。这道题也可以很轻松写成迭代的写法，请读者自己动手完成。

解法二、动态规划

当然，这也是一道典型的动态规划的题型，可以用动态规划来求解。假设我们可以设状态为以第 i 个数字结尾的最长子序列，长度为 Li。对于第 i + 1个数字，我们可以检查每个数字 i ，如果大于它，新子序列的长度 Li + 1，这里的最大值就是以第 i + 1 个数字结尾的最长递增子序列长度。

因为，最长子序列不一定是以哪个值结尾的，所以最后整个 dp 数组的最大值就是最终答案。

写出代码就是：

1
2
3
4
5
6
7
8

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums) # 不难想象，最短的递增子序列长度是 1，当作初始值
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

该算法的时间复杂度是 O(n^2)，因为每个数字，我们都要考察前面所有的数字的情况。空间复杂度是 O(n)。

– END –