leetcode300. 最长递增子序列,动态规划附状态转移方程
leetcode300. 最长递增子序列
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1:
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
输入:nums = [0,1,0,3,2,3]
输出:4
示例 3:
输入:nums = [7,7,7,7,7,7,7]
输出:1

目录
- leetcode300. 最长递增子序列
- 子序列与子串的区别
- 子序列(Subsequence)
- 子串(Substring)
- 总结
- 最长递增子序列问题
- 题目描述
- 题目分析
- 算法
- 状态转移方程
- 初始化
- 遍历进行状态转移
- 返回结果
- 算法流程
- 代码实现
- 打表过程
- 最终结果
- 算法分析
- 易错点
- 相似题目
子序列与子串的区别
子序列(Subsequence)
- 定义:一个给定序列的子序列是从原序列中在不改变序列顺序的情况下删除某些元素(也可以不删除任何元素)而形成的序列。
- 特点:
- 不需要连续。
- 保持元素的原有顺序。
- 示例:对于序列
A = [5, 1, 22, 25, 6, -1, 8, 10],[5, 22, 25]和[1, 6, -1]都是它的子序列。
子串(Substring)
- 定义:子串是指从原字符串中连续取出的一部分。
- 特点:
- 必须连续。
- 保持元素的原有顺序。
- 示例:对于字符串
S = "abcdefg","abc"和"def"都是它的子串。
总结
- 主要区别:子序列不要求连续,而子串必须是连续的。
最长递增子序列问题
题目描述
给定一个整数数组,找到最长的递增子序列的长度。
题目分析
这是一个经典的动态规划问题。我们可以通过计算以每个元素为结尾的最长递增子序列的长度来最终得到整个数组的最大递增子序列长度。
算法
状态转移方程
- 定义:
dp[i]表示以nums[i]为结尾的最长递增子序列的长度。 - 转移方程:
dp[i] = max(dp[i], dp[j] + 1),其中0 <= j < i且nums[i] > nums[j]。 - 解释:
- 如果
nums[i]大于nums[j],那么nums[i]可以加到以nums[j]结尾的递增子序列的末尾,形成一个新的更长递增子序列。 - 因此,我们需要更新以
nums[i]结尾的最长递增子序列的长度。 max(dp[i], dp[j] + 1)确保了对于每个nums[i],我们选择一个最优的dp[j]来形成新的递增子序列。
- 如果
初始化
dp[i] = 1,因为任何单个元素自身都是一个递增子序列。
遍历进行状态转移
- 遍历数组,对于每个元素
nums[i],再遍历其之前的所有元素nums[j],如果nums[i] > nums[j],则更新dp[i]。
返回结果
- 返回
dp数组中的最大值,即为最长递增子序列的长度。
算法流程
代码实现
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();if (n == 1) return 1;int result = 0;vector<int> dp(n, 1);for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = max(dp[j] + 1, dp[i]);}}result = max(result, dp[i]);}return result;}
};
打表过程

最终结果
- 最长递增子序列长度为
4,对应于dp[7]。
算法分析
- 时间复杂度:O(n^2),因为我们需要遍历数组中的每个元素,对于每个元素,我们又需要遍历其之前的所有元素。
- 空间复杂度:O(n),用于存储 DP 数组。
易错点
- 注意在遍历时正确应用状态转移方程。
- 确保在更新
dp[i]时考虑所有可能的dp[j]。
相似题目
| 题目 | 链接 |
|---|---|
| 最长连续递增序列 | LeetCode 674 |
| 俄罗斯套娃信封问题 | LeetCode 354 |
| 最长公共子序列 | LeetCode 1143 |
相关文章:
leetcode300. 最长递增子序列,动态规划附状态转移方程
leetcode300. 最长递增子序列 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2…...
C语言:字符串函数strcpy
该函数用于字符串的拷贝。 使用方法如下: #include<stdio.h> #include<string.h>int main() {char str[10];char* str1 "abcd";//strcpy(str, str1);//把str1复制到str,但此函数不安全所以用strcpy_sstrcpy_s(str, 10, str1);/…...
Day16-指针2
数组指针与指针数组 变量指针:指向变量的地址。 数组指针:指向数组的地址。 指针变量:存放其他变量地址的变量。 指针数组:存放数组元素指针的变量。 数组指针 概念:数组指针是指向数组的指针。特点: 先…...
数据结构(5.5_3)——并查集的进一步优化
Find操作的优化(压缩路径) 压缩路径——Find操作,先找到根节点,再将查找路径上所有结点都挂到根结点下 代码: //Find "查"操作优化,先找到根节点,再进行"路径压缩" int Find(int S[], int x) {…...
(回溯) LeetCode 131. 分割回文串
原题链接 一. 题目描述 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串。返回 s 所有可能的分割方案。 示例 1: 输入:s "aab" 输出:[["a","a","b"],[…...
【Linux】阻塞信号|信号原理|深入理解捕获信号|内核态|用户态|sigaction|可重入函数|volatile|SIGCHILD|万字详解
目录 编辑 一,常见的信号术语 二,信号在内核中的表示 信号标志位 Pending表 Block表 handler表 POSIX.1标准 三,sigset_t 信号集操作函数 sigemptyset sigfillset sigaddset sigdelset sigismember sigprocmask sig…...
基于Linux对 【进程地址空间】的详细讲解
研究背景: ● kernel 2.6.32 ● 32位平台 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀– 在学习操作系统中想必大家肯定都见过下面这…...
[python]使用Pandas处理多个Excel文件并汇总数据
在数据分析和处理过程中,经常需要处理多个Excel文件,并将其中的数据进行汇总和分析。本文介绍使用Python的Pandas库来读取多个Excel文件,并汇总不同类型的数据,例如员工工资、工件数量等。 代码示例 以下是一个完整的代码示例&a…...
提升体验:UI设计的可用性原则
在中国,每年都有数十万设计专业毕业生涌入市场,但只有少数能够进入顶尖企业。尽管如此,所有设计师都怀揣着成长和提升的愿望。在评价产品的用户体验时,我们可能会依赖直觉来决定设计方案,或者在寻找改善产品体验的切入…...
x264 编码器 SSIM 算法源码分析
SSIM SSIM(Structural Similarity Index)是一种用于衡量两幅图像之间视觉相似度的指标。它不仅考虑了图像的亮度、对比度和饱和度,还考虑了图像的结构信息。SSIM的值介于-1到1之间,值越接近1表示两幅图像越相似。 SSIM是基于以下三个方面来计算的: 亮度(Luminance):比…...
echarts使图表组件根据屏幕尺寸变更而重新渲染大小
效果图: 通过 window.addEventListener(resize, this.resizeChart); 实现 完整代码: <template><div class"dunBlock"><div class"char2" id"char2" ref"chart"></div></div…...
电脑图片损坏打不开怎么办?能修复吗?
照片和视频是记录和保存现实生活中的事件的最好方式。由于手机储存空间有限,一般我们会把有纪念意义的照片放到电脑上进行保存,但有时难免会遇到照片被损坏打不开的情况,一旦遇到这种情况,先不要急,也不要因为照片打不…...
vue-cli(二)
箭头函数 一般的函数: 这里window是用来调用函数的 function fun(){console.log(this) } window.fun(); 箭头函数: 1、如果只有一个参数,形参的小括号可以省略 2、如果只有一条语句,{}可以省略 完整的写法 let fun2 a>…...
今日头条的账号id在哪里看(网页版)
今日头条的账号id在哪里看(网页版) 1.https://mp.toutiao.com/profile_v4/index2.登录今日头条账号3.设置->头条号ID 1.https://mp.toutiao.com/profile_v4/index 2.登录今日头条账号 3.设置->头条号ID 打开下方链接: https://mp.to…...
单体应用提高性能和高并发处理-合理使用多核处理
合理使用多核处理能力是提升单体应用性能和处理高并发能力的重要手段。以下是关于如何合理利用多核处理器的详细讲解,包括多线程编程、线程池的使用、并行计算、以及如何避免常见的性能陷阱。 1. 多线程编程 多线程编程是利用多核处理器的直接方式。每个线程可以在…...
基于STM32/GD32的双CAN、一路485开发板
双CAN开发板 双CAN、一路485开发板的设计开发板配置器件选型CAN设计硬件设计软件设计 485设计硬件设计软件设计 其他设计LED硬件按键硬件 PCB板子和实物图开发板测试视频其他资料 双CAN、一路485开发板的设计 最近工作经常会出现一些小问题。就想设计一款带CAN的开发板用来测试…...
快排/堆排/归并/冒泡/
常见的内排序算法 插入排序 直接插入排序 原理:相当于扑克牌变成有序,先拿第一张,把他调节成有序,再拿第二张,与第一张相比找到第二张的位置,再继续拿第三张,以此类推。 void InsertSort(in…...
React基础教程(08):state体验
文章目录 7、state再体验7.1 异步更新状态7.2 同步更新状态方式17.3 同步更新状态方式27.4 betterScroll7.5 列表案例7、state再体验 7.1 异步更新状态 完整代码 import React from "react";export default class App extends React.Component{state = {count:1,}…...
Win10 创建新的桌面2,并实现桌面切换
1. Win10 创建新的桌面2 Win - Tab 2. Win10 桌面切换 Ctrl - Win - ←/→ 我们下期见,拜拜!...
MySQL数据库介绍及基础操作
目录: 一.数据库介绍 二.数据库分类 三. 数据库的操作 四. 常用数据类型 五. 表的操作 一.数据库介绍 1.文件保存数据有以下几个缺点: 1.1文件的安全性问题 1.2文件不利于数据查询和管理 1.3文件不利于存储海量数据 1.4文件在程序中控制不方便 为了解决上述问题&…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...
CSS3相关知识点
CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...
