序列型动态规划——最长递增子序列

本是古典何须时尚 2022-10-27 06:28 201阅读 0赞

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

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

**示例 ：**

输入：nums = [10,9,2,5,3,7,101,18]
    输出：4
    解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

### 1、题目分析 ###

这是典型的序列类型动态规划题目。

### 2、确定状态 ###

最后一份：对于最优的策略，一定有最后一个元素a\[j\]。

第一种情况：最优策略中最长上升子序列为\{a\[j\]\}，答案就是1

第二种情况子序列长度大于1，那么最优策略中a\[j\]前一个元素是a\[i\]，并且a\[i\]<a\[j\]。

因为是最优策略，那么它选中的以a\[j\]结尾的上升子序列一定是最长的。

但是因为不确定a\[j\]前一个元素是谁，因此需要枚举每个i，转化为子问题：i<j。

综上所述，我们可以假设状态：f\[i\]表示以a\[i\]结尾的最长上升子序列的长度。

### 3、转移方程 ###

f\[i\]表示以a\[i\]结尾的最长上升子序列的长度。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]

### 4、初始条件和边界情况 ###

情况2必须满足i>0,a\[j\]>a\[i\]，满足单调性

初始条件：空

### 5、计算顺序 ###

从小大到计算。

答案是max\{f\[0\],f\[1\],f\[2\]……,f\[n-1\]\}

算法时间复杂度O(n\*n)，空间复杂度O(n)

### 6、代码实现 ###

class Solution:
        def lengthOfLIS(self, nums: List[int]) -> int:
            if len(nums)==0:
                return 0
            dp = [0 for i in range(len(nums))]
            dp[0]=1
            max1 = 1
            for i in range(1,len(nums)):

#  #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]: /images/20221024/7f4ea969eb3c466b99cfd5bc758835e1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，201人围观）

还没有评论，来说两句吧...

相关阅读

相关 300. 最长递增子序列（动态规划）

300. 最长递增子序列题目解题思路代码题目给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来

﹏ヽ暗。殇╰゛Y/ 2023年10月05日 18:23/ 0 赞/ 19 阅读

相关动态规划之最长递增子序列

[300. 最长递增子序列][300.] 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或

痛定思痛。/ 2023年09月30日 21:14/ 0 赞/ 5 阅读

相关 LeetCode300. 最长递增子序列【动态规划】

难度：`中等` 题目描述： > 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 > 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改

喜欢ヅ旅行/ 2023年01月21日 14:22/ 0 赞/ 183 阅读

相关序列型动态规划——最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，\[3,6,2,7\

本是古典何须时尚/ 2022年10月27日 06:28/ 0 赞/ 202 阅读

相关 673 最长递增子序列的个数（动态规划-最长上升子序列）

1. 问题描述：给定一个未排序的整数数组，找到最长递增子序列的个数。示例 1: 输入: \[1,3,5,4,7\] 输出: 2 解释: 有两个最长递增子序列，

雨点打透心脏的1/2处/ 2022年09月02日 12:51/ 0 赞/ 211 阅读

相关动态规划--最长递增子序列

对于一个数字序列，请设计一个复杂度为O(nlogn)的算法，返回该序列的最长上升子序列的长度，这里的子序列定义为这样一个序列U1，U2...，其中Ui < Ui+1，且A\[U

待我称王封你为后i/ 2022年08月18日 02:17/ 0 赞/ 182 阅读

相关【动态规划】最长递增子序列

题目：求一个无序数组中最长的递增子序列。例如： 1,3,2,5,4,6的最长递增子序列的长度是4。12446和1346。解析:直接给出动态规划的解，dp\[i\]表示以ar

￡神魔★判官ぃ/ 2022年08月09日 02:08/ 0 赞/ 212 阅读

相关算法-动态规划解决最长递增子序列

题目描述：给出一个序列 a1,a2,a3,a4,a5,a6,a7....an,求它的一个子序列（设为s1,s2,...sn），使得这个子序列满足这样的性质，

偏执的太偏执、/ 2022年07月24日 06:18/ 0 赞/ 197 阅读

相关动态规划问题 —— 最长递增子序列

题目描述链接：[https://www.nowcoder.com/questionTerminal/585d46a1447b4064b749f08c2ab9ce66][

忘是亡心i/ 2022年04月24日 03:52/ 0 赞/ 221 阅读

相关动态规划最长递增子序列

方法一：最长公共子序列法将问题转换成求递增排序的数组与原数组的最长公共子序列。不知道如何排序？看这里： [七大排序算法总结][Link 1] 不知道什么是最长

小咪咪/ 2021年10月01日 09:00/ 0 赞/ 353 阅读