专栏首页小浩算法漫画:动态规划系列 第三讲

漫画:动态规划系列 第三讲

在上一篇中,我们了解了什么是DP(动态规划),并且通过DP中的经典问题 "最大子序和",学习了状态转移方程应该如何定义。在本节中,我们将沿用之前的分析方法,通过一道例题,进一步巩固之前的内容!

01

第300题:最长上升子序列

第300题:给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]

输出: 4

解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

说明:

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

本题有一定难度!

如果没有思路请回顾上一篇的学习内容!

不建议直接看题解!

02

题目图解

首先我们分析题目,要找的是最长上升子序列(Longest Increasing Subsequence,LIS)。因为题目中没有要求连续,所以LIS可能是连续的,也可能是非连续的。同时,LIS符合可以从其子问题的最优解来进行构建的条件。所以我们可以尝试用动态规划来进行求解。首先我们定义状态:

dp[i] :表示以nums[i]结尾的最长上升子序列的长度

我们假定nums为[1,9,5,9,3]

我们分两种情况进行讨论:

  • 如果nums[i]比前面的所有元素都小,那么dp[i]等于1(即它本身)(该结论正确)
  • 如果nums[i]前面存在比他小的元素nums[j],那么dp[i]就等于dp[j]+1(该结论错误,比如nums[3]>nums[0],即9>1,但是dp[3]并不等于dp[0]+1)

我们先初步得出上面的结论,但是我们发现了一些问题。因为dp[i]前面比他小的元素,不一定只有一个!

可能除了nums[j],还包括nums[k],nums[p] 等等等等。所以dp[i]除了可能等于dp[j]+1,还有可能等于dp[k]+1,dp[p]+1 等等等等。所以我们求dp[i],需要找到dp[j]+1,dp[k]+1,dp[p]+1 等等等等中的最大值。(我在3个等等等等上都进行了加粗,主要是因为初学者非常容易在这里摔跟斗!这里强调的目的是希望能记住这道题型!)

即:

dp[i] = max(dp[j]+1,dp[k]+1,dp[p]+1,.....)

只要满足:

nums[i] > nums[j]

nums[i] > nums[k]

nums[i] > nums[p]

....

最后,我们只需要找到dp数组中的最大值,就是我们要找的答案。

分析完毕,我们绘制成图:

03

Go语言示例

根据分析,得到代码:

func lengthOfLIS(nums []int) int {
    if len(nums) < 1 {
        return 0
    }
    dp := make([]int, len(nums))
    result := 1
    for i := 0; i < len(nums); i++ {
        dp[i] = 1
        for j := 0; j < i; j++ {
            //这行代码就是上文中那个 等等等等
            if nums[j] < nums[i] {
                dp[i] = max(dp[j]+1, dp[i])
            }
        }
        result = max(result, dp[i])
    }
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

注:本系列所有教程中都不会用到复杂的语言特性,大家不需要担心没有学过go。算法思想最重要,使用go纯属本人爱好。同时,本系列所有代码均在leetcode上进行过测试运行,保证其严谨性!

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:浩仔

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《剑指offer》第28天:最长上升子序列(高频)

    首先我们分析题目,要找的是最长上升子序列(Longest Increasing Subsequence,LIS)。因为题目中没有要求连续,所以 LIS可能是连续...

    程序员小浩
  • 漫画:动态规划系列 第二讲

    在上一篇文章中,我们讲解了DP的概念并且通过示例了解了什么是动态规划。本篇中,我们将继续通过1道简单题型,进一步学习动态规划的思想。

    程序员小浩
  • 《剑指offer》第26天:最大子序和

    首先我们分析题目,一个连续子数组一定要以一个数作为结尾,那么我们可以将状态定义成如下:

    程序员小浩
  • 程序员面试金典 - 面试题 16.17. 连续数列(DP/分治)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/contiguous-sequence-lcci 著...

    Michael阿明
  • 每日算法系列【LeetCode 376】摆动序列

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

    godweiyang
  • 《剑指offer》第28天:最长上升子序列(高频)

    首先我们分析题目,要找的是最长上升子序列(Longest Increasing Subsequence,LIS)。因为题目中没有要求连续,所以 LIS可能是连续...

    程序员小浩
  • Leetcode 300. 最长上升子序列(n方dp,nlogn贪心+二分查找)

    d[i]表示长度为i的末尾元素值,遍历一遍nums,遇到比当前d[len]元素大的就接在后面,否则就二分插入d[1~len]中的某个位置~

    glm233
  • 动态规划设计

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

    黑白格
  • 漫画:动态规划系列 第二讲

    在上一篇文章中,我们讲解了DP的概念并且通过示例了解了什么是动态规划。本篇中,我们将继续通过1道简单题型,进一步学习动态规划的思想。

    程序员小浩
  • 【leetcode刷题】T170-组合总和 Ⅳ

    https://leetcode-cn.com/problems/combination-sum-iv/

    木又AI帮

扫码关注云+社区

领取腾讯云代金券