10

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

 3 years ago
source link: https://sexywp.com/300-len-of-lts.htm
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

给你一个整数数组 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 正是最后的答案。

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

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)
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 数组的最大值就是最终答案。

写出代码就是：

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)
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 —


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK