LeetCode 动态规划专题 8：最长上升子序列问题

作者: 李威威 | 来源:发表于2019-05-28 23:17 被阅读2次

例题：LeetCode 第 300 题：Longest Increasing Subsequence

传送门：英文网址：300. Longest Increasing Subsequence ，中文网址：300. 最长上升子序列。

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

分析：首先仔细审题，明确题目中的条件。

1、子序列：不要求连续子序列，只要保证元素前后顺序一致即可；

2、上升：这里的“上升”是“严格上升”，类似于 [2, 3, 3, 6, 7] 这样的子序列是不符合要求的；

一个序列可能有多个最长上升子序列，题目中只要我们求这个最长的长度。如果使用回溯搜索，选择所有的子序列进行判断，时间复杂度为 $O( (2^n) * n )$ 。

思路1：动态规划。这个问题具有“最优子结构”。

定义状态：LIS(i) 表示以第 i 个数字为结尾的最长上升子序列的长度。即在 [0, ..., i] 的范围内，选择以数字 nums[i] 结尾可以获得的最长上升子序列的长度。关键字是：以第 i 个数字为结尾，即我们要求 nums[i] 必须被选取。反正一个子序列一定要以一个数字结尾，那我就将状态这么定义，这一点是重要且常见的。

状态转移方程：遍历到索引是 i 的数的时候，我们应该把索引是 [0, ... ,i - 1] 的 LIS 都看一遍，如果当前的数 nums[i] 大于之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的 LIS 。把前面的 i 个数都看了， LIS[i] 就是它们的最大值加 $1$ 。即比当前数要小的那些里头，找最大的，然后加 $1$ 。

状态转移方程即：LIS(i) = max( 1 + LIS(j) if j < i and nums[i] > nums[j])

最后不要忘了，应该扫描一遍这个 LIS[i] 数组，其中最大的就是我们所求的。

我们以下面的数组为例进行说明：

例如：[10，9，2，5，3，7，101，18]。

填表：

原始数组	10	9	2	5	3	7	101	18
LIS 刚开始的值	1	1	1	1	1	1	1	1
LIS 最后的值	1	1	1	2	2	3	4	4

最关键的就是填这张表，其实并不难。最后，我们把整个数组扫描一遍，就找到了最大值。

又例如：[10，15，20，11，9，101]。

原始数组	10	15	20	11	9	101
LIS 刚开始的值	1	1	1	1	1	1
LIS 最后的值	1	2	3	2	1	4

Python 代码：关键：找它前面比他小的那些数中最大的

class Solution:

    # 动态规划的思路：将 dp 数组定义为：以 nums[i] 结尾的最长上升子序列的长度
    # 那么题目要求的，就是这个 dp 数组中的最大者
    # 以数组  [10, 9, 2, 5, 3, 7, 101, 18] 为例：
    # dp 的值： 1  1  1  2  2  3  4    4

    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        size = len(nums)
        if size <= 1:
            return size
        dp = [1] * size
        for i in range(1, size):
            for j in range(i):
                if nums[i] > nums[j]:
                    # + 1 的位置不要加错了
                    dp[i] = max(dp[i], dp[j] + 1)
        # 最后要全部走一遍，看最大值
        return max(dp)

Java 代码：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return len;
        }
        int[] dp = new int[len];
        // 自己一定是一个子序列
        Arrays.fill(dp, 1);
        for (int i = 1; i < len; i++) {
            // 看以前的，比它小的，说明可以接在后面形成一个更长的子序列
            // int curMax = Integer.MIN_VALUE; 不能这样写，万一前面没有比自己小的，
            // 这个值就得不到更新
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }

        int res = dp[0];
        for (int i = 0; i < len; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

LIS 问题的 $O(nlogn)$ 解法请看这里。如果用二分法解决，其中含有贪心思想（因为在一个更小的数后面，才有可能接更大的数。规律：如果比最后一个大，直接接在后面，否则就要执行一次更新操作：找到第 1 个比它大的数，更新它）

例如：1 2 3 4 5 7（更新成 6） 7 7 7 7 7 8 9 来了一个 6。

记忆化递归的解法。有 $O(n \log n)$ 复杂度的解法。

思路：自己写一个辅助数组，用二分查找完成数组的覆盖或者插入，遍历完整个输入数组，辅助数组的长度就是所求。其实这道题的一个子过程就是 LeetCode 第 35 题：搜索插入位置。这个思路用到的策略是贪心算法，技巧和二分查找。

关键在于找大于等于“当前遍历的那个数”的第 1 个索引，将它替换成“当前遍历的那个数”，这样使得这个数变小，后面才有可能接一个更大的数。

LeetCode 第 300 题：Longest Increasing Subsequence-1

LeetCode 第 300 题：Longest Increasing Subsequence-2

LeetCode 第 300 题：Longest Increasing Subsequence-3

Python 代码：

class Solution:
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        size = len(nums)
        if size < 2:
            return size
        # 最长上升子序列
        lis = []
        for num in nums:
            # 找到大于等于 target 的第 1 个数
            l = 0
            r = len(lis)
            while l < r:
                mid = l + (r - l) // 2
                if lis[mid] >= num:
                    r = mid
                else:
                    l = mid + 1
            if l == len(lis):
                lis.append(num)
            else:
                lis[l] = num
        return len(lis)


if __name__ == '__main__':
    nums = [10, 9, 2, 5, 3, 7, 101, 18]
    solution = Solution()
    result = solution.lengthOfLIS(nums)
    print(result)

说明：这道题还可以用动态规划来完成。

练习：LeetCode 第 376 题：摆动序列

传送门：376. 摆动序列。

一个序列，它的相邻数字的大小关系是升序降序轮流交替的（最初可以是升序，也可以是降序），就称为wiggle sequence。比如[1, 7, 4, 9, 2, 5] 就是一个wiggle sequence。但是[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 就不是。给出一个数组，求出他的最长 wiggle sequence 子序列。

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例 1:
输入: [1,7,4,9,2,5]
输出: 6 
解释: 整个序列均为摆动序列。
示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:
输入: [1,2,3,4,5,6,7,8,9]
输出: 2
进阶:
你能否用 O(n) 时间复杂度完成此题?

思路1：状态机。贪心算法，每一次都让非严格上升或者非严格下降的长度最长，这样后面遇到一个下降的元素才会使得摇摆的序列变得更长。

注意：初始状态不能单独拿出来判断，因为有这种特例：[1,1,1,1,17,5,10,13,15,10,5,16,8]。

Python 代码：

class Solution:
    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        size = len(nums)
        if size < 2:
            return size
        # [1,17,5,10,13,15,10,5,16,8]

        # 0 表示初始状态，1 表示上升，2 表示下降
        res = 1
        state = 0

        for i in range(1, size):
            if state == 0:
                if nums[i - 1] > nums[i]:
                    res += 1
                    state = 2
                    continue
                if nums[i - 1] < nums[i]:
                    state = 1
                    res += 1
                    continue

            if state == 1 and nums[i - 1] > nums[i]:
                res += 1
                state = 2
                continue
            if state == 2 and nums[i - 1] < nums[i]:
                res += 1
                state = 1
        return res


if __name__ == '__main__':
    solution = Solution()
    nums = [1, 1, 7, 4, 9, 2, 5]
    result = solution.wiggleMaxLength(nums)
    print(result)

思路2：动态规划。抓住一点：增加之后，再增加，最长摇摆子序列的长度不变，只有减少了最长摇摆子序列的长度才会加 1。

up[i]：到第 i 个元素为止最后状态是“上升”的最长“摆动”序列长度；

down[i]：到第 i 个元素为止最后状态是“下降”的最长“摆动”序列长度；

遍历数组，从第 2 个元素开始（即索引为 1 开始）比较它与前一个元素的值。

如果 nums[i - 1] < nums[i]，表明第 i - 1 到第 i 个元素是上升的，因此 up[i] 只需在down[i-1] 的基础上加 $1$ 即可，而 down[i] 保持不变，即 down[i] = down[i - 1]。

总结一下：

如果它大于前一个元素，就根据 down 数组的最后一个值更新 up 数组的值；

如果它小于前一个元素，就根据 up 数组的最后一个值更新 down 数组的值；

如果它等于前一个元素，两个数组的值都不更新。

Python 代码：

class Solution:
    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        size = len(nums)
        if size == 0:
            return 0
        # 从第 2 个元素开始，当前元素比上一个元素大的时候，能够构成的最长摇摆子序列的长度，否则，该值与之前的值相等
        up = [0 for _ in range(size)]
        # 从第 2 个元素开始，当前元素比上一个元素小的时候，能够构成的最长摇摆子序列的长度，否则，该值与之前的值相等
        down = [0 for _ in range(size)]

        up[0] = 1
        down[0] = 1
        for i in range(1, size):
            if nums[i - 1] < nums[i]:
                # 下降
                up[i] = up[i - 1]
                down[i] = up[i - 1] + 1
            elif nums[i - 1] > nums[i]:
                # 上升：表示当前这个元素可以接在 down 所表示的最长摇摆子序列的最后一个，构成一个更长的子序列
                # 此时更新 up 的值，它根据 down 的最后一个 + 1
                # 理解这一步很关键，这一步理解清楚了，其它两个分支就自然清楚了
                up[i] = down[i - 1] + 1
                down[i] = down[i - 1]
            else:
                up[i] = up[i - 1]
                down[i] = down[i - 1]
        return max(up[-1], down[-1])

因为状态只与前一个值有关，于是有下面更节约空间复杂度的写法。

Python 代码：

class Solution:
    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        size = len(nums)
        if size == 0:
            return 0
        up = 1
        down = 1
        for i in range(1, size):
            if nums[i - 1] < nums[i]:
                down = up + 1
            elif nums[i - 1] > nums[i]:
                up = down + 1
        return max(up, down)

（本节完）

LeetCode 动态规划专题 8：最长上升子序列问题

例题：LeetCode 第 300 题：Longest Increasing Subsequence

练习：LeetCode 第 376 题：摆动序列

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

动态规划