【完虐算法】最长上升子序列复盘总结

你好,我是Johngo!

今天是字符串类型中另外一类需要动态规划思想解决的问题。

而且有一个很典型的 「字符串」题目,尤其是第二个例子需要静下心好好捉摸。

经过本期「字符串」的讲解,一定能够让你在关于「动态规划解字符串」方面有一个新的清晰的认识。

回顾上一期的【总监面】https://mp.weixin.qq.com/s/yfTd-NZUS-Qc8yXaAXymhQ,也就是涉及到动态规划解决公共子序列的问题。然后大学宿舍同学给出了一个完美的解决方案。

另外,可能是由于面试太过于顺利,他自己居然还把「上升子序列」的问题引出来了!

不愧是高手,要是搁一般人,能做完给定的题目,哪敢自己再引题目出来!

既然都聊到这里了。

今天把咱们计划中「字符串-最长上升子序列」问题,好好再说道说道。

说在前面

言归正传,这一期来说说字符串的第 7 块内容 「字符串 – 最长公共子序列」

github:https://leetcode-cn.com/problems/longest-common-subsequence/

文档地址:https://github.com/xiaozhutec/share_leetcode/tree/master/docs

整体架构(github中可查看完整源文件):

【完虐算法】最长上升子序列复盘总结

字符串 – 最长上升子序列

一般情况下,「最长上升子序列」会涉及到 2 种情况!

情况 1,非连续子序列

之前分享过「最长公共前缀」、「最长公共子序列」,都是针对两个以及两个以上字符串进行一些问题的解决。

所以在使用『动态规划』思想解决问题的时候,通常会借用二维以及多维数组辅助记录中间计算的数值(动态规划中的空间换时间策略)

而本文涉及到的「最长上升子序列」,肯定是针对一个字符串的问题。

那么,在使用『动态规划』的时候,也一定是会利用一维辅助数组进行问题的解决。

情况 2,连续子序列

另外呢,还有一类情况是,要得到最长连续上升子序列。

谈到连续,就要求得局部最优解了,这种情况一定会使用到的是『贪心算法』。动态规划也能解决,如果熟练之后, 发现有些地方确实是想通的!

「贪心算法」通过记录局部最优解,进而求得全局最优!

案例

整体关于字符串「最长上升子序列」方面的问题用到的解决办法无非两种!

  • 动态规划
  • 贪心算法

下面会通过 3 个典型的案例讲解,分别是 LeetCode 的三个题目:

  • 300.最长递增子序列
  • 673.最长递增子序列的个数
  • 674.最长连续递增序列

300.最长递增子序列

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

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

输入:nums = [1, 3, 6, 7, 9, 4, 10, 5, 6]
输出:6
解释:最长递增子序列是 [1, 3, 6, 7, 9, 10],因此长度为 6 。

该例子就要用到「动态规划」的思想去解决,而且使用到一维辅助数组。

还是在动态规划模块提到的四步骤,动态数组定义初始化状态转移方程优化、、。

当然,这四个步骤要灵活运用,可以充当一个解决类似问题的敲门砖。

就拿上述例子,利用四步骤进行问题的分析和解决。

一、动态数组定义

定义动态数组 dp,和 nums长度一致,即长度为 9 的数组。

动态数组 dp 每一个位置的数值代表:截止位置 i(一定包括位置 i)最长上升子序列长度。

比如 :字符串[1, 6, 7, 4],dp 数组为[1, 2, 3, 2],注意dp 的最后一位是 2,而不是 3。

dp 数组的每一位一定是截止到位置 i,而且要包括位置 i 的最长上升子序列。

因为至少也会有 1 个最长递增子序列。

所以全部初始化为 1。

【完虐算法】最长上升子序列复盘总结

二、初始化

上述全部初始化为 1 即可!

三、状态转移方程定义

位置 i 的数值大于位置 j 的数值的情况下,说明序列是上升的。

应该计算得到 dp[i] = dp[j]+1 或者 如果 dp[i] 本身如果很大的话,能取自身。这里好像有点不好理解,后面的详细步骤中会有提及,其实很简单!(下面第六轮计算得以体现~)

动态方程:

dp[i] = max(dp[i], dp[j]+1), 0<=j<=i-1 and nums[i]>nums[j]

另外,从动态转移方程的定义可以看出,每一个第 i 个位置,都要与前 0 到 i-1 位置的数字作对比。

所以,需要 i-1 轮,即 8 轮,去填充 dp 数组。

下面就案例进行每一步骤的详细说明:

第一轮:填充 dp 数组位置 1

先从位置 i=1 位置开始,由于比位置 j=0 大。

所以,dp[1]=max(dp[1], dp[0]+1) = max(1, 1+1) = 2

【完虐算法】最长上升子序列复盘总结

第二轮:填充 dp 数组位置 2

位置 i=2 的数值,比位置 j=0 大。

所以,dp[2]=max(dp[2], dp[0]+1) = max(1, 1+1) = 2

【完虐算法】最长上升子序列复盘总结

位置 i=2 的数值,比位置 j=1 大。

所以,dp[2]=max(dp[2], dp[1]+1) = max(2, 2+1) = 3

【完虐算法】最长上升子序列复盘总结

第三轮:填充 dp 数组位置 3

位置 i=3 的数值,比位置 j=0 大。

所以,dp[3]=max(dp[3], dp[0]+1) = max(1, 1+1) = 2

【完虐算法】最长上升子序列复盘总结

位置 i=3 的数值,比位置 j=1 大。

所以,dp[3]=max(dp[3], dp[1]+1) = max(2, 2+1) = 3

【完虐算法】最长上升子序列复盘总结

位置 i=3 的数值,比位置 j=2 大。

所以,dp[3]=max(dp[3], dp[2]+1) = max(2, 3+1) = 4

【完虐算法】最长上升子序列复盘总结

第四轮:填充 dp 数组位置 4

位置 i=4 的数值,比位置 j=0 大。

所以,dp[4]=max(dp[4], dp[0]+1) = max(1, 1+1) = 2

【完虐算法】最长上升子序列复盘总结

位置 i=4 的数值,比位置 j=1 大。

所以,dp[4]=max(dp[4], dp[1]+1) = max(2, 2+1) = 3

【完虐算法】最长上升子序列复盘总结

位置 i=4 的数值,比位置 j=2 大。

所以,dp[4]=max(dp[4], dp[2]+1) = max(3, 3+1) = 4

【完虐算法】最长上升子序列复盘总结

位置 i=4 的数值,比位置 j=3 大。

所以,dp[4]=max(dp[4], dp[3]+1) = max(4, 4+1) = 5

【完虐算法】最长上升子序列复盘总结

第五轮:填充 dp 数组位置 5

位置 i=5 的数值,比位置 j=0 大。

所以,dp[5]=max(dp[5], dp[0]+1) = max(1, 1+1) = 2

【完虐算法】最长上升子序列复盘总结

位置 i=5 的数值,比位置 j=1 大。

所以,dp[5]=max(dp[5], dp[1]+1) = max(2, 2+1) = 3

【完虐算法】最长上升子序列复盘总结

位置 i=5 的数值,不比位置 j=2 大。

而且 i=5 的数值,循环判断,比 j=2,3,4 的数值都小

所以,本轮结束!

第六轮:填充 dp 数组位置 6

位置 i=6 的数值,比位置 j=0 大。

所以,dp[6]=max(dp[6], dp[0]+1) = max(1, 1+1) = 2

【完虐算法】最长上升子序列复盘总结

位置 i=6 的数值,比位置 j=1 大。

所以,dp[6]=max(dp[6], dp[1]+1) = max(2, 2+1) = 3

【完虐算法】最长上升子序列复盘总结

位置 i=6 的数值,比位置 j=2 大。

所以,dp[6]=max(dp[6], dp[2]+1) = max(3, 3+1) = 4

【完虐算法】最长上升子序列复盘总结

位置 i=6 的数值,比位置 j=3 大。

所以,dp[6]=max(dp[6], dp[3]+1) = max(4, 4+1) = 5

【完虐算法】最长上升子序列复盘总结

位置 i=6 的数值,比位置 j=4 大。

所以,dp[6]=max(dp[6], dp[4]+1) = max(5, 5+1) = 6

【完虐算法】最长上升子序列复盘总结

位置 i=6 的数值,比位置 j=5 大。

所以,dp[6]=max(dp[6], dp[5]+1) = max(6, 3+1) = 6

【完虐算法】最长上升子序列复盘总结

注意:

这一步是最好诠释取 max 作用的地方:

如果不取 max 的话,这里 dp[6] 取到的就是4。

显然是不对的!

第七轮:填充 dp 数组位置 7

位置 i=7 的数值,比位置 j=0 大。

所以,dp[7]=max(dp[7], dp[0]+1) = max(1, 1+1) = 2

【完虐算法】最长上升子序列复盘总结

位置 i=7 的数值,比位置 j=1 大。

所以,dp[7]=max(dp[7], dp[1]+1) = max(2, 2+1) = 3

【完虐算法】最长上升子序列复盘总结

循环判断,直到 j=5 才比位置 i=7 的数值大。

所以,dp[7]=max(dp[7], dp[5]+1) = max(3, 3+1) = 4

【完虐算法】最长上升子序列复盘总结

位置 i=7 的数值,不比位置 j=6 大。

所以,本轮结束!!

第八轮:填充 dp 数组位置 8

位置 i=8 的数值,比位置 j=0 大。

所以,dp[8]=max(dp[8], dp[0]+1) = max(1, 1+1) = 2

【完虐算法】最长上升子序列复盘总结

位置 i=8 的数值,比位置 j=1 大。

所以,dp[8]=max(dp[8], dp[1]+1) = max(2, 2+1) = 3

【完虐算法】最长上升子序列复盘总结

循环判断,直到位置 j=5 的数值,比位置 i=8 小。

所以,dp[8]=max(dp[8], dp[5]+1) = max(3, 3+1) = 4

【完虐算法】最长上升子序列复盘总结

继续循环判断,直到位置 j=7 的数值,比位置 i=8 小。

所以,dp[8]=max(dp[8], dp[7]+1) = max(4, 4+1) = 5

【完虐算法】最长上升子序列复盘总结

以上就是整个最长递增子序列在利用动态规划思想的全部计算细节。

四、优化

在优化这个模块,动态规划在这个题目是没有优化点的, 以往都是在空间方面进行优化。

今天的案例在一维数组作为辅助的同时,需要记录每个位置的最优解,最后求得最大值。

最后,把主要的代码贴出来,看似步骤挺多,不太容易阅读,其实代码很简单:

def lengthOfLIS(self, nums):
    size = len(nums)
    if size == 1:
        return 1
    # 1.初始化dp数组,内容初始化为全1
    dp = [1 for _ in range(size)] 
    # 2.动态方程定义:dp[i] = max(dp[i], dp[j]+1), 0<=j<=i-1 and nums[i]>nums[j]
    for i in range(1, size):
        for j in range(0, i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)

现在就是最长上升子序列的第一个例题的全部分享内容。

在这个题目之后,有一个进阶的题目,会不会出现几个相同长度的最长上升子序列。

看下一个题目。

673.最长递增子序列的个数

给定一个未排序的整数数组,找到最长递增子序列的个数。

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列,分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

思路和上面的题目类似,就是多求一个最长递增子序列的个数

所以直观上来说,这里需要定义两个数组变量,一个存放最长上升子序列的长度,另外一个存放最长上升子序列的个数:

  • dp[]:到 nums[i] 为止的最长递增子序列长度
  • count[]:到 nums[i] 为止的最长递增子序列个数

最重要的一个思路点是:如果 dp[i] 的值增加了,说明长度增加,所以个数 count[i] 不加;如果 dp 值不变,说明长度未增加,个数 count[i] 对应的值要增加。

一、动态数组定义

dp[i]:到 nums[i] 为止的最长递增子序列长度;

count[i]:到 nums[i] 为止的最长递增子序列个数;

注意理解:是截止到位置 i 为止,要包含位置 i 的元素,而不是符合 <=i 之前字符串或者整体最长递增子序列。

二、初始化状态

dp = [1] * n:代表最长递增子序列的长度至少为 1

count = [1] * n:代表最长递增子序列的个数至少为 1

三、状态转移方程

对于每一个数 nums[i],看在它之前的数 numsj 是否比当前数 nums[i] 小。

辅助解释 ①:如果 nums[i]>nums[j],那么相当于到 nums[j] 为止的最长递增子序列长度到 nums[i] 增加了1,到 nums[i] 为止的最长递增子序列长度就变成了 dp[i]=dp[j]+1;

辅助解释 ②:但因为满足 nums[i]>nums[j] 的 nums[j] 不止一个,dp[i] 应该取这些 dp[j]+1 的最值,并且这些 dp[j]+1 还会有相等的情况,一旦相等,到 nums[i] 为止的最长递增子序列个数 count[i] 就应该增加了。

因此,在 nums[i]>nums[j] 的大前提下,具体的状态转移如下

3.1 如果 dp[j]+1>dp[i],说明最长递增子序列的长度增加了,dp[i]=dp[j]+1,长度增加,数量不变 count[i]=count[j]

3.2 如果 dp[j]+1==dp[i],说明最长递增子序列的长度并没有增加,但是出现了长度一样的情况,数量增加 count[i]+=count[j]

当然,在这中间需要不断记录和更新,最长递增子序列的最大长度 max_length。

最后,遍历 dp 数组,如果 dp 数组记录的最大长度 dp[i] 等于 max_length,将对应的数量 count[i] 加到结果 res 中。

该例和上一例的区别在于需要记录最长上述子序列的个数,即增加了 count[] 来记录计算的中间结果。

和上例思路相仿,下面直接给出核心代码:

def findNumberOfLIS(self, nums):
    size = len(nums)
    if size == 1:
        return 1
    # 最长递增子序列长度
    max_len = 1
    # 初始化dp和count数组,初始化为全 1
    dp = [1 for _ in range(size)]
    count = [1 for _ in range(size)]

    for i in range(1, size):
        for j in range(0, i):
            if nums[i] > nums[j]:
                if dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1
                    count[i] = count[j]
                elif dp[i] == dp[j] + 1:
                    count[i] += count[j]
            # 记录最长子序列长度
            if max_len < dp[i]:
                max_len = dp[i]
    # 获取最长子序列个数
    max_len_num = 0
    for i in range(size):
        if dp[i] == max_len:
            max_len_num += count[i]
    return max_len_num

好了,这就是利用「动态规划」的思路去解决「最长上升子序列」问题的全部解释以及两个典型例题的完整讲解。

下面也是类似的题目,但利用贪心将会极其容易的进行解决!

674.最长连续递增序列

给定一个未经排序的整数数组,找到最长且连续递增的子序列,并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], …, nums[r – 1], nums[r]] 就是连续递增子序列。

输入:nums = [1,3,5,4,7]
输出:3
解释:最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的,因为 5 和 7 在原数组里被 4 隔开。

看到这个题目之后,立马会想到的可能就是贪心算法。

既然是连续递增,而且是求解每个局部的最优值(局部局可能长的连续上升子序列),一般来说就要用贪心策略来解决了。

通过记录局部最优解,而得出全局的最优解!

通过两个下标,开始和结束,逐次比较相邻的两个元素,做出更新开始下标以及记录局部最长相邻上升子序列的操作。

初始化 start=0,然后移动 i 到后面每个位置

如果 nums[i]>nums[i-1],则 i++

如果 nums[i]<=nums[i-1],则 start=i

① start = 0, res_len = i-start+1 = 1

【完虐算法】最长上升子序列复盘总结

② start = 0, 由于nums[i] > nums[i-1],所以 i++, res_len = i-start+1 = 2

【完虐算法】最长上升子序列复盘总结

③ start = 0, 由于nums[i] > nums[i-1],所以 i++, res_len = i-start+1 = 3

【完虐算法】最长上升子序列复盘总结

④ start = 0, 由于nums[I]<nums[i-1],start=i,

此时,start = 3,res_len = max(res_len, i-start+1) = 3。

也就是当 start 被重新赋值之后,取最后结果的时候,需要判断之前的长度和当前长度,取其大值!

【完虐算法】最长上升子序列复盘总结

⑤ start = 3, 由于nums[i] > nums[i-1],所以 i++。

此时,当前局部的长度还是小于之前局部的长度值。故 res_len = max(res_len, i-start+1) = 3。

【完虐算法】最长上升子序列复盘总结

其实看到最后,发现整体的思路依旧是动态规划。只是把 res_len 变量设为一个值。

如果把 res_len 设为一个数组,就会更加清晰了。

再补充一句,此时的解法是相较于设为数组解法优化后的方法,即在空间上进行了优化。

下面看下核心代码:

def findLengthOfLCIS(self, nums):
    size = len(nums)
    start = 0
    res_len = 0
    for i in range(size):
        if nums[i] <= nums[i-1]:
            start = i
        res_len = max(res_len, i-start+1)

    return res_len

很短,不过这也属于一道简单题目。

好了,今年就是关于「字符串-最长上升子序列」的全部分享,这类型题目在面试中有过大量的出现,如果你有遇到过也可以在评论区留言,给到其他同学一些建议。

发布者:Johngo学长。文章已受到原创版权保护。
转载请注明出处:https://www.johngo689.com/3724/

(0)
上一篇 2022年1月5日 下午2:53
下一篇 2022年1月21日 下午2:44

相关推荐

发表评论

登录后才能评论
免费咨询
免费咨询
扫码关注
扫码关注
联系站长

站长Johngo!

大数据和算法重度研究者!

持续产出大数据、算法、LeetCode干货,以及业界好资源!

2022012703491714

微信来撩,免费咨询:xiaozhu_tec

分享本页
返回顶部