11｜动态规划新问题1：攻破最长递增子序列问题
卢誉声
你好，我是卢誉声。
还记得我们在上个模块中讲解的子数组和子序列问题吗？相较于较为复杂的子序列问题，它的答案不一定连续；我们还讲解了子数组问题，这类问题的答案是连续的。因此，这两者之间最大的区别，其实就在于答案是否连续。
随着时间的推移，面试官们也往往不再满足于考察传统的动态规划问题了，即便涉及了子序列和子数组问题。所以，在这一课中，我将带着你一起掌握最长递增序列的问题。
在本课的最后，我还会给出完整的攻破子序列的解题模板。还是那句话，由于是经验总结，因此在 90% 以上的情况下这个模板（套路）都是工作的，它足以应对你可能遇到的所有面试问题。
既然准备要解决的问题是最长递增序列，这就会涉及到子数组和子序列两种情况。你也无需担心，今天我会为你讲解这两种情况。那么按照惯例，在开始前，我先提出一个简单的问题：在处理递增序列时，连续和不连续的答案会对状态转移方程产生什么影响？
接下来就让我们带着这个问题，开始今天的学习之旅吧。
最长连续递增序列
我们先从一个较为简单的递增序列问题说起，从题目本身就可以看出，这是一个基于子数组的递增序列问题。我们看到这样的题目时，首先就要有一个意识，那就是所求答案肯定是连续的。既然如此，我们先看看问题的描述。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
动态规划算法在解决最长递增子序列问题中发挥着重要作用。本文深入介绍了动态规划中的最长递增子序列问题，包括最长连续递增序列和最长上升子序列的长度问题。作者通过分析算法问题，提出了状态转移方程，并给出了Java和C++的实现代码。文章通过具体的问题分析和代码实现，帮助读者理解了动态规划在解决最长递增子序列问题中的应用。此外，文章还讨论了最长上升子序列的数量问题，并给出了相应的问题描述和示例。最后，文章总结了算法的时间复杂度和空间复杂度，并强调了备忘录的定义对于状态转移方程的重要性。整体而言，本文为读者提供了深入的动态规划算法知识，并通过具体问题的讲解和代码实现，帮助读者更好地理解和应用动态规划算法。文章内容涵盖了动态规划中子序列问题的解题模板，为读者提供了全面的总结和经验套路，适用于解决各类面试问题。文章还提供了解决子序列问题的解题模板和套路，以及一些优化算法时间复杂度和空间复杂度的思考。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《动态规划面试宝典》，新⼈⾸单¥59
《动态规划面试宝典》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(6)
- 最新
- 精选
Roy Liang最长连续递增序列那里： >>最后，我们来看一看决策是什么。考虑一下，在什么情况下，当前子问题的解需要根据子问题的子问题计算得出呢？原问题问的是最长连续递增序列。因此，当 DP[i]>DP[i−1] 时，我们需要更新当前子问题的答案，这就是该问题的决策。 这里的条件DP[i]>DP[i−1]是不是有笔误？应该是nums[i] > nums[i-1]，后面的代码就是这样的作者回复: 笔误。感谢指正。
2020-10-202
BBQ#借助一个单调递增数组，用二分法将最长子序列的复杂度变为 nlogn def lengthOfLIS(self, nums: List[int]) -> int: if not nums: return 0 #dp = [0] * len(nums) tail = [nums[0]] #准备 tail数组，如果大于tail[-1] 就加上去，如果小于，就找到第一个大于等于target的，替换掉 for i in range(1, len(nums)): if nums[i] > tail[-1]: tail.append(nums[i]) else: left, right = 0, len(tail) - 1 while left < right: mid = left + ((right-left)>>1) if tail[mid] < nums[i]: left = mid + 1 else: right = mid tail[left] = nums[i] #替换掉 return len(tail)作者回复: 没有问题，每个问题就应该多加思考，这样遇到类似问题才能真的举一反三。极力提倡大家尽量自己多思考，不断优化解法，才能融会贯通，真正把知识变成自己的东西。 顶顶顶
2021-03-071- Geek_b16406如果count[i]定义为长度为i的最长子序列，则不需要状态转移方程。只需要再“最长递增子序列长度”代码的基础上稍作修改，不用额外的两个for循环
作者回复: 这样的话需要在上面的循环里去根据现在count[i]的逻辑来处理这个数量，其实和加一个循环在时间复杂度上没有差别，也是可以实现的。文中是想把两个逻辑尽量分开，便于解读。
2022-07-14归属地：上海2 - Geek_f8ca86最长连续递增序列的备忘录意义，应该是以i为结尾的最长连续递增序列，而不是从0到i吧？
作者回复: 恩，的确应该是以 i 为结尾的最长连续递增序列，res是0到i中的最长连续递增序列。正文做了更新和修正，感谢指正！
2021-03-09 - CD另外层循环的数字下标为 j，内部循环的数字下标为 i 大家都是最外层 i 里面是j
作者回复: 这是由于在讲述过程中假设 i ... j （i < j） 的缘故。
2020-10-26 
我来也老师将 最长上升子序列长度 变种到 求数量，就理解为什么要留这个课后思考题了。 课后思考题： 利用二分查找，将内层循环到时间复杂度从O（n）降低到O（logn）。 偷个懒 直接上链接： https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti作者回复: 很好，所有的题目都要自己动手验证。
2020-10-09
收起评论
